ISL 2003 C1
by Wolstenholme, Aug 4, 2014, 5:22 PM
Let 
be a 
-element subset of the set 
. Prove that there exist numbers 
, 
in 
such that the sets ![\[ A_j=\{x+t_j\mid x\in A\},\qquad j=1,2,\ldots,100 \]](//latex.artofproblemsolving.com/d/5/c/d5c2a7b943e8c7200361698f3eb6f83700ad68d6.png)
are pairwise disjoint.
Proof:
Let each element of
be the vertex of a graph where two vertices 
are connected by an edge if and only if the sets 
and 
are disjoint. Consider an arbitrary vertex 
. Since the 
the maximum number of vertices 
such that sets and 
are not disjoint is 
. Therefore every vertex of the graph has degree at least 
Therefore the graph has at least 
edges. It suffices to show that this graph contains 
as a subgraph.
Now, by Turan's Theorem, the maximum number of edges a graph with
vertices that does not contain may contain is obtained when the graph is a complete 
-partite graph with 
independent sets of size 
and 
independent set of size 
. It is easy to compute that this graph has 
edges. But since 
we have the desired result.
be a 
-element subset of the set 
. Prove that there exist numbers 
, 
in 
such that the sets ![\[ A_j=\{x+t_j\mid x\in A\},\qquad j=1,2,\ldots,100 \]](http://latex.artofproblemsolving.com/d/5/c/d5c2a7b943e8c7200361698f3eb6f83700ad68d6.png)
are pairwise disjoint.Proof:
Let each element of
be the vertex of a graph where two vertices 
are connected by an edge if and only if the sets 
and 
are disjoint. Consider an arbitrary vertex 
. Since the 
the maximum number of vertices 
such that sets and 
are not disjoint is 
. Therefore every vertex of the graph has degree at least 
Therefore the graph has at least 
edges. It suffices to show that this graph contains 
as a subgraph.Now, by Turan's Theorem, the maximum number of edges a graph with
vertices that does not contain may contain is obtained when the graph is a complete 
-partite graph with 
independent sets of size 
and 
independent set of size 
. It is easy to compute that this graph has 
edges. But since 
we have the desired result.
August 2016
June 2016