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 $2^7=128$ such strings. Denote by $T$ the set of all such strings and by $T_i$, for $i=1,2,\dots,7$, the set of such strings with $i$ ones. Note that $T_i$ 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 $i$th 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 $i$th string has a $1$ in the $j_1$th, $j_2$th, $j_3$th 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
.........