Combinatorics and Probability 765distinct subsets of cardinal 2 inAis 4950. By the pigeonhole principle, there exist
distinct elementsx, y ∈ Athat belong to at least 49 subsets. Let these subsets be
A 1 ,A 2 ,...,A 49. Then the conditions of the problem imply that the union of these
subsets has 2+ 49 × 2 =100 elements, so the union isA. However, the union of any 48
subsets among the 49 has at most 2+ 2 × 48 =98 elements, and therefore it is different
fromA.
(G. Dospinescu)
893.First, it is not hard to see that a configuration that maximizes the number of partitions
should have no three collinear points. After examining several cases we guess that the
maximal number of partitions is
(n
2)
. This is exactly the number of lines determined by
two points, and we will use these lines to count the number of partitions. By pushing
such a line slightly so that the two points lie on one of its sides or the other, we obtain a
partition. Moreover, each partition can be obtained this way. There are 2
(n
2)
such lines,
obtained by pushing the lines through thenpoints to one side or the other. However,
each partition is counted at least twice this way, except for the partitions that come from
the sides of the polygon that is the convex hull of thenpoints, but those can be paired
with the partitions that cut out one vertex of the convex hull from the others. Hence we
have at most 2
(n
2)
/ 2 =
(n
2)
partitions.
Equality is achieved when the points form a convexn-gon, in which case(n
2)
counts
the pairs of sides that are intersected by the separating line.
(67th W.L. Putnam Mathematical Competition, 2006)
894.First solution: Consider the set of differencesD={x−y|x, y∈A}. It contains
at most 101× 100 + 1 =10101 elements. Two setsA+tiandA+tjhave nonempty
intersection if and only ifti−tjis inD. We are supposed to select the 100 elements in
such a way that no two have the difference inD. We do this inductively.
First, choose one arbitrary element. Then assume thatkelements have been chosen,
k≤99. An elementxthat is already chosen prevents us from selecting any element from
the setx+D. Thus afterkelements are chosen, at most 10101k≤ 10101 × 99 = 999999
elements are forbidden. This allows us to choose the(k+ 1 )st element, and induction
works. With this the problem is solved.
Second solution: This solution can be improved if we look instead at the set of positive
differencesP={x−y|x, y∈A, x≥y}. The setPhas
( 101
2)
- 1 =5051 elements. The
inductive construction has to be slightly modified, by choosing at each step thesmallest
element that is not forbidden. In this way we can obtain far more elements than the
required 100. In fact, in the general situation, the argument proves that ifAis ak-element
subset ofS={ 1 , 2 ,...,n}andmis a positive integer such thatn>(m− 1 )(
(k
2)
- 1 ), then
there existt 1 ,t 2 ,...,tm∈Ssuch that the setsAj={x+tj|x∈A},j= 1 , 2 ,...,m,
are pairwise disjoint.
(44th International Mathematical Olympiad, 2003, proposed by Brazil)