IMO problem 1

The post below has been deleted. Click to close.

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

iandrei

138 posts

iandrei

#1 h Jul 14, 2003, 5:06 PM • 11 Y

Y by Davi-8191, Wizard_32, aops5234, Adventure10, Sprites, THEfmigm, megarnie, Mango247, and 3 other users

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.

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

Anonymous

334 posts

Anonymous

#2 h Jul 15, 2003, 12:18 PM • 8 Y

Y by ValidName, lahmacun, Adventure10, myh2910, Mango247, and 3 other users

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.

Z K

The post below has been deleted. Click to close.

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

Alison

264 posts

Alison

#3 h Jul 18, 2003, 4:00 PM • 6 Y

Y by A_Math_Lover, biomathematics, Adventure10, Mango247, and 2 other users

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.

Z K Y

The post below has been deleted. Click to close.

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

Anonymous

334 posts

Anonymous

#4 h Jul 18, 2003, 11:45 PM • 6 Y

Y by ValidName, Adventure10, Mango247, and 3 other users

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 ..

Z K

The post below has been deleted. Click to close.

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

Anonymous

334 posts

Anonymous

#5 h Aug 4, 2003, 10:59 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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

Z K

The post below has been deleted. Click to close.

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

me@home

2349 posts

me@home

#6 h Jun 10, 2006, 7:38 PM • 4 Y

Y by Adventure10, Mango247, and 2 other users

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 ..

Z K Y

The post below has been deleted. Click to close.

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

msecco

154 posts

msecco

#7 h Aug 14, 2009, 9:02 PM • 4 Y

Y by Adventure10, Mango247, and 2 other users

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

Z K Y

The post below has been deleted. Click to close.

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

Bugi

1857 posts

Bugi

#8 h Aug 14, 2009, 9:13 PM • 3 Y

Y by Adventure10 and 2 other users

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!

Z K Y

The post below has been deleted. Click to close.

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

Dragonboy

38 posts

Dragonboy

#9 h Jun 16, 2012, 5:31 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

Mahi

52 posts

Mahi

#10 h Jun 16, 2012, 7:22 AM • 4 Y

Y by Adventure10, Mango247, and 2 other users

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

Z K Y

The post below has been deleted. Click to close.

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

Dragonboy

38 posts

Dragonboy

#11 h Jun 16, 2012, 8:17 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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|$

Z K Y

The post below has been deleted. Click to close.

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

Mahi

52 posts

Mahi

#12 h Jun 16, 2012, 8:47 AM • 4 Y

Y by Adventure10, Mango247, and 2 other users

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

Z K Y

The post below has been deleted. Click to close.

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

Dragonboy

38 posts

Dragonboy

#13 h Jun 16, 2012, 9:31 AM • 4 Y

Y by Adventure10, Mango247, and 2 other users

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?

Z K Y

The post below has been deleted. Click to close.

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

Mahi

52 posts

Mahi

#14 h Jun 16, 2012, 2:52 PM • 4 Y

Y by Adventure10, Mango247, and 2 other users

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.

Z K Y

The post below has been deleted. Click to close.

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

Wolstenholme

543 posts

Wolstenholme

#15 h Aug 4, 2014, 5:20 PM • 3 Y

Y by Adventure10 and 2 other users

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.

Z K Y

The post below has been deleted. Click to close.

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

Math4Life7

1703 posts

Math4Life7

#69 h Oct 27, 2023, 8:23 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

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

ihatemath123

3449 posts

ihatemath123

#70 h Dec 30, 2023, 3:41 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

mannshah1211

652 posts

mannshah1211

#71 h Jan 17, 2024, 9:10 AM

Y by

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.

This post has been edited 3 times. Last edited by mannshah1211, Jan 17, 2024, 9:53 AM

Z K Y

The post below has been deleted. Click to close.

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

eibc

600 posts

eibc

#72 h Feb 22, 2024, 3:17 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

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

RGB

19 posts

RGB

#73 h Feb 22, 2024, 3:18 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

dolphinday

1328 posts

dolphinday

#74 h Feb 25, 2024, 7:06 PM

Y by

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.

This post has been edited 1 time. Last edited by dolphinday, Feb 25, 2024, 7:21 PM

Z K Y

The post below has been deleted. Click to close.

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

bjump

1032 posts

bjump

#75 h Apr 1, 2024, 11:39 PM • 1 Y

Y by megarnie

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.

Z K Y

The post below has been deleted. Click to close.

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

RedFireTruck

4243 posts

RedFireTruck

#76 h Jul 30, 2024, 9:31 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1286 posts

ezpotd

#77 h Aug 25, 2024, 7:08 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

joshualiu315

2534 posts

joshualiu315

#78 h Sep 30, 2024, 5:17 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

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

Saucepan_man02

1356 posts

Saucepan_man02

#79 h Nov 22, 2024, 1:47 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

Maximilian113

575 posts

Maximilian113

#80 h Nov 26, 2024, 3:43 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

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

megahertz13

3184 posts

megahertz13

#81 h Nov 26, 2024, 5:05 PM

Y by

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}$ .

This post has been edited 1 time. Last edited by megahertz13, Nov 26, 2024, 5:05 PM

Z K Y

The post below has been deleted. Click to close.

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

ihategeo_1969

239 posts

ihategeo_1969

#82 h Mar 21, 2025, 8:14 AM

Y by

Say $t_1$ , $\dots$ , $t_k$ are max such subsets.

So adding $A_{k+1}$ has an element common with one of $A_1$ , $A_2$ , $\dots$ , $A_k$ . Hence for any $T \in S/\{t_1\dots,t_k\}$ , we have $a_\ell+T=a_j+t_i$ Fix RHS and see that $a_\ell$ takes $101-1$ values and so $101k \ge \frac{10^6-k}{100} \implies k>99 \iff k \ge 100$ And done.

Z K Y

The post below has been deleted. Click to close.

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

YaoAOPS

1541 posts

YaoAOPS

#83 h Apr 23, 2025, 7:46 PM

Y by

Let $D = A - A$ be the elements which can be expressed as the difference of two elements in the list. Then $|S| \le 101 \cdot 100 + 1 = 10101$ since $0 \in D$ is over counted $100$ times. We now select each $t_i$ iteratively. Note that if $t_i$ is selected, then any subsequent $t_j$ selected can't be in $t_i + D$ for the sets to be pairwise disjoint, and furthermore this is sufficient. As such, we may select $t_i$ from $S \setminus \bigcup_{j=1}^{i-1} (t_j + D)$ while preserving the condition. For each $i$ , we have that
$\begin{align*} \left|S \setminus \bigcup_{j=1}^{i-1} (t_j + D)\right| &\ge 1000000 - \sum_{j=1}^{99} \left|(t_j + D)\right| \\ &\ge 1000000 - 99 \cdot 10101 = 1. \end{align*}$ so we may choose $t_{100}$ as well to finish.

Z K Y