Maths Olympiad Prep

Library / /9 of 25

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

Snow White and the Seven Dwarves are living in their house in the forest. On each of 16 consecutive days, some of the dwarves worked in the diamond mine while the remaining dwarves collected berries in the forest. No dwarf performed both types of work on the same day. On any two different (not necessarily consecutive) days, at least three dwarves each performed both types of work. Further, on the first day, all seven dwarves worked in the diamond mine.

Prove that, on one of these 16 days, all seven dwarves were collecting berries.

Solutions — 2

Solution 1

Solution:

We define VV as the set of all 128 vectors of length 7 with entries in {0,1}\{0,1\}. Every such vector encodes the work schedule of a single day: if the ii-th entry is 0 then the ii-th dwarf works in the mine, and if this entry is 1 then the ii-th dwarf collects berries. The 16 working days correspond to 16 vectors d1,,d16d_{1}, \ldots, d_{16} in VV, which we will call day-vectors. The condition imposed on any pair of distinct days means that any two distinct day-vectors did_{i} and djd_{j} differ in at least three positions.

We say that a vector xVx \in V covers some vector yVy \in V, if xx and yy differ in at most one position; note that every vector in VV covers exactly eight vectors. For each of the 16 day-vectors did_{i} we define BiVB_{i} \subset V as the set of the eight vectors that are covered by did_{i}. As, for iji \neq j, the day-vectors did_{i} and djd_{j} differ in at least three positions, their corresponding sets BiB_{i} and BjB_{j} are disjoint. As the sets B1,,B16B_{1}, \ldots, B_{16} together contain 168=128=V16 \cdot 8=128=|V| distinct elements, they form a partition of VV; in other words, every vector in VV is covered by precisely one day-vector.

The weight of a vector vVv \in V is defined as the number of 1-entries in vv. For k=0,1,,7k=0,1, \ldots, 7, the set VV contains (7k)\binom{7}{k} vectors of weight kk. Let us analyse the 16 day-vectors d1,,d16d_{1}, \ldots, d_{16} by their weights, and let us discuss how the vectors in VV are covered by them.

1. As all seven dwarves work in the diamond mine on the first day, the first day-vector is d1=(0000000)d_{1}=(0000000). This day-vector covers all vectors in VV with weight 0 or 1.

2. No day-vector can have weight 2, as otherwise it would differ from d1d_{1} in at most two positions. Hence each of the (72)=21\binom{7}{2}=21 vectors of weight 2 must be covered by some day-vector of weight 3. As every vector of weight 3 covers three vectors of weight 2, exactly 21/3=721 / 3=7 day-vectors have weight 3.

3. How are the (73)=35\binom{7}{3}=35 vectors of weight 3 covered by the day-vectors? Seven of them are day-vectors, and the remaining 28 ones must be covered by day-vectors of weight 4. As every vector of weight 4 covers four vectors of weight 3, exactly 28/4=728 / 4=7 day-vectors have weight 4.

To summarize, one day-vector has weight 0, seven have weight 3, and seven have weight 4. None of these 15 day-vectors covers any vector of weight 6 or 7, so that the eight heavyweight vectors in VV must be covered by the only remaining day-vector; and this remaining vector must be (1111111)(1111111). On the day corresponding to (1111111)(1111111) all seven dwarves are collecting berries, and that is what we wanted to show.

Solution 2

Solution:

If a dwarf XX performs the same type of work on three days D1,D2,D3D_{1}, D_{2}, D_{3}, then we say that this triple of days is monotonous for XX. We claim that the following configuration cannot occur: There are three dwarves X1,X2,X3X_{1}, X_{2}, X_{3} and three days D1,D2,D3D_{1}, D_{2}, D_{3}, such that the triple (D1,D2,D3)(D_{1}, D_{2}, D_{3}) is monotonous for each of the dwarves X1,X2,X3X_{1}, X_{2}, X_{3}.

(Proof: Suppose that such a configuration occurs. Then among the remaining dwarves there exist three dwarves Y1,Y2,Y3Y_{1}, Y_{2}, Y_{3} that performed both types of work on day D1D_{1} and on day D2D_{2}; without loss of generality these three dwarves worked in the mine on day D1D_{1} and collected berries on day D2D_{2}. On day D3D_{3}, two of Y1,Y2,Y3Y_{1}, Y_{2}, Y_{3} performed the same type of work, and without loss of generality Y1Y_{1} and Y2Y_{2} worked in the mine. But then on days D1D_{1} and D3D_{3}, each of the five dwarves X1,X2,X3,Y1,Y2X_{1}, X_{2}, X_{3}, Y_{1}, Y_{2} performed only one type of work; this is in contradiction with the problem statement.)

Next we consider some fixed triple X1,X2,X3X_{1}, X_{2}, X_{3} of dwarves. There are eight possible working schedules for X1,X2,X3X_{1}, X_{2}, X_{3} (like mine-mine-mine, mine-mine-berries, mine-berries-mine, etc). As the above forbidden configuration does not occur, each of these eight working schedules must occur on exactly two of the sixteen days. In particular this implies that every dwarf worked exactly eight times in the mine and exactly eight times in the forest.

For 0k70 \leqslant k \leqslant 7 we denote by d(k)d(k) the number of days on which exactly kk dwarves were collecting berries. Since on the first day all seven dwarves were in the mine, on each of the remaining days at least three dwarves collected berries. This yields d(0)=1d(0)=1 and d(1)=d(2)=0d(1)=d(2)=0. We assume, for the sake of contradiction, that d(7)=0d(7)=0 and hence
d(3)+d(4)+d(5)+d(6)=15 d(3)+d(4)+d(5)+d(6)=15
As every dwarf collected berries exactly eight times, we get that, further,
3d(3)+4d(4)+5d(5)+6d(6)=78=56 3 d(3)+4 d(4)+5 d(5)+6 d(6)=7 \cdot 8=56
Next, let us count the number qq of quadruples (X1,X2,X3,D)(X_{1}, X_{2}, X_{3}, D) for which X1,X2,X3X_{1}, X_{2}, X_{3} are three pairwise distinct dwarves that all collected berries on day DD. As there are 765=2107 \cdot 6 \cdot 5=210 triples of pairwise distinct dwarves, and as every working schedule for three fixed dwarves occurs on exactly two days, we get q=420q=420. As every day on which kk dwarves collect berries contributes k(k1)(k2)k(k-1)(k-2) such quadruples, we also have
321d(3)+432d(4)+543d(5)+654d(6)=q=420 3 \cdot 2 \cdot 1 \cdot d(3)+4 \cdot 3 \cdot 2 \cdot d(4)+5 \cdot 4 \cdot 3 \cdot d(5)+6 \cdot 5 \cdot 4 \cdot d(6)=q=420
which simplifies to
d(3)+4d(4)+10d(5)+20d(6)=70 d(3)+4 d(4)+10 d(5)+20 d(6)=70
Finally, we count the number rr of quadruples (X1,X2,X3,D)(X_{1}, X_{2}, X_{3}, D) for which X1,X2,X3X_{1}, X_{2}, X_{3} are three pairwise distinct dwarves that all worked in the mine on day DD. Similarly as above we see that r=420r=420 and that
765d(0)+432d(3)+321d(4)=r=420 7 \cdot 6 \cdot 5 \cdot d(0)+4 \cdot 3 \cdot 2 \cdot d(3)+3 \cdot 2 \cdot 1 \cdot d(4)=r=420
which simplifies to
4d(3)+d(4)=35 4 d(3)+d(4)=35
Multiplying (1) by 40-40, multiplying (2) by 1010, multiplying (3) by 1-1, multiplying (4) by 44, and then adding up the four resulting equations yields 5d(3)=305 d(3)=30 and hence d(3)=6d(3)=6. Then (4) yields d(4)=11d(4)=11. As d(3)+d(4)=17d(3)+d(4)=17, the total number of days cannot be 16. We have reached the desired contradiction.

A Variant. We follow the second solution up to equation (3). Multiplying (1) by 88, multiplying (2) by 3-3, and adding the two resulting equations to (3) yields
3d(5)+10d(6)=22 3 d(5)+10 d(6)=22
As d(5)d(5) and d(6)d(6) are positive integers, (5) implies 0d(6)20 \leqslant d(6) \leqslant 2. Only the case d(6)=1d(6)=1 yields an integral value d(5)=4d(5)=4. The equations (1) and (2) then yield d(3)=10d(3)=10 and d(4)=0d(4)=0.

Now let us look at the d(3)=10d(3)=10 special days on which exactly three dwarves were collecting berries. One of the dwarves collected berries on at least five special days (if every dwarf collected berries on at most four special days, this would allow at most 74/3<107 \cdot 4 / 3<10 special days); we call this dwarf XX. On at least two out of these five special days, some dwarf YY must have collected berries together with XX. Then these two days contradict the problem statement. We have reached the desired contradiction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.