Problem

Source: Finland 2019, p5

Tags: combinatorics



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?