Assume that we have already found t_1, t_2, ..., t_k (k<=99) and are searching for t_{k+1}. We can not take t_{k+1} only of form t_i+a_j-a_l, where 1<=i<=k and a_j and a_l are elements of A. So, we have k*101*100 forbidden values of t_{k+1}, which correspond to a_j<>a_l, and k forbidden values which correspond to a_j=a_l. So, at most 99*101*100+99=1000000-1 forbidden values, and at least 1 admissible.

Notice that if instead of taking an arbitrary t_{k+1}, you always take the smallest t_{k+1} that is not forbidden, you will only have to make sure that t_{k+1} is distinct from all t_i+a_j-a_l with a_j>a_l. This is true because the values with a_j<a_l are all <=t_k, and so have been forbidden at some earlier step. This gives you ceiling(1000000/5051) = 198 t_i's. However, Fedor's proof also shows that you can choose 100 t_i's such that the sets are parwise disjoint even when taken mod 10^6.

Let A = {a1 < a2 < ... < a101}. Draw an undirected graph and put a vertex between i and j iff the sets (A+i) and (A+j) are disjoint . The graph will have 10^6 vertices . For an arbitrary vertex x to be joined with y , x-y must not be one of the numbers ai - aj (i<>j) , which are 101*100 numbers . So the vertex x has degree at least 10^6 - 101*100 . But this means that the graph has at least 10^6(10^6 - 101*100)/2 edges. The problem asks to prove that there is an 100-clique in the graph. But by Turan's theorem , there is a k-clique in a graph with n vertices iff the number of edges is strictly greater than : M(n,k) = (k-2)/(k-1) * (n^2 - r^2)/2 + r*(r-1)/2 where we have taken r to be the remainder of n when divided by k-1. In our case n=10^6 , k=100 and r=1. A simple calculation shows that the number of vertices is greater than M(10^6,100)+1 and thus we are done. P.S. : in an IMO paper , should one prove Turan's theorem or not ? I guess so ..

Fedor Petrov wrote: Assume that we have already found t_1, t_2, ..., t_k (k<=99) and are searching for t_{k+1}. We can not take t_{k+1} only of form t_i+a_j-a_l, where 1<=i<=k and a_j and a_l are elements of A. So, we have k*101*100 forbidden values of t_{k+1}, which correspond to a_j<>a_l, and k forbidden values which correspond to a_j=a_l. So, at most 99*101*100+99=1000000-1 forbidden values, and at least 1 admissible. so it is right to assume that for every K there exists a number such that \lim \lambda

Fedor Petrov wrote: Assume that we have already found $\{t_k\}_{1=k}^{99}$ and are searching for $t_{k+1}$. We can not take $t_{k+1}$ only of form $t_i+a_j-a_l \ | \ 1\leq i\leq k \ \ a_j, a_l \in A$. So, we have $k*101*100$ forbidden values of $t_{k+1}$, which correspond to $a_j<>a_l$, and $k$ forbidden values which correspond to $a_j=a_l$. So, at most $99*101*100+99=1000000-1$ forbidden values, and at least $1$ admissible. Alison wrote: Notice that if instead of taking an arbitrary $t_{k+1}$, you always take the smallest $t_{k+1}$ that is not forbidden, you will only have to make sure that $t_{k+1}$ is distinct from all $t_i+a_j-a_l \ | \ a_j>a_l$. This is true because the values with $a_j<a_l$ are all $\leq t_k$, and so have been forbidden at some earlier step. This gives you $\lceil 1000000/5051 \rceil = 198 t_i's$. However, Fedor's proof also shows that you can choose $100 t_i's$ such that the sets are parwise disjoint even when taken $mod 10^6$. Guest wrote: Let $A = {a_1 < a_2 < ... < a_{101}}$. Draw an undirected graph and put a vertex between $i, j$ iff the sets $(A+i)$ and $(A+j)$ are disjoint . The graph will have $10^6$ vertices . For an arbitrary vertex $x$ to be joined with $y$ , $x-y$ must not be one of the numbers $ai - aj (i<>j)$ , which are $101*100$ numbers . So the vertex $x$ has degree at least $10^6 - 101*100$ . But this means that the graph has at least $10^6(10^6 - 101*100)/2$ edges. The problem asks to prove that there is an $100-clique$ in the graph. But by Turan's theorem , there is a $k-clique$ in a graph with $n$ vertices iff the number of edges is strictly greater than : $M(n,k) = (k-2)/(k-1) * (n^2 - r^2)/2 + r*(r-1)/2$ where we have taken $r$ to be the remainder of $n$ when divided by $k-1$. In our case $n=10^6 , k=100 , r=1$. A simple calculation shows that the number of vertices is greater than $M(10^6,100)+1$ and thus we are done. P.S. : in an IMO paper , should one prove Turan's theorem or not ? I guess so ..

This problem has been proposed by Carlos Gustavo Tamm de Araujo Moreira, from Brazil.

http://www.artofproblemsolving.com/Wiki/index.php/IMO_Problems_and_Solutions It already says so in the Wiki. If you know an author which isn't listed there, please contribute!

May be my solution is wrong but it seems to me that we just need $|S|\geq 99\binom{101}{2}+100$. Please help me if you find any bug in my solution SOLUTION

Dragonboy wrote: Make a set $S_{i+1}\subset S_i$ such that $S_{i+1}$ doesn't contain $t_{i+1}$ and any element $K$ satisfying $K-t_{i+1}=|x-y|$ for any distinct $x,y\in A$ In here, you are just striking out the elements such that $K-t_{i+1}=|x-y|$, but the case remains where $K-t_{i+1}=-|x-y|$, which can also satisfy $y+t_i=x+t_j$ instead of $y+t_j=x+t_i$. So the limit is (about) doubled and it reaches near $10^6$, which can be achieved with a little more strict bounding. Although, nice approach with algorithmic way

Mahi wrote: Dragonboy wrote: Make a set $S_{i+1}\subset S_i$ such that $S_{i+1}$ doesn't contain $t_{i+1}$ and any element $K$ satisfying $K-t_{i+1}=|x-y|$ for any distinct $x,y\in A$ In here, you are just striking out the elements such that $K-t_{i+1}=|x-y|$, but the case remains where $K-t_{i+1}=-|x-y|$, which can also satisfy $y+t_i=x+t_j$ instead of $y+t_j=x+t_i$. So the limit is (about) doubled and it reaches near $10^6$, which can be achieved with a little more strict bounding. Although, nice approach with algorithmic way I think i have mentioned that $t_{i+1}$ is the smallest element in $S_i$ and any other element $K$ in $S_i$ is greater than $t_{i+1}$.So, there is no $K$ satisfying $K-t_{i+1}=-|x-y|$

Yes, if you choose $t_i$'s in increasing sequence, then it reduces to $t_i-t_j=y-x$ where $i>j$ which implies $y>x$ and thus the strategy is optimized by two

Mahi wrote: Yes, if you choose $t_i$'s in increasing sequence, then it reduces to $t_i-t_j=y-x$ where $i>j$ which implies $y>x$ and thus the strategy is optimized by two I'm not understanding what you're saying. Let me make it more clear for you (As much as i can) After choosing all $t_i$ by the algorithm, for the sake of contradiction , let's assume there exists $t_i>t_j$ and $x>y$ such that $t_i-t_j=x-y$. But It's not possible since we've banished such $t_i$ when we choose $t_{j+1}$ (According to algorithm). Is it clear now?

In my last post, I just shared my opinion about the algorithm. I understood it earlier. It was clear to me after I noticed the part "greatest in the set $S_i$". Thanks for your concern. By the way, something similar was also told by Alison in a previous post.

Let each element of $ S $ be the vertex of a graph where two vertices $ u, v $ are connected by an edge if and only if the sets $ A + u $ and $ A + v $ are disjoint. Consider an arbitrary vertex $ v $. Since the $ |A + v| = 101 $ the maximum number of vertices $ w $ such that sets $ A + v $ and $ A + w $ are not disjoint is $ 100 * 101 $. Therefore every vertex of the graph has degree at least $ 10^6 - 100*101 - 1. $ Therefore the graph has at least $ \frac{10^6(10^6 - 100*101 - 1)}{2} $ edges. It suffices to show that this graph contains $ K_{100} $ as a subgraph. Now, by Turan's Theorem, the maximum number of edges a graph with $ 10^6 $ vertices that does not contain $ K_{100} $ may contain is obtained when the graph is a complete $ 99 $-partite graph with $ 98 $ independent sets of size $ 10101 $ and $ 1 $ independent set of size $ 10102 $. It is easy to compute that this graph has $ \binom{98}{2}10101^2 + 98 \cdot 10101 \cdot 10102 = 494949494949 $ edges. But since $ \frac{10^6(10^6 - 100*101 - 1)}{2} = 494949500000 > 494949494949 $ we have the desired result.

Please let me know if the following solution is correct. I think its equivalent to what Fedor Petrov said, but then we have some complicated solutions using Turan's theorem, so I don't understand why we need that. I must be misunderstanding the problem, otherwise it is trivial... Choose $t_1$ arbitrarily from $S$. For $1<i \le 100$, we must choose $t_i$ such that $t_i \neq t_j +(a_k-a_l)$ for $1 \le j <i$ and $1 \le k,l \le 101$. The RHS assumes at most $101^2-100$ distinct values for each $j$, where $100$ is subtracted to remove the cases where $k=l$. Thus RHS assumes at most $(101^2-100)(i-1)$ values for each $i$. Thus there are at least $10^6-(101^2-100)(i-1) \ge 10^6-(101^2-100)(100)=1$ choice(s) for each $t_i$.

I think you are right, viperstrike. Remember this is from 11 years ago! AoPS was just in its infancy back then. I think you forgot to add 99...

General problem. Let $A$ be a $n+1$-element subset of set $S= \left \{ 1,2, \cdots ,n^3 \right \}$. Prove that there exist numbers $t_1,t_2, \cdots , t_n$ in $S$ such that the sets $$A_j = \{ x+t_j | x \in A \}, \qquad j=1,2, \cdots , n$$are pairwise disjoint.

iandrei wrote: Let $A$ be a $101$-element subset of the set $S=\{1,2,\ldots,1000000\}$. Prove that there exist numbers $t_1$, $t_2, \ldots, t_{100}$ in $S$ such that the sets \[ A_j=\{x+t_j\mid x\in A\},\qquad j=1,2,\ldots,100 \]are pairwise disjoint. We can get a better bound! Prove that $|S|\geq 198$

Solved on OTIS Excerpts. Very standard and straightforward counting problem. There will only be no way to add another $t_j$, from where there are $10^6$ choices, into the set T that contains all $t_k$s if the value is already in the set, or if there would then be some overlap between two sets $A_i$ and $A_j$; that is, $x+t_i=y+t_j$, for some distinct x and y in A. There are k of the first type; of the second type, |A|(|A|-1) ways for x and y, and |T| ways for there to exist some t_i such that there would be some overlap. Hence we have $$k+|A|(|A|-1)|T|=k+101*100k\ge 10^6.$$It is now easily checked (by, for example, estimating the LHS=10^4k+k) that k=99 is too small, hence $\boxed{k\ge 100}$, as desired. $\blacksquare$

Suppose that we have chosen a maximal number $k$ of $t_i$. This means that for all $10^6-k$ numbers $m$ in $S$ not among the $t_i$, there exists $t_i$ and $x, y \in A$ such that $t_i + x = m + y$. On the other hand, the number of triplets $(t_i, x, y)$ is bounded above by $10100k$, so it follows that $10100k \geq 10^6 - k$, enough to imply $k \geq 100$ (rounding up).

We can see that for $a_x, a_y \in A$. We want no pairs such that $a_x - a_y = t_i - t_j$. We choose our $t_i$ greedily and by induction. Firstly we choose $t_1 =1$. For our induction step we let $t_{n+1}$ be the first value such that $t_{n+1} - t_j \neq a_x - a_y$ for all $j \in [1, n]$. We can see that there are $\binom{101}{2}$ values of $a_x - a_y$, and there are $n$ values of $j$. Thus the number of values that cannot be obtained by $t_{100}$ is bounded above by $\binom{101}{2} \cdot 100 \leq 10^6$. $\blacksquare$

The "disjoint" condition is satisfied iff $a_w + t_x \neq a_y + t_z$ for all valid $(w,x,y,z)$; in other words, $|a_w - a_y| \neq |t_x - t_z|$ for all valid $w, x, y$ and $z$. There are up to $\binom{101}{2} = 5050$ distinct absolute differences between two elements of $A$. Consider just arithmetic sequences $t_1, t_2, \dots, t_{100}$ with common difference $d$, where $1 \leq d \leq 10101$. The possible values of $|t_x - t_z|$ are $\{ d, 2d, \dots, 99d \}$; as $d$ varies from $1$ to $10101$, there must be some (in fact, at least $5051$) values of $d$ for which none of $\{ d, 2d, \dots, 99d \}$ are the absolute difference between any two elements of $A$, so we just pick $d$ to be any of those values.

Let $k$ be the largest size of such a set $t$. Let $t_1, t_2, \cdots, t_k$ be the numbers, and let $A_1, A_2, \cdots, A_{101}$ be the numbers. Let $n$ be the number of numbers of the form $x - y + t_j$, where $x, y \in A$. Then, we must have the inequality $10^6 - k \le n,$ since if $10^6 - k > n,$ we have at least one more valid choice to add to $t$. But, in turn, $n \le 101 \cdot 100 \cdot k$, which gives the desired inequality. EDIT: This is incorrect. I'll edit in the correct solution sometime soon. EDIT 2: Done.

Suppose that we pick $n$ numbers $t_1, t_2, \ldots, t_n$ satisfying the problem conditions for maximal $n$. Then for $x \in S$ and $x \neq t_k$ for some $k$, we must have $x - t_{\ell} = a_i - a_j$ or $x = t_{\ell} + a_i - a_j$ for some integers $1 \le \ell \le n$ and $1 \le i \neq j \le 100$. For a fixed $t_\ell$, there are $101 \cdot 100 = 10100$ ways to choose $(a_i, a_j)$, which is enough to imply that $10100n \ge 10^6 - n$, or $n \ge 100$.

We can prove this by contradiction. Suppose there is a $101$-element subset $A$ of $S = \{1,2,\ldots,1000000\}$ such that, for any choice of $100$ numbers $t_1, t_2, \ldots, t_{100}$ from $S$, there exist indices $i$ and $j$ ($1 \leq i < j \leq 100$) such that $A_i$ and $A_j$ have at least one common element. Let $B_1, B_2, \ldots, B_{100}$ be the sets $A_1, A_2, \ldots, A_{100}$ respectively. For each $j$, the set $B_j$ can be expressed as $B_j = A + t_j = \{x + t_j \mid x \in A\}$. Now, consider the union of all $B_j$'s for $j = 1, 2, \ldots, 100$: \[ B = B_1 \cup B_2 \cup \ldots \cup B_{100} \] Since $B_j = A + t_j$, the union $B$ is essentially the set of all elements in $S$ that can be obtained by adding an element from $A$ to any of the $100$ chosen $t_j$'s. Now, by our assumption, there must exist two indices $i$ and $j$ ($1 \leq i < j \leq 100$) such that $B_i \cap B_j \neq \emptyset$. This implies that there exists an element $x$ in $A$ such that $x + t_i = x + t_j$, which means $t_i = t_j$. However, this contradicts our assumption that any choice of $100$ numbers $t_1, t_2, \ldots, t_{100}$ must yield distinct sets $B_j$. Therefore, our assumption must be false, and there must be a $101$-element subset $A$ with the desired property.

Keep on choosing $t_i$ until we get stuck(we can't pick any more $t$) for some $i = k$. This implies that for all $t \in S$, it has already been picked or that for some $a$, $b$, $t_i \in S$ we have $t = b + t_i - a$. So then there are at most $k \cdot 10100$($101$ choices for $b$ and $100$ for $a$) values for $t$, so $k \geq 100$ as desired.

badly worded solution Choose $t_i$'s greedily then for all $a$, $b$ in $A$, and $1 \le j \le 100$ we cannot pick $t_j+a-b$, or $t_i-b+a$ in the list of $t$'s in the future. So for every new $t$ added we eliminate at most $101 \cdot 100 = 10100$ more $t$'s. So we can pick at least $\left \lceil \frac{10^6}{10100} \right \rceil = 100$ different $t$'s before we could be forced to stop, finishing the problem.

we basically just dont want any absolute difference in $A$ to also be an absolute difference in $t$ there are at most $\binom{101}{2}=5050$ distinct absolute differences in $A$ this means that every time we pick a $t_i$, at most $1+5050\cdot2=10101$ elements get eliminated from $S$ as possibilities for other $t_i$ if we pick $t_1=1$, then only at most $5051$ elements get eliminated from $S$ the first time since $5051+98\cdot 10101=989898+5051<995000$, we can pick $t_{100}$, as desired.

Observe the condition is equivalent to the difference between no two $t_i$ being the difference between two $a_i$. Choose $t_i$, for each $t_i$ we automatically eliminate out of candidacy for future $t_i$ all the numbers that are a different of two $A_i$ from $t_i$, which is at most $2 \cdot \binom{101}{2}$, where the $2$ is for positve/negative, and we also eliminate the chosen number itself, for a total for $10101$ eliminations per chosen $t_i$. Now any number not eliminated can be added to $t_i$ and the condition will still be satisfied, so add the first $99$ numbers and see that we have eliminated $999999$ numbers, and there is one number remaining and we see that we can just add this and done.

Suppose we have a working set: $A = \{a_1, a_2, \dots, a_{101} \}$. Note that $A_i$ and $A_j$ are disjoint if and only if \[t_i-t_j \notin \{a_p-a_q\vert 1\le p \ne q \le 101\}.\] In order to get such a set, we will proceed by a greedy algorithm. Assume that we have already picked $n$ elements in $T = \{t_1, \dots, t_n\}$ such that $T$ is as large as possible. That means every $i \in \{1,2,\dots,10^6\}$ is either in $T$ or satisfies \[i = t_i+b-a,\] for some $t_i \in T$ and $a,b \in A$. There are at most $|T| \cdot |A| \cdot (|A|-1) = 10100n$ values of $i$. Thus, \[n+10100n \ge 10^6 \implies n>99,\] as desired. $\blacksquare$

Here we go: Consider the set $T$ to have $t_1, \cdots, t_n$ currently. Let $A = \{ a_1, a_2, \cdots, a_{101} \}$. Let set $D$ denote the pair-wise differences of elements of set $A$. Then, if we cant add another element $t \in S$ to $S$, then we must have: $t = t_k + d$ for some $d \in D$. Note that: $|D| \le 101*100$. Thus: $$101*100*n > 10^6 \implies n \ge 100$$and we are done.

Let the elements of $A$ be $a_1, a_2, \cdots a_{101},$ and let the elements of $T$ be $t_1, t_2, \cdots, t_n.$ Since each $x+t_j, x\in A$ is distinct, then clearly for all $p, q, r, s$ $$|t_p-t_q| \neq |a_r-a_s|.$$Set $t_1=1.$ Clearly since there are at most $\binom{101}{2}=5050$ pairwise differences among the elements of $A,$ every time we add a number to the set $T$ we reduce the possible number of potential numbers to add to $T$ by at most $2 \cdot 5050 + 1 = 10101.$ (we account for both sides, and the number itself) Therefore, after choosing $99$ numbers, there are at least $$10^6 - 10101\cdot 99=1$$possible number to add to the set $T,$ so thus it is possible to have $100$ elements in $T.$ QED

First choose a random $t_1\in S$. We will prove that if we have already chosen distinct $t_1,t_2,\dots,t_k$ satisfying the condition, then we can choose a $t_{k+1}$ such that the disjoint condition is satisfied. This will finish the problem. If there are any intersections, there exists a $1\le j\le k$ and $x,y\in A$ satisfying $$t_j+x=t_{k+1}+y\implies t_{k+1}=t_j+x-y.$$However, since $t_j\ne t_{k+1}$, we have $x\ne y$. Then, there are $$k\cdot 101\cdot 100=10100k$$ways to choose the right-hand side of the equation $t_{k+1}=t_j+x-y$. Since $t_{k+1}$ is not equal to any of $t_1, t_2,\dots,t_k$, there are at most $10101k$ numbers that $t_{k+1}$ cannot be. However, $$10101k\le 999999<|S|,$$so there always exists a $t_{k+1}$.