IMO ShortList 2001, combinatorics problem 4

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

15 users

TOPICS

No tags match your search

M

No tags match your search

M

IMO ShortList 2001, combinatorics problem 4

G H J

Reveal topic tags

Combinatorial Number Theory

greedy algorithm

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 2001, combinatorics problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Sep 30, 2004, 5:26 PM • 5 Y

Y by narutomath96, Adventure10, ImSh95, Mango247, ohhh

A set of three nonnegative integers $\{x,y,z\}$ with $x < y < z$ is called historic if $\{z-y,y-x\} = \{1776,2001\}$ . Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

Attachments:

This post has been edited 2 times. Last edited by orl, Oct 25, 2004, 12:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#2 h Sep 30, 2004, 5:27 PM • 3 Y

Y by Adventure10, ImSh95, Mango247

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

82 posts

jgao

#3 h Dec 14, 2006, 11:22 PM • 3 Y

Y by Adventure10, ImSh95, Mango247

Anyone with a solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

315 posts

#4 h Jun 8, 2008, 4:11 PM • 5 Y

Y by narutomath96, DCMaths, ImSh95, Adventure10, Mango247

Just do it.

We partition the nonnegative integers into three sets X, Y and Z by taking disjoint historic triples {x,y,z} x<y<z and putting x into X, y into Y and z into Z according to a simple algorithm. We also keep track of a set S which is the set of nonnegative integers not yet in X,Y or Z. The algorithm is as follows:

i) Take the least element of S, x, and put it into X (so remove it from S). We also put x+1776+2001 into Z.
ii) If x+1776 is in S, we put it into Y. If x+1776 is no longer in S, we put x+2001 into Y instead.
iii) Return to step (i), having removed another historic triple from S.

Since we keep taking the least remaining element of S, it is clear that if such an algorithm succeeds, we have put every integer into precisely one of X,Y and Z once, which is equivalent to having partitioned the integers into historic triples.

Step (i) will clearly succeed, because x is in S by definition, and x+1776+2001 must be in S, as it cannot yet be in X (being bigger than x), or Y (being bigger than x+2001) and can only be put into Z by this value of x.

Step (ii) must also succeed. Suppose it doesn't (noting that for x<1776 it will obviously always work). Then x+2001 must be in Z. But this implies that x-1776 was placed into at some point X. At the time this happened, x should have been placed into Y, but by virtue of its being in S, it isn't already in Y, so this is a contradiction. Thus step (ii) succeeds also, and the algorithm works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1963 posts

ABCDE

#5 h May 16, 2016, 4:19 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

We use the following algorithm: Let $a$ be the smallest integer that has not been put in a set. If $a+1776$ has not been put in a set make the set $\{a,a+1776,a+3777\}$ and otherwise make the set $\{a,a+2001,a+3777\}$ . Suppose that this fails at some point and we can make neither of those sets. This would mean that $a+2001$ was already in a set. It cannot be the least element of a set because otherwise we would have made a set with $a$ as the least element instead when we first put $a+2001$ in a set. If $a+2001$ is the middle element of a set then the least element has to be $a+225$ since $a$ is not in a set yet, but this would be the same contradiction as $a+2001$ being the least element. This means that $a+2001$ is the largest element of its set, so the least element would be $a-1776$ . But then we would have made our middle element $a$ , a contradiction. Hence, this algorithm works and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

386 posts

#6 h Aug 11, 2020, 1:10 PM • 1 Y

Y by ImSh95

So obviously we are going to have two types of historic sets:
$\{x,1776+x,3777+x\} \; (I)$ $\{x,2001+x,3777+x\} \; (II)$ so obviously we don't want to end up in a situation such that all the points except one in the set of $\mathbb{Z}_{\geq 0}$ are covered at all.So we need to devise an algorithm such that we don't get into that position.

Algorithm
The algorithm, takes the smallest number now covered by any of the sets. Use type $I$ if possible, if not then use $II$ .
To prove that this works we use contradiction.
Suppose this fails, so let $x_i$ be the $i$ -th turn.We say that the algorithm has failed on the $(n+1)$ -th turn. Where it failed must have been at $x_{n+1}+2001$ or $x_{n+1}+1776$ , since $x_{n+1}+3777$ hasn't been covered at all.Furthermore $x_{n+1}+b$ must have been the largest members of their respected set.So by backtracking we have that:
$x_{n+1}+2001-3777=x_{n+1}-1776 \; - \; \text{minimal element of set}$ But notice how then $x_{n+1}$ would have been covered by our algorithm.Thus a contradiction is taking place here.
For the case of $x_{n+1}+1776$ , we also get a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#7 h Dec 12, 2021, 10:55 PM • 2 Y

Y by centslordm, ImSh95

Needless to say, the flavortext didn't age well.

Call an element clogged if it's in a historic set and unclogged otherwise. We use a greedy algorithm, where on the $i$ th step, we construct a new historic set $H_i$ with $x$ as the smallest unclogged element, $y$ as $x+1776$ if it's unclogged and $x+2001$ otherwise, and $z=x+3777$ . I claim that it will not terminate.

Suppose FTSOC that on some turn, both $x+1776$ and $x+2001$ are clogged. Note that $x+2001$ must be a $z$ element by size, which means that either $x$ or $x+2021-1776$ is clogged as an $y$ element. The former is obviously impossible, and in the latter case, $x$ must have been clogged in the first place.

This post has been edited 2 times. Last edited by mathleticguyyy, Dec 13, 2021, 2:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1727 posts

awesomeming327.

#8 h Aug 11, 2022, 2:52 AM • 1 Y

Y by ImSh95

Let $1776=a,2001=b$ . Consider the following algorithm: consider a set $S$ . Let $m$ be the smallest nonnegative integer not in $S$ , then let $S$ be $S\cup \{m,m+a,m+a+b\}$ whenever possible, and let $S$ be $S\cup\{m,m+b,m+a+b\}$ if not possible, and we call $m$ an operator.

We claim that every point, one of the two historic sets above will be available. First, we take care of $m+a+b.$ Note that if $m+a+b$ is in the set, then there must've been an operator that is at least $m$ . However, that raises a contradiction because if a number larger than $m$ is used as an operator, then by then $m$ must have been in $S$ already, but now that we are using $m$ as an operator, $m$ must not have been in $S$ .

Now, if $m+a$ is unavailable, then either $m+a-b$ was an operator before or $m-b$ was an operator before. If $m+b$ is unavailable, then $m-a$ was an operator before. Since $m$ is currently being used as an operator, the historic set associated with $m-a$ is $\{m-a,m+b-a,m+b\}$ , but the set with $m+b-a$ is only used when $m$ is unavailable! Obviously this cannot be the case, so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1922 posts

#9 h Nov 16, 2022, 6:33 PM • 2 Y

Y by ImSh95, Mango247

We provide an algorithm that generates sets that cover any nonnegative integer eventually. Call a historic set an $\alpha$ set if $y-x=1776$ and $z-y=2001$ . Similarly, call a historic set a $\beta$ set if $y-x=2001$ and $z-y=1776$ .

Our algorithm first covers $0$ with an $\alpha$ set, then repeatedly tries to cover the lowest uncovered number with the same type of set until the $x$ of the new set has to be more than one greater than the $x$ of the previous set, then it switches to the other type of set. If at one point, the lowest uncovered number is greater than any covered number, restart by covering the lowest uncovered number with an $\alpha$ set.

Now, we will prove that our algorithm works. When the first $1776$ $\alpha$ sets are made, there will be a gap between the largest $y$ and the smallest $z$ . When we start to use the $\beta$ sets, note how the previously largest $y$ and the previously largest $z$ are now one-upped by the $x$ and $y$ in the new $\beta$ set. This continues until a new gap is formed between the largest $y$ and the smallest $z$ , and the algorithm is continued. If at any point the gap doesn't exist anymore, we can simply restart the algorithm. Now, we note that the $x$ and $z$ cannot possibly clash( $z$ is supposed to always be $1776+2001$ above $x$ which increases every time), and $y$ cannot clash because it one-ups the previous largest $z$ . QED.

This post has been edited 2 times. Last edited by cj13609517288, Nov 16, 2022, 6:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2455 posts

#10 h Jan 31, 2023, 12:18 AM • 1 Y

Y by ImSh95

Note that a historic set is either in the form $\{x, x+1776, x+1776+2001\}$ (which we will call a 1776 set) or $\{x, x+2001, x+1776+2001\}$ (a 2001 set).

We can use the following algorithm to achieve this task:
We let $x$ be the smallest number not yet covered. If none of the numbers in the 1776 set have been covered already, then we use a 1776 set, otherwise we use a 2001 set.

Now we prove that this algorithm works. We prove that if the 1776 set does not work, then the 2001 set will always work.
Assume for the sake of contradiction that the 2001 set does not work.
Clearly the $x$ element can't have already been covered.
If the $x+1776+2001$ element has been covered, then that means that on some previous step, we either used the 1776 set on $x+2001$ or the 2001 set on $x+1776$ . However, this is impossible as $x < x+1776 < x+2001$ .
If the $x+2001$ has already been covered, then either we used the 1776 set on $x+2001-1776$ , or we used any set on $x-1776$ . Clearly the first one is impossible as $x+2001-1776>x$ . Now we consider the second case. If we used the 1776 set on $x-1776$ , then it would imply that we would have already covered $x$ , a contradiction. If we used the 2001 set, then that means that some element in the 1776 set was already covered. If $x+2001$ was already covered, then this implies that $x$ was already covered, contradiction. Otherwise, this implies that $x$ was already covered, another contradiction.

Therefore, a situation where both sets don't work, and the algorithm always works. $\square$

This post has been edited 1 time. Last edited by programmeruser, Jan 31, 2023, 12:22 AM
Reason: add extra newline

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

499 posts

#11 h Mar 27, 2023, 2:01 AM • 1 Y

Y by ImSh95

We claim that using the following algorithm we can cover the postive integers:
-Find the lowest positive integer $x$ that hasn't already been covered.
-Let $y$ be the lowest if $x+1776$ and $x+2001$ that isn't covered.
-Let $z$ be $x+3777$ .
-Then, add the triple $\{x, y, z\}$ .

Assume towards a contradiction $x+2001$ is already covered. It can't be the 1st number in its triplet, since it's higher than $x$ and the triplets are added in strictly increasing order based on the 1st number. For the same reason, it can't be the 2nd number in its triplet. So, it is the third in its triplet. The first must be 1776. However, then, because $x$ has not yet been covered, when this triplet was created, $x$ would've been made the 2nd number, a contradiction. So, the 2nd step must be possible.

By similar logic, if $x+3777$ is already covered, then it must be the 3rd in its triplet. However, then $x$ would be the first, a contradiction.

So, we can continue this procedure indefinitely and cover the positive integers. We can flip it to cover the nonpositive integers. So, we can cover all integers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#12 h Jun 26, 2023, 8:24 PM • 1 Y

Y by ImSh95

dont like bashy stuff like this
silly from the aime

x,y,z=x (call it 1st element),x+{1776 or 2001} (second elements, where 1776 or 2001 is two options), x+1776+2001
Clearly the optimal strategy is to cover the smaller numbers (because why would you skip and go to larger? That just plugs your historic sets possible)
Now we show that the algorithm choosing the smallest number not used and use the set with smaller sum if possible, use the larger if not. We prove that this works. Suppose at x_n you cannot cover it. This means either both of the second elements are covered or the largest is. Clearly the largest is not by our algorithm of doing small first, so both x+1776 and x+2001 must be covered. x+2001 must be the largest number in its set (it can't be n+1776, and can't be n), hence the smallest number in this set must be x+2001-2001-1776. However, x_n is not covered, hence x_n-1776,x_n,x_n+2001 must have been used (smaller set). Hence, contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

575 posts

#13 h Apr 11, 2025, 7:43 PM

Y by

Replace $1776$ and $2001$ with any positive integers $a, b$ with $a<b.$ Note that historic sets would be of the form $\{ x, x+a, x+a+b \}$ or $\{x, x+b, x+a+b\}.$ We use the greedy algorithm, where we operate on the smallest nonnegative integer $k$ not yet covered. If $k+a$ is not yet covered, we use the former set, otherwise we use the latter.

It suffices to show that with this algorithm, no number is covered more than once. For the sake of a contradiction, assume that at some point $\ell$ is the smallest number not covered, but $\ell+a, \ell+b$ are already covered. Assume that this is the first occurence of such a situation. Observe that $\ell+a+b$ cannot be covered as it is larger than any $\ell_i+a+b$ covered previously. $\ell+a, \ell+b$ must not have been the smallest numbers in their sets as they are both larger than $\ell,$ so $\ell+a$ must have been covered with $\{\ell-b, \ell+a-b, \ell+a\}, \{\ell+a-b, \ell+a, \ell+2a\},$ while $\ell+b$ was covered along with $\{\ell-a, \ell+b-a, \ell+b\}, \{\ell+b-a, \ell+b, \ell+2b\}.$ For this the latter cannot occur as $\ell+b-a > \ell,$ so $\{\ell-a, \ell+b-a, \ell+b\}$ must occur. But this overlaps with any of the first two historic sets, contradiction. Hence the algorithm works. QED

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a