A puzzle, courtesy of the Midnight Mathematicians: “A passel of math students are kidnapped and held captive in some unknown, and probably unfriendly, vector space. On the forehead of each student, without their knowledge, is drawn either a 1 or a 0. The hyper-intelligent, pan-dimensional captor will only give the information necessary to leave said vector space to students who correctly identify the mark on their forehead. At the end of each day, each student has the opportunity to guess, but an incorrect guess means they will be trapped forever. The students are not allowed to communicate in any way, but every day they see each other for their one meal together (also, there are no surfaces which produce clean reflections in this space). The only information they are given is that there is at least one student with a 1 and at least one student with a 0. What is the largest number of days it could need to take for n students (n>=2) to all set themselves free?”
Send your solutions (with proof) to firstname.lastname@example.org. If you are correct, you will be given the highest of accolades: your name mentioned here, next issue.
Let p represent the number of foreheads with a 1, and let q represent the number of foreheads with a 0.
We know that n>p,q>0. Without loss of generality, assume that p>=q, which implies that q<=n/2.
Let d represent the number of days that the students have been trapped.
Conjecture: On Day d, some student(s) start escaping if and only if d=q.
Proof by induction:
Base Case (Day 1):
If q = 1:
The student with a 0 sees n-1 1’s on everybody else’s forehead. This allows him to quickly deduce that his forehead must have a 0, and he escapes the first day.
If q > 1:
Everybody sees both 0’s and 1’s, so nobody can deduce the number on their forehead. Therefore, nobody can escape.
Inductive Step (Day d+1):
Assume our conjecture is true for all previous Days.
If all students still remain on Day d+1, that means that q > d, since otherwise some student(s) would have escaped already.
If q = d+1:
Each of the q students with a 0 sees q-1=d 0’s. But, if there were truly d 0’s out there, they would have escaped the previous day, according to our conjecture.
Therefore, each of the q students can deduce that he must have a 0 on his forehead, to bring the total number of 0’s up to q=d+1 (which is why no one had already escaped). This group of students escapes that very day.
If q > d+1:
Everybody sees at least d+1 0’s and 1’s (remember, p>=q). Because each student only knows that q > d (ie, q could be as small as d+1), nobody has enough information to know what his forehead says. Therefore, nobody can escape.
We have shown the base case and the inductive step, therefore the conjecture has been proved by induction.
Note that the students with 0’s escape as a group, since each can come to the same conclusion at the same time.
Because of this, if at any point students escape, the remaining students can deduce that they must have not been part of that group (otherwise they would have escaped with the group of 0’s).
Therefore, all of the students will have finished escaping no later than one day after the first students escape, which is Day q+1.
Also, note the special case where p=q. Not only do the group of 0’s escape on Day q, but so do the group of 1’s.
If by Day n/2-1 nobody has escaped, that means that q>=n/2. Because p+q = n, that implies that p=q=n/2. Therefore, on Day n/2, each student can deduce the number on his forehead. (for example, if Huckleberry sees n/2 0’s and n/2-1 1’s, he knows he must be a 1).
So, if p!=q, all students escape by Day q+1 (q students on Day q, and p students on Day q+1). If p=q=n/2, all students escape on Day n/2.
Therefore, the worse case scenario is as follows:
If n even, then all students escape by Day n/2.
If n odd, then all students escape by Day (n-1)/2 + 1 = (n+1)/2
The correct answer is:
n/2 days (rounded up to the nearest day) for all n
Let us call the number of students with 1’s on their foreheads “k”, and the number of students with 0’s on their foreheads “j”. Let us assume for the sake of the proof that k <= j (if the inverse were true, we would simply switch “1” and “0”).
If k=1, that is, one student has a 1 and all other students have 0’s, the lone 1 student will leave the first night.
If k=2, that is, two students have 1’s and all other students have 0’s, each student with a 1 thinks to himself, “If I have a 0 on my head, that student with a 1 on his head will leave on the first night. Otherwise, I have a 1 on my head.” When nobody leaves the first night, the students with 1’s on their heads know they have 1’s and leave the second night.
If k=3, then each student with a 1 on his head thinks to himself “If I have a 0 on my head, then those students with 1’s on their heads will both leave on the second night. Otherwise, I have a 1 on my head.” When nobody leaves the second night, the students with 1’s on their heads know their numbers and leave the third night.
By induction, if there are k students with 1’s on their heads, then each of them thinks “If I have a 0 on my head, then the students with 1’s on their heads will leave on the (k-1)th night.” When nobody does, the students with 1’s on their heads know their numbers and leave on the kth night.
If k=j, then the students with 0’s on their heads go through the same process and everyone leaves on the same night (the kth). However, if k>j, then the students with 0’s on their heads will see the students with 1’s leave, realize they all must have 0’s, and leave the following night, the (k+1)th night.
Since k can at most be n/2 (rounded down), and we add 1 for odd n’s, then we can state the solution as: n/2 days, rounded to the nearest day.
It takes floor(n/2)+1 days for all n students to set themselves free
Let n = the total number of students
Let a = the number of students with 1’s and b = the number with 0’s
Without loss of generality, suppose b<=a
Lemma: Students with 0’s will leave on the bth day, and all students will have left by the b+1st day
Consider the case where b=1:
The single person with a zero will see that all other students have 1’s and will then be able to conclude that he has the sole zero because there must be at least one person with a 0. He will be able to leave the first day.
Since he was able to leave the first day, the remaining students will know that he saw all 1’s and will then conclude that they are 1’s
Now consider the case where b=2:
Seeing both 1’s and 0’s, no one will be able to determine their number on the first day. Everyone will then be able to conclude that since b =/= 1, b>=2 (And, by symmetry, the same for a). The two people with 0’s will only see one other person with a 0 and will conclude that they must have the other 0. The people with 0’s will then be able to leave the second day, followed by the people with 1’s on the third.
Suppose that there exists some k such that for all b=k. Looking around, the students with 0’s will see that k-1 of their peers have 0’s. Knowing that there must be at least k number of 0’s, they must themselves have a 0. The students with a 0 may then leave on the kth day followed by 1’s on the k+1st.
Thus, because we have shown it to be true for our base case b=1 and for b=k given that it is true for all b