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.
Problem
Source: European Girl's MO 2013, Problem 6
Tags: pigeonhole principle, combinatorics, EGMO, EGMO 2013, Hi
11.04.2013 19:53
Here is a sketch : There are at most 6 days for which 3 of the dwarves collect berries. At most 5 days for which 4 of the dwarves collect berries. At most 3 days for which 5 of the dwarves collect berries. At most 1 day for which 6 of the dwarves collect berries. But one can check that the four equalities cannot appear simultanemously. Hence, at most 14 days. Plus the day when they all work in the mine : 15 days. Hence, if we consider an other supplementary day, the four dwarves will collect berries
12.04.2013 01:46
i got the following A,B,C,D denote the number of day 3,4,5,6 dwarves collect berries. I got this if D<=1 if D=1 then B<=6 but always B<=7 so D+B<=7 it always holds A<=7 if C=1 then A<=6 if C=2,3 then A<=4 but it holds C<=3 so C+A<=7 so A+B+C+D<=14 giving a contradiction. you get these inequallities by counting the number of some pairs in 2 different ways.
12.04.2013 08:38
Leader, I agree with your solution. It is more precise than mine. But do you think that there exists a configuration that really verifies the statement : on the first day, they all go in the mine. On the second one, they collect berries. Then, during 7 days they collect berries. The last 7 days they work in the mine ?
12.04.2013 11:41
yes let dwarves be 1,2,..,7 in the next 7 days the ones that collected berries are 1,2,3 1,4,5 1,6,7 2,4,6 2,5,7 3,4,7 3,5,6 then in the next 7 each dwarve did what he didn't do 7 days earlier.
12.04.2013 19:28
Here is a slightly different approach. Number the dwarves from 1 to 7 and assign a string of 0's and 1's to each day, of which entry i is 0 if dwarf i worked in the mine, and 1 if he worked in the field. There are 27=128 such strings. Denote by T the set of all such strings and by Ti, for i=1,2,…,7, the set of such strings with i ones. Note that Ti has \binom{7}{i} elements. Define a distance function d(s_1,s_2) on the set of such strings to be the number of entries in string s_1 which differs from the corresponding entry in string s_2, e.g. d(1001001,1111111)=4, since the strings differ in 4 places. Also define the \emph{adjacency set} A_s of a string s to be the set of strings t for which d(s,t)\le 1, i.e. all strings which differ from s in at most one position. Note that for any s, the set A_s has 8 elements, s and each of the 7 strings. Moreover, if we take s\in T_i, then A_s contains the one element from T_i, i elements from T_{i-1} and 7-i elements from T_{i+1}. The conditions of the problem can be restated as choosing a set X of 16 strings s_i for which the A_{s_i} are mutually disjoint. Therefore, their union must have 8\times 16=128 distinct strings, meaning that every string is in some A_{s_i}. We have 0000000\in X and hence that T_1\subseteq A_{0000000}. Also T_2\cap X=\emptyset, since every string in T_2 is distance 2 from 0000000. But each of the 21 elements of T_2 must be in some A_s, where s\in T_3. For each such s, there are 3 strings from T_2 in A_s. Hence we need 7 such s to put each of the elements of T_2 in exactly one set A_s. Hence X\cap T_3 has exactly 7 elements. Since T_3 has 35 elements, this means there are 28 more elements from T_3 that must be in some A_s. Moreover, these s cannot be in T_2, so they must be in T_4. But for each s\in T_4 the set A_s contains 4 elements from T_3. Hence, there needs to be 7 elements in X\cap T_4. For each of these 7 elements s, there are 3 elements in A_s\cap T_5. Since T_5 has 21 elements, T_5 is contained in the union of the A_s already picked. Thus the last A_s must be exactly T_6\cup T_7. But the only s\in T_6\cup T_7 for which A_s=T_6\cup T_7, is s\in T_7, or equivalently s=1111111. This means that on one of the days all the dwarves were working in the field.
17.05.2013 01:24
Here is a solution I came up with today during school and later in the day. It amusingly replaces combinatorial insight with a big power sum computation. It may generalize; I haven't checked. Let Q_n denote the vector space \left\{ 0,1 \right\}^n. For a vector v, let v[i] denote the ith component. We may identify each day with a vector v_k, where v_k[i] = 0 if dwarf i worked in the diamond mine, and v_k[i] = 1 otherwise. Let V = \left\{ v_1, v_2, \dots, v_{16} \right\} be the subset of Q_7 in the problem, and assume v_{16} = 0000000. We first prove the following: Lemma: Exactly two vectors start with each of 000, 001, \dots, 111. Similar statements hold for any choice of three indices. Proof. If three vectors start with 000 (say) then we run into problems. \blacksquare Now we know that v_{16} is the all-null vector. Ignoring that vector (and hence considering just the first 15 vectors), let n_i be the number of 1's in v_i, where i = 1, 2, \dots, 15. Claim: We have \begin{align*} \sum_{i=1}^{15} \binom{n_i}{1} &= \frac{16}{2} \binom{7}{1} = 56 \\ \sum_{i=1}^{15} \binom{n_i}{2} &= \frac{16}{2^2} \binom{7}{2} = 84 \\ \sum_{i=1}^{15} \binom{n_i}{3} &= \frac{16}{2^3} \binom{7}{3} = 70. \end{align*}Proof. This follows using the lemma and double counting. For example, the third equation is counting the number of quadruples (i, j_1, j_2, j_3) such that the ith string has a 1 in the j_1th, j_2th, j_3th position, where j_1 < j_2 < j_3. The left-hand side counts the number when summed by i; the right-hand side counts the number according to the \binom73 choices of (j_1, j_2, j_3). \blacksquare We may then rewrite the lemma as \begin{align*} \sum_{i=1}^{15} n_i &= 56 \\ \sum_{i=1}^{15} n_i^2 &= 2 \cdot 84 + 56 = 224 \\ \sum_{i=1}^{15} n_i^3 &= 6 \cdot 70 + 3 \cdot 224 - 2 \cdot 56 = 980. \end{align*}Now remark that (n_i-3)(n_i-4)(n_i-7) \le 0 for each integer 1 \le n_i \le 7. We compute \begin{align*} 0 &\ge \sum_{i=1}^{15} (n_i-3)(n_i-4)(n_i-7) \\ &= \sum_{i=1}^{15} n_i^3 - 14n_i^2 + 61n_i - 84 \\ &= 1 \cdot 980 - 14 \cdot 224 + 61 \cdot 56 - 15 \cdot 84 \\ &= 980 - 3136 + 3416 - 1260 \\ &= 0. \end{align*}This implies that n_i \in \left\{ 3,4,7 \right\} for each i. If n_i \neq 7 for any i then we have 224 = \sum n_i^2 \equiv 15 \cdot 2 \not\equiv 0 \pmod{7} which is impossible. This means that n_i = 7 for some i, and therefore, 1111111 \in V, as desired. Remark: Up to permutation there turns out to be a unique set of 16 vectors. Xinyang Chen gives the following compact description of the unique solution: 0000000 and 1111111, of course 1101000 and its six cyclic shifts 0110100, 0011010, 0001101, 1000110, 0100011, 1010001. The complements of the above seven strings (i.e.\ 0010111, 1001011, etc.).
25.05.2017 20:09
First, we claim that for any 1, 2, or 3 of the dwarves, each possible distribution of their work place on a day occurs an equal number of times throughout the 16 days. Otherwise, by Pigeonhole there exist three days and three dwarves that each work the same job throughout those days, so the last four dwarves must satisfy the condition of differing by at least 3 jobs each pair of days, which is easily seen to be impossible. Now, let a_i be the number of dwarves in the diamond mine on day i, and note that by the above and double counting, we have \sum\binom{a_i}1=2^{4-1}\binom71,\sum\binom{a_i}2=2^{4-2}\binom72,\sum\binom{a_i}3=2^{4-3}\binom73 so \sum a_i=56,\sum a_i^2=224,\sum a_i^3=980. Now, note that on the first day all seven work in the diamond mine, so summing across the rest of the days yields \sum a_i=49,\sum a_i^2=175,\sum a_i^3=637. In particular, we have that across the rest of the days \sum(a_i^3-7a_i^2+12a_i)=0, so as n^3-7n^2+12n=n(n-3)(n-4)\ge0 for all nonnegative integers n, we must have a_i=0,3,4 for all i>1. In particular, this means that if there did not exist a day in which all dwarves were collecting berries, then there were at least 8 days in which exactly 3 of the dwarves did one of the jobs. It is easy to show that this is impossible. WLOG suppose that only dwarves 1,2,3 worked that job for a day. Note that no two of the 8 days can have their sets of dwarves working that job share more than two dwarves, as otherwise the symmetric difference would not have size at least 3. Then, all of other 7 days must have at most one of dwarves 1,2,3 in that job, so at least two dwarves out of 4,5,6,7. But then as there are only 6 distinct pairs of dwarves and 7 days remaining, two of the days must share a pair of dwarves, a contradiction.
25.05.2017 23:39
11.03.2019 12:46
This solution is pretty unique. But it almost characterize such set of all possible 16 strings and proving that 17 does not work. First of all, remove all the snow white stuff and consider the set of 16 binary strings instead. We will need the following lemma more than once. Lemma : Let S be a set of 2^{n-1} binary strings, each with length n such that 000...0\in S. Suppose that for any i such that 1\leqslant i\leqslant n, if we delete i-th digit then we get each of all 2^{n-1} strings of length n-1 exactly once. Then set S must be in form \{a_1a_2...a_n\mid a_i\in\{0,1\} \text{ and } a_1+a_2+...+a_n\equiv 0\pmod 2\} Proof : Straightforward. Basically if we arrange each string by first n-1 digits, then the last digits of every strings are forced. This can be proven by using induction on the number of 1's. Now we give the main claim. Claim : Consider first three digits of each strings. Then each binary string with length three occurs exactly twice. Proof : Suppose that some string occurred three times. By suitable XOR operation, we can WLOG that one of them is 000000 and the other two begins with 000. Now by permuting last four digits, we can also WLOG that the second one is 0001110. Now the third one must be 0000111, 0001101, 0001011 or 0001111. Simple case-checking gives contradiction. Pick a tuple of any four positions (out of 7), by our lemma and main claim, it's easy to see that list of every strings, restricted to those four positions must be in form set of all 16 strings, each occur exactly once. set of all 8 strings with even number of 1's, each occur exactly twice. Call the former type bad and latter type good. We claim that Claim : There exists at least one good tuple. Proof : Suppose that there is no good tuple at all. By our lemma, if we restrict each string to first five digits, then our set must be in form \{\overline{a_1a_2...a_5}\mid a_1+a_2+...+a_5\equiv 0\pmod 2\}Similarly, a_6 and a_7 must be forced to be equal to a_5. This yields contradiction. Now WLOG that one good tuple is (1,2,3,4). Then consider two strings which begins with 0000, the first one must be 0000000. Clearly the last one must be 0000111. Thus another string which ends with 111 must be 111111. Hence we are done.
06.03.2023 06:20
Reminds me of 2010 C5. Represent the information in the problem by 16 binary strings s_1, s_2, s_3, \cdots, s_{16} each with seven digits. Let a_i be the number of 1's in string i (where we represent a dwarf collecting berries by a 1.) The goal is to show that there exists an a_i = 7. Claim. Across all strings, each 3-prefix is used exactly twice. Proof. Check that the second condition is violated otherwise (in other words, among the last four digits, we cannot have three distinct strings differ in at least three places pairwise). \blacksquare Thus by double counting pairs of digits in each string, we establish \sum_{i=1}^{16} a_i = 56, \ \sum_{i=1}^{16} {a_i \choose 2} = 4{7 \choose 2} = 84, \ \sum_{i=1}^{16} {a_i \choose 3} = 2{7\choose 3} = 70.This eventually yields \sum_{i=1}^{16} a_i^2 = 224 and \sum_{i=1}^{16} a_i^3 = 980. This implies (quite artificially, but in a motivated manner) \sum_{i=1}^{15} (a_i - 3)(a_i - 4)(a_i - 7) \geq 0.(Notice that we ignore the null string on the first day here.) But on the other hand, (a_i - 3)(a_i - 4)(a_i - 7) \leq 0 for obvious reasons, so equality must hold everywhere. In particular, a_i \in \{3, 4, 7\}. Combined with \sum_{i=1}^{16} a_i = 56, this is enough to imply \{a_1, a_2, \cdots, a_{16}\} = \{0, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 7\}as 2's and 5's cannot appear because of the second condition. This implies the result.
04.05.2023 08:58
This is a bit artificial problem. The triple thingy was too artificial to be honest, after noticing that anyone can tell that it was intended by the problem author. Sketch of my solution goes as follow: Note that a triple of 0 and 1's repeats exactly twice (call this fact 1). Let x_{i} be the number of dwarves working in berry forest on the i'th day. From fact 1 you can count \sum_{i=1}^{16} x_{i}, {x_{i} \choose 2}, {x_{i} \choose 3}. Then like consider the sum \sum_{i=1}^{16} (x_{i}-3)(x_{i}-4)(x_{i}-7), this will be 0. Which gives x_{i} \in {3,4,7}. Now assume x_{i} \neq 7. The fact that \sum_{i=1}^{16} x_{i} = 56 gives it that there must exist a x_{k} such that it is 7. So, we're done.
16.02.2024 15:43
This one is tough... This problem basically can be repeated as follow: There are 16 strings s_1, s_2, \cdots, s_{16} consists of 0 and 1, where any two strings has Hamming Distance at least 3. If s_1=0000000, prove that there exists an i such that s_i=1111111. Notice that for any (i,j,k), we know that each of the 8 possibility of s_t[i]+s_t[j]+s_t[k] can only appear for two different t (because the other four characters has to differ by at least 3 characters). Now let a_i be the number of 1 in s_i. Counting gives us \sum a_i = 56, \sum \tbinom{a_i}{2}=84, which yields \sum a_i^2=224, and \sum \tbinom{7}{3}=70, which yields \sum a_i^3=980. Miraculously, we got \sum(a_i-3)(a_i-4)(a_i-7)\geq 0. But since a_i are all integer, so \sum(a_i-3)(a_i-4)(a_i-7)\leq 0 as well. So each a_i must be 3,4,7 and we're done by the unique (7,3,1)-design. Side note: this solution is the same as many above, as I think this is the intended solution. The miraculous inequality might be tricky to find from scratch, however knowing some block design would help solve this (the unique (7,3,1)-design would provide a construction).
27.05.2024 16:58
.........