Difference between revisions of "2001 IMO Shortlist Problems/C4"
m (New page: == Problem == A set of three nonnegative integers <math>\{x,y,z\}</math> with <math>x < y < z</math> is called <i>historic</i> if <math>\{z - y,y - x\} = \{1776,2001\}</math>. Show that t...) |
(Adding in a solution) |
||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | {{ | + | We describe a greedy algorithm to cover all integers. If an integer has been included in a set, we call it 'colored'. We also say that a number x is 'in column A' (A being x, y, or z) if x was in the x, y, or z position in its historic set (e.g. in <math>\{1,2,4\}</math>, 4 is in column z, 2 in column y, and 1 in column x). |
| + | |||
| + | Steps of Algorithm: | ||
| + | 1) Take the smallest integer k which is not colored | ||
| + | 2) If k+a is likewise not colored, then the new historic set is <math>\{k,k+a,k+a+b\}</math> | ||
| + | 3) if k+a is colored, then the new historic set is <math>\{k,k+b,k+a+b\}</math> | ||
| + | |||
| + | Proof for why k+a+b is never colored in 2) or 3): | ||
| + | Assume otherwise. If k+a+b is in column z, then k would already be colored. If k+a+b is in column y, then k+a or k+b would be in column x, but this will never happen by the algorithm, as it says to take the smallest integer k which is not colored, so if k+a or k+b were chosen, k would already have been colored. Similarly, k+a+b can't be in column x. | ||
| + | |||
| + | We see that if this works, all sets will be pairwise disjoint, as at every stage, we only include integers which are not colored. Also, this covers (and colors) all nonnegative integers, as if there is a set of integers which have not been colored, the algorithm just takes the smallest one and continues until there are none left. | ||
| + | |||
| + | Now, we prove 2) and 3): | ||
| + | |||
| + | For 2), there is nothing left to prove as we have shown that k+a+b will always be available and not colored. | ||
| + | |||
| + | For 3), the main thing to prove is that if k+a is colored already, k+b cannot have been colored. Again, assume otherwise. If k+b has been colored, it can't be in column x, due to size constraints as above. If in column y, the only option is that k+b-a is the first value in its historic set (as otherwise k would already have been colored). However, <math>k + b - a > k</math>, as b > a. The last remaining option is that k+b is in column z, meaning k-a must be in column x. However, the algorithm states in 2) that the default is to color k-a+a = k, so in this case k would already be colored. And we are done. | ||
== Resources == | == Resources == | ||
Revision as of 16:30, 5 July 2020
Problem
A set of three nonnegative integers 
with 
is called historic if 
. Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.
Solution
We describe a greedy algorithm to cover all integers. If an integer has been included in a set, we call it 'colored'. We also say that a number x is 'in column A' (A being x, y, or z) if x was in the x, y, or z position in its historic set (e.g. in 
, 4 is in column z, 2 in column y, and 1 in column x).
Steps of Algorithm:
1) Take the smallest integer k which is not colored
2) If k+a is likewise not colored, then the new historic set is 
3) if k+a is colored, then the new historic set is 
Proof for why k+a+b is never colored in 2) or 3): Assume otherwise. If k+a+b is in column z, then k would already be colored. If k+a+b is in column y, then k+a or k+b would be in column x, but this will never happen by the algorithm, as it says to take the smallest integer k which is not colored, so if k+a or k+b were chosen, k would already have been colored. Similarly, k+a+b can't be in column x.
We see that if this works, all sets will be pairwise disjoint, as at every stage, we only include integers which are not colored. Also, this covers (and colors) all nonnegative integers, as if there is a set of integers which have not been colored, the algorithm just takes the smallest one and continues until there are none left.
Now, we prove 2) and 3):
For 2), there is nothing left to prove as we have shown that k+a+b will always be available and not colored.
For 3), the main thing to prove is that if k+a is colored already, k+b cannot have been colored. Again, assume otherwise. If k+b has been colored, it can't be in column x, due to size constraints as above. If in column y, the only option is that k+b-a is the first value in its historic set (as otherwise k would already have been colored). However, 
, as b > a. The last remaining option is that k+b is in column z, meaning k-a must be in column x. However, the algorithm states in 2) that the default is to color k-a+a = k, so in this case k would already be colored. And we are done.
