Difference between revisions of "2010 IMO Problems/Problem 6"
(→Solution) |
(→Solution) |
||
| Line 12: | Line 12: | ||
:<math>w1 = \frac{a_{1}}{1}, w2 = \frac{a_{2}}{2}, ......, ws = \frac{a_{s}}{s}</math> | :<math>w1 = \frac{a_{1}}{1}, w2 = \frac{a_{2}}{2}, ......, ws = \frac{a_{s}}{s}</math> | ||
:<math>\text{We claim the right choice of l is the one maximizing wl.}</math> | :<math>\text{We claim the right choice of l is the one maximizing wl.}</math> | ||
| − | :<math>\text{Our plan is to view each | + | :<math>\text{Our plan is to view each} a_{n} \text{as a linear combination of the weights} w_{1}\text{, ...,} w_{s} \text{and track their coefficients}.</math> |
:<math>\text{To this end, let’s define an n-type to be a vector T = ⟨t1,...,ts⟩ of nonnegative integers such that}</math> | :<math>\text{To this end, let’s define an n-type to be a vector T = ⟨t1,...,ts⟩ of nonnegative integers such that}</math> | ||
*<math>n = t_{1}+...+t_{s}</math> | *<math>n = t_{1}+...+t_{s}</math> | ||
| − | *<math>t_{i} is divisibe by i for every i</math> | + | *<math>t_{i} \text{is divisibe by i for every i}</math> |
== See Also == | == See Also == | ||
Revision as of 10:28, 6 October 2022
Problem
Let 
be a sequence of positive real numbers, and 
be a positive integer, such that
![\[a_n = \max \{ a_k + a_{n-k} \mid 1 \leq k \leq n-1 \} \ \textrm{ for all } \ n > s.\]](http://latex.artofproblemsolving.com/f/1/2/f12c9c5e0f154549118a33a2f359329333f432a7.png)
Prove there exist positive integers 
and 
, such that
![\[a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.\]](http://latex.artofproblemsolving.com/b/0/b/b0b2bd4507621302eeee27ae50ed9c0afd72c6ef.png)
Author: Morteza Saghafiyan, Iran
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
