Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 IMO Problems/Problem 6"

(Created page with '== Problem == Let <math>a_1, a_2, a_3, \ldots</math> be a sequence of positive real numbers, and <math>s</math> be a positive integer, such that <cmath>a_n = \max \{ a_k + a_{n-…')
 
(→‎2010 IMO Problem 6 - Aadi)
 
(85 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
=2010 IMO Problem 6=
 
== Problem ==
 
== Problem ==
  
Line 6: Line 7:
 
<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>
  
−
''Author: Morteza Saghafiyan, Iran''
+
== Solution ==
 +
So for solving This Problem, we need to take a assumption that,
 +
:Let
 +
:<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 } w_{l}.</math>
 +
:<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>n = t_{1}+...+t_{s}</math>
 +
*<math>t_{i} \text{is divisibe by i for every i}</math>
 +
::<math>T_{1} \text{ = ⟨1, 0, 0, . . . , 0⟩}</math>
 +
::<math>T_{2} \text{ = ⟨0, 2, 0, . . . , 0⟩}</math>
 +
::<math>T_{3} \text{ = ⟨0, 0, 3, . . . , 0⟩}</math>
 +
::::<math>.</math>
 +
::::<math>.</math>
 +
::::<math>.</math>
 +
::<math>T_{s} \text{ = ⟨0, 0, 0, . . . , s⟩}</math>
 +
:<math>\text{for n = 1,..., s, respectively. Then for any n} \not\le \text{s}</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>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 ==
 +
{{IMO box|year=2010|num-b=5|after=Last Question}}
 +
 
 +
[[Category:Olympiad Number Theory Problems]]
 +
 
 +
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

Latest revision as of 07:46, 12 March 2024

2010 IMO Problem 6

Problem

Let $a_1, a_2, a_3, \ldots$ be a sequence of positive real numbers, and $s$ 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.\] Prove there exist positive integers $\ell \leq s$ and $N$, such that \[a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.\]

Solution

So for solving This Problem, we need to take a assumption that,

Let
$w1 = \frac{a_{1}}{1}, w2 = \frac{a_{2}}{2}, ......, ws = \frac{a_{s}}{s}$
$\text{We claim the right choice of l is the one maximizing } w_{l}.$
$\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}.$
$\text{To this end, let’s define an n-type to be a vector T = ⟨t1,...,ts⟩ of nonnegative integers such that}$
  • $n = t_{1}+...+t_{s}$
  • $t_{i} \text{is divisibe by i for every i}$
$T_{1} \text{ = ⟨1, 0, 0, . . . , 0⟩}$
$T_{2} \text{ = ⟨0, 2, 0, . . . , 0⟩}$
$T_{3} \text{ = ⟨0, 0, 3, . . . , 0⟩}$
$.$
$.$
$.$
$T_{s} \text{ = ⟨0, 0, 0, . . . , s⟩}$
$\text{for n = 1,..., s, respectively. Then for any n} \not\le \text{s}$
$\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}$
$\text{the linear combinations possible in the recursion, in other words the recursion in the problem is phrased as}$
$a_{n} = max_{\text{(T is valid n-type)}} v(t)$
$\text{In fact, we have the following description of valid n-types:}$
$\text{Assume n} \not\le \text{s. Then an n-type ⟨}t_{1}\text{,..., }t_{s}\text{⟩ is valid if and only if either}$
    • $\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}$
    • $\text{there exists an index i}\not\le\text{s/2 with} t_{i} \ge \text{2i}$
$\text{Proof. Immediate by forwards induction on n > s that all n-types have this property.The reverse direction is by downwards}$
$\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}$
$\text{and the case} \sum i\frac{t_{i}}{i} = 2$
$\text{Now, for each n} \not\le \text{s we pick a valid n-type } T_{n} \text{ with } a_{n} = v(T_{n})$
$\text{if there are ties, we pick one for which the } l^{th} \text{ entry is as large as possible}$
$\text{Proof credits to Evan Chen}$

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_IMO_Problems/Problem_6&oldid=216924"