Each student in a classroom has $0,1,2,3,4,5$ or $6$ pieces of candy. At each step the teacher chooses some of the students, and gives one piece of candy to each of them and also to any other student in the classroom who is friends with at least one of these students. A student who receives the seventh piece eats all $7$ pieces. Assume that for every pair of students in the classroom, there is at least one student who is friend swith exactly one of them. Show that no matter how many pieces each student has at the beginning, the teacher can make them to have any desired numbers of pieces after finitely many steps.
Problem
Source: Turkey TST 2004 - P6
Tags: combinatorics proposed, combinatorics
16.10.2019 04:18
We will call a subset of the students of the classroom a tasty subset if the teacher can make a sequence of steps so that each of the students of the subset gains exactly one candy, while noboby else gains a candy. Call a student tasty if the subset with only this student in it is a tasty subset. Our ultimate goal will be to show that all the students are tasty. Let's label the students $1, 2, \cdots, n$ arbitrarily, and let $S_i$ be the set of students which are either $i$ or friends with $i.$ Claim. For any subset $S \subseteq [n]$, $\cap_{i \in S} S_i$ is a tasty subset. Proof. We will prove this by strong induction on the size of $|S|.$ If $|S| = 1$ this is evident. Suppose it holds for $|S| \le k.$ When $|S| = k+1$, notice that $\cup_{i \in S} S_i$ is a tasty subset, from the condition of the problem. Hence, by PIE, it is not hard to see how to use the inductive hypothesis to string together steps after which the students in $\cap_{i \in S} S_i$ gain a candy and everyone else has the same number of candies. Hence the induction is complete. $\blacksquare$ Lemma. If $A, B$ are disjoint tasty subsets, then $A \cup B$ is tasty. Furthermore, if $A, B$ are tasty subsets with $A \subseteq B$, then $B / A$ is tasty. Proof. This is obvious. $\blacksquare$ Suppose, for contradiction, that not all students were tasty. Let $T$ be the nonempty set of non-tasty students. If $|T| = 1$, then because the set of all students is clearly tasty (the teacher just selects all the students), iterated applications of the lemma imply that the student in $T$ is tasty as well, contradiction. Else suppose that $|T| > 1.$ Consider the subset $P$ of all the students satisfying the following properties. Firstly, $P$ is an intersection of some of the $S_i$'s (and is hence tasty by the Claim). Secondly, $|P \cap T|$ is nonzero, and as small as possible subject to this condition. We claim then that $|P \cap T|$ is $1.$ Indeed, suppose not for contradiction. Let $v, w \in |P \cap T|.$ We know from the condition of the problem that there exists another student of label $s$ for some $s$ such that $s$ knows exactly one of $v, w.$ Then, we'd have that $P \cap S_s$ is also an intersection of the $S_i$'s, so that $|(P \cap S_s) \cap T|$ is smaller than $|P \cap T|$ and nonzero. This is absurd, and so our supposition that $|P \cap T| > 1$ was incorrect. But then, from repeated iteration of the lemma, it follows that the student in $P \cap T$ is tasty because we can just "subtract off" the other students (who are all tasty by $|P \cap T| = 1$). This is a contradiction to the fact that $T$ has only non-tasty students. Our assumption that not all students are tasty was incorrect, and so all students are tasty. Hence, the teacher can literally do whatever he/she wants, and we win. $\square$