Maths Olympiad Prep

Library / /26 of 27

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Brazil

33 friends are collecting stickers for a 2011-sticker album. A distribution of stickers among the 33 friends is incomplete when there is a sticker that no friend has. Determine the least mm with the following property: every distribution of stickers among the 33 friends such that, for any two friends, there are at least mm stickers both don't have, is incomplete.

Solutions — 2

Solution 1

Since 2011=336122011 = 33 \cdot 61 - 2, consider the example where Si={kZ61(i1)<k61i}S_i = \{k \in \mathbb{Z} \mid 61(i-1) < k \le 61i\} for i=1,2,,31i = 1, 2, \dots, 31, S32={kZ6131<k<6132}S_{32} = \{k \in \mathbb{Z} \mid 61 \cdot 31 < k < 61 \cdot 32\} and S33={kZ6132k2011}S_{33} = \{k \in \mathbb{Z} \mid 61 \cdot 32 \le k \le 2011\}.
Notice that Si=61|S_i| = 61 for 1i311 \le i \le 31 and Si=60|S_i| = 60 for i=32i = 32 and i=33i = 33. Thus SiSj261|S_i \cup S_j| \le 2 \cdot 61, and therefore m>2011261=1889m > 2011 - 2 \cdot 61 = 1889.

Now we prove that the minimum value of mm is, in fact, m=1890m = 1890. First, notice that if m=1890m = 1890 then SiSj20111890=121|S_i \cup S_j| \le 2011 - 1890 = 121. Suppose that S1S2S3>181|S_1 \cup S_2 \cup S_3| > 181. Then one of the sets, say S1S_1, has more than 181/3181/3 elements, that is, S161|S_1| \ge 61. But (S1S2S3)(S1S2)>181121    S3(S1S2)>60|(S_1 \cup S_2 \cup S_3) \setminus (S_1 \cup S_2)| > 181 - 121 \iff |S_3 \setminus (S_1 \cup S_2)| > 60. But S3S1=S3S1+S1S3(S1S2)+S1>60+61=121|S_3 \cup S_1| = |S_3 \setminus S_1| + |S_1| \ge |S_3 \setminus (S_1 \cup S_2)| + |S_1| > 60 + 61 = 121, contradiction. Hence S1S2S3181|S_1 \cup S_2 \cup S_3| \le 181.
So, S1S2S33S1S2S3+S4S5+S6S7++S32+S33181+15121=1996|S_1 \cup S_2 \cup \dots \cup S_{33}| \le |S_1 \cup S_2 \cup S_3| + |S_4 \cup S_5| + |S_6 \cup S_7| + \dots + |S_{32} + S_{33}| \le 181 + 15 \cdot 121 = 1996, and there exists sixteen stickers that none of the 33 friends have.

Solution 2

We will prove that m=1890m = 1890 in another way. The example for m=1889m = 1889 is the same from the previous solution.
Again, number the stickers from 1 to 2011 and let TiT_i be the set of the stickers that the friend ii does not have, 1i331 \le i \le 33.
Consider all pairs (x,{i,j})(x, \{i, j\}) such that xTiTjx \in T_i \cap T_j. If for every sticker there is a friend that has it, that is, T1T2T33=T_1 \cap T_2 \cap \dots \cap T_{33} = \emptyset then for each xx there exists kk such that xTkx \notin T_k. So each xx belongs to at most 32 sets TiT_i and, hence, there exist at most 2011(322)2011 \cdot \binom{32}{2} pairs (x,{i,j})(x, \{i, j\}). On the other hand, since TiTjm|T_i \cap T_j| \ge m there exists at least m(332)m \cdot \binom{33}{2} pairs (x,{i,j})(x, \{i, j\}). Therefore, if T1T2T33=T_1 \cap T_2 \cap \dots \cap T_{33} = \emptyset then
m(332)2011(322)    m1890 m \cdot \binom{33}{2} \le 2011 \cdot \binom{32}{2} \iff m \le 1890

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.