A teacher is known to have $2^k$ apples for some $k \in \mathbb{N}$. He ets one of the apples and distributes the rest of the apples to his students $A$ and $B$. The students do not see how many apples the other gets, and they do not know the number $k$. However, they have pre-selected a discreet way to reveal one another something about the number of apples: each of the students scratches their head either by their right, left or both hands, depending on the number of apples they have received. To the teacher's surprise, the students will always know which one of the students got more apples, or that the teacher ate the only apple by herself. How is this possible?
Problem
Source: Finland 2019, p5
Tags: combinatorics
12.03.2022 13:04
Can we say this: If the number of apples that they received mode 4 is: 0,2:both hands 1:right hand 3:left hand Then they will know that their teacher ate it by herself or not.
12.03.2022 13:14
Can we say this?: They can write their number(Apples) mod 2 or like a binary number they say their number from the right number like this: If it was 0:Right hand If it was 1:Left hand If their number is finished:Both hands Then they can know each other's number to know who ate more apples and by knowing the total apples that they ate they can know their teacher ate that apple or not: If the total was a number like 2^k,she didn't eat it. Else:She ate it
30.11.2022 05:31
Each student calculates the binary expansion of the number of apples they receive. Since the total of both of their apples combined is a mersenne number 2^k-1, a string of k 1s written in binary. Thus, for each binary place value up to 2^(k-1), one student has a 1 and the other has a 0. This also means that except for the case that zero apples are given at all, one student has an even number and the other has an odd number. Next they calculate the number of “holes” their binary number has. A hole is a single 0 or string of 0 preceded by or surrounded by 1s. For instance, 50 in binary 110010 has two holes, or 7 in binary 111 has none. We can call the corresponding strings of 1s “islands”. An odd number has one more island than hole (because of the one/s at the end) while an even number has equal number of holes and islands. Because a 1 in some digit place for one student corresponds to a 0 in that digit place to the other, a hole for one student corresponds to an island for the other. Each student knows the others number must either be the the number created by switching their holes with islands, or the number created by switching their holes with islands and placing an additional island in front of their highest value (for example if A has 18, which is 10010 in binary, they know that B has either 1101 or 13 apples, or 1…101101 or 13+32(2^n-1) for positive n). So the other student can only have the same number of holes or the same number plus or minus one. They will signal to each other the parity of the count of holes (for instance an odd number of holes is signaled by the right hand, or an even number of holes by the left). If they signal with the same hand, they both know that the student with the even number of APPLES has the greater amount. If they signal with different hands, they both know the student with the odd number of apples has the greater amount. This leaves the case where both students get zero apples. To account for this, have each student signal using both hands if they receive zero apples. Thus they can tell if they both received zero or if only one of them did.
30.11.2022 06:38
After thinking it over a bit, we could simplify it further to only need two signals. If instead of counting the parity of the number of runs of 0s, we count the parity of the number of runs of 1s (islands), we can impose a rule that counts for all cases including the case where both students get zero. Signaling an even number of islands with one hand and and an odd number of islands with the other shares enough information to not require the third hand. Differing signals means the student with the odd number of apples has the greater number, while similar signals means the student with the even number of apples has the greater number unless that number is zero, in which case the other student must have zero as well