Difference between revisions of "2010 IMO Problems/Problem 6"
(→Solution) |
(→2010 IMO Problem 6 - Aadi) |
||
(25 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | =2010 IMO Problem 6= | ||
== Problem == | == Problem == | ||
Line 5: | Line 6: | ||
Prove there exist positive integers <math>\ell \leq s</math> and <math>N</math>, such that | Prove there exist positive integers <math>\ell \leq s</math> and <math>N</math>, such that | ||
<cmath>a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.</cmath> | <cmath>a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.</cmath> | ||
− | |||
− | |||
== Solution == | == Solution == | ||
Line 27: | Line 26: | ||
:<math>\text{an n-type is valid if it can be written as the sum of a valid k-type and a valid (n-k)-type componentwise. These represent}</math> | :<math>\text{an n-type is valid if it can be written as the sum of a valid k-type and a valid (n-k)-type componentwise. These represent}</math> | ||
:<math>\text{the linear combinations possible in the recursion, in other words the recursion in the problem is phrased as}</math> | :<math>\text{the linear combinations possible in the recursion, in other words the recursion in the problem is phrased as}</math> | ||
+ | :<math>a_{n} = max_{\text{(T is valid n-type)}} v(t)</math> | ||
+ | :<math>\text{In fact, we have the following description of valid n-types:}</math> | ||
+ | : | ||
+ | :<math>\text{Assume n} \not\le \text{s. Then an n-type ⟨}t_{1}\text{,..., }t_{s}\text{⟩ is valid if and only if either}</math> | ||
+ | **<math>\text{there exist indices i} \not\ge \text{j with i+j} \not\le \text{s,}t_{i}\not\le\text{i and }t_{j} \ge \text{j}</math> | ||
+ | **<math>\text{there exists an index i}\not\le\text{s/2 with} t_{i} \ge \text{2i}</math> | ||
+ | :<math>\text{Proof. Immediate by forwards induction on n > s that all n-types have this property.The reverse direction is by downwards}</math> | ||
+ | :<math>\text{induction on n. Indeed if} \sum i\frac{t_{i}}{i} \not\le 2 \text{then we may subtract off on of {T1, . . . , Ts} while preserving the condition}</math> | ||
+ | :<math>\text{and the case} \sum i\frac{t_{i}}{i} = 2</math> | ||
+ | :<math>\text{Now, for each n} \not\le \text{s we pick a valid n-type } T_{n} \text{ with } a_{n} = v(T_{n})</math> | ||
+ | :<math>\text{if there are ties, we pick one for which the } l^{th} \text{ entry is as large as possible}</math> | ||
+ | :<math>\text{Proof credits to Evan Chen}</math> | ||
== See Also == | == See Also == |
Latest revision as of 08:46, 12 March 2024
2010 IMO Problem 6
Problem
Let be a sequence of positive real numbers, and
be a positive integer, such that
Prove there exist positive integers
and
, such that
Solution
So for solving This Problem, we need to take a assumption that,
- Let
See Also
2010 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |
Let w1 = a1 1 , w2 = a2 2 , . . . , ws = as s . (The choice of the letter w is for “weight”.) We claim the right choice of ℓ is the one maximizing wℓ . Our plan is to view each an as a linear combination of the weights w1, . . . , ws and track their coefficients. To this end, let’s define an n-type to be a vector T = ⟨t1, . . . , ts⟩ of nonnegative integers such that • n = t1 + · · · + ts; and • ti is divisible by i for every i. We then define its valuation as v(T) = Ps i=1 witi . Now we define a n-type to be valid according to the following recursive rule. For 1 ≤ n ≤ s the only valid n-types are T1 = ⟨1, 0, 0, . . . , 0⟩ T2 = ⟨0, 2, 0, . . . , 0⟩ T3 = ⟨0, 0, 3, . . . , 0⟩ . . . Ts = ⟨0, 0, 0, . . . , s⟩ for n = 1, . . . , s, respectively. Then for any n > s, an n-type is valid if it can be written as the sum of a valid k-type and a valid (n − k)-type, componentwise. These represent the linear combinations possible in the recursion; in other words the recursion in the problem is phrased as an = max T is a valid n-type v(T). In fact, we have the following description of valid n-types: Claim — Assume n > s. Then an n-type ⟨t1, . . . , ts⟩ is valid if and only if either • there exist indices i < j with i + j > s, ti ≥ i and tj ≥ j; or • there exists an index i > s/2 with ti ≥ 2i. Proof. Immediate by forwards induction on n > s that all n-types have this property. The reverse direction is by downwards induction on n. Indeed if P i ti i > 2, then we may subtract off on of {T1, . . . , Ts} while preserving the condition; and the case P i ti i = 2