Maths Olympiad Prep

Library / Brazilian Math Olympiad /64 of 66

Brazilian Math Olympiad

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=33⋅61−22011 = 33 \cdot 61 - 2, consider the example where Si={k∈Z∣61(i−1)<k≤61i}S_i = \{k \in \mathbb{Z} \mid 61(i-1) < k \le 61i\} for i=1,2,…,31i = 1, 2, \dots, 31, S32={k∈Z∣61⋅31<k<61⋅32}S_{32} = \{k \in \mathbb{Z} \mid 61 \cdot 31 < k < 61 \cdot 32\} and S33={k∈Z∣61⋅32≤k≤2011}S_{33} = \{k \in \mathbb{Z} \mid 61 \cdot 32 \le k \le 2011\}.
Notice that ∣Si∣=61|S_i| = 61 for 1≤i≤311 \le i \le 31 and ∣Si∣=60|S_i| = 60 for i=32i = 32 and i=33i = 33. Thus ∣Si∪Sj∣≤2⋅61|S_i \cup S_j| \le 2 \cdot 61, and therefore m>2011−2⋅61=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 ∣Si∪Sj∣≤2011−1890=121|S_i \cup S_j| \le 2011 - 1890 = 121. Suppose that ∣S1∪S2∪S3∣>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, ∣S1∣≥61|S_1| \ge 61. But ∣(S1∪S2∪S3)∖(S1∪S2)∣>181−121  ⟺  ∣S3∖(S1∪S2)∣>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 ∣S3∪S1∣=∣S3∖S1∣+∣S1∣≥∣S3∖(S1∪S2)∣+∣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 ∣S1∪S2∪S3∣≤181|S_1 \cup S_2 \cup S_3| \le 181.
So, ∣S1∪S2∪⋯∪S33∣≤∣S1∪S2∪S3∣+∣S4∪S5∣+∣S6∪S7∣+⋯+∣S32+S33∣≤181+15⋅121=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, 1≤i≤331 \le i \le 33.
Consider all pairs (x,{i,j})(x, \{i, j\}) such that x∈Ti∩Tjx \in T_i \cap T_j. If for every sticker there is a friend that has it, that is, T1∩T2∩⋯∩T33=∅T_1 \cap T_2 \cap \dots \cap T_{33} = \emptyset then for each xx there exists kk such that x∉Tkx \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 ∣Ti∩Tj∣≥m|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 T1∩T2∩⋯∩T33=∅T_1 \cap T_2 \cap \dots \cap T_{33} = \emptyset then
m⋅(332)≤2011⋅(322)  ⟺  m≤1890 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.