A magician wants to demonstrate the following trick to an audience of $n \ge 16$ people. He gives them $15$ hats and after giving instructions to his assistant (which the audience does not hear), leaves the hall. Some $15$ people in the audience put on one of the hats. The assistant tags in front of everyone, one of the hats with a marker and then the person with an unmarked hat takes it off. The magician then returns back to the hall and after surveying the situation, knows who in the audience has taken off his hat. For what $n$ is this possible?
HIDE: original wording Магьосник иска да покаже следния фокус пред публика от $n \ge 16$ души. Той им дава $15$ шапки и след като даде инструкции на помощника си (които публиката не чува), напуска залата. Някои $15$ души от публиката си слагат по една от шапките. Асистентът маркира пред всички една от шапките с маркер и след това човек с немаркирана шапка си я сваля. След това магьосникът се връща обратно в залата и след оглед на ситуацията познава кой от публиката си е свалил шапката. За кои $n$ е възможно това?Problem
Source: IFYM - XI International Festival of Young Mathematicians Sozopol 2022, Theme for 11-12 grade, 4th round p8
Tags: combinatorics, number theory
GM_YoanaMl
29.08.2024 04:15
Hmmm, no solutions yet...Let me fix that
The answer is $n=16$ and $n=17$.
Call "initial set" the set of people with hats from the beginning.
Label the people $0, 1, ..., n-1$.
Strategy for $n=16$:
.Let the person without a hat initially be number $x$. Then the assistant marks the person with number $15-x$ and let that person be $y$. Since $15$ is odd, $x\neq y$, so the assistant can do that. Then the magician comes and sees $y$ and the numbers $a$ and $b$ of the two people without hats. He checks which one of them is equal to $15-y$ and let that be $a$. So $b$ is the one who has taken off his hat and this way, the magician guesses it correctly. $\blacksquare$
Strategy for $n=17$:
.Let the two people without a hat initially be $x$ and $y$. Then the assistant marks $z$ such that $2z\equiv x+y$ (mod $17$). Since $17$ is odd, there exists exactly one $z$ from $0$ to $16$ that satisfies the congruence. If $z$ is equal to one of $x$ and $y$, then this implies $x\equiv y$ (mod $17$), which is impossible. So the assistant is allowed to mark $z$.
Now the magician comes and sees the marked number $z$ and the three people without hats, let them be $a$, $b$ and $c$. Let $z_a$, $z_b$ and $z_c$ be residues (mod $17$) such that $2z_a\equiv b+c$ (mod $17$), $2z_b\equiv a+c$ (mod $17$) and $2z_c\equiv a+b$ (mod $17$). Note that $z_a$, $z_b$ and $z_c$ are pairwise distinct because if two of them are equal, WLOG $z_a=z_b$, then $b+c\equiv2z_a\equiv2z_b\equiv a+c$ (mod $17$), which implies $a\equiv b$ (mod $17$), contradiction. The magician checks which one of $z_a$, $z_b$ and $z_c$ is equal to $z$, let it be $z_i$ where $i$ is $a$, $b$ or $c$. Then the person who took off his hat is $i$ and the magician guesses it correctly. $\blacksquare$
Why do all $n\geq 18$ not work:
.Suppose there is a strategy for $n=18+k$ where $k$ is a nonnegative integer. For any set $S$ of $15$ people let $M(S)$ be the person the assistant has to mark according to the strategy.
Claim: For any two sets of people $A$ and $B$ with $15$ elements such that $|A\cap B=14|$ we have $M(A)\neq M(B)$.
Proof: Suppose the contrary. Let $A=\{x_1, x_2, ..., x_{13}, y, a\} $and $B=\{x_1, x_2, ..., x_{13}, y, b\}$, $M(A)=M(B)=y$. Let the remaining $k+2$ people be $l_1, l_2, ..., l_{k+2}$. Consider the scenario when the magician sees $a, b, l_1, l_2, ..., l_{k+2}$ with no hats and $y$ is marked. Then both $A$ and $B$ are possible initial sets and both $a$ and $b$ are possible people who had taken off their hats, so the magician fails. $\square$
That means that from any set $S$ of $16$ people the values of $M(T)$, where $T$ is a subset of $S$ with $15$ elements, are pairwise distinct. Let $P$ be the set of $15$-element subsets of $S$. Since there are $16$ people and $16$ different values, then the function $f: P \rightarrow S$ such that for all $T \in P$ $ f(T)=M(T)$ is a bijection. Fix a person $X$ and a set $Q$ of $18$ people including $X$ and consider the number $m$ of pairs of the form $(A, B)$ where $A$ is a subset of $Q$ of $16$ people including $X$ and $B$ is a subset of $A$ with $15$ people such that $M(B)=X$. On one hand, if we fix $A$, we have exactly $1$ possible option for $B$ because $f$ is bijective. So $m$ is the number of $16$-element subsets in $Q$ that include $X$, which is ${17\choose 15}=136$. On the other hand, if we fix $B$, we have $3$ options for $A$ - the union of $B$ and one of the remaining $3$ people in $Q$. That means $m$ is divisible by $3$, contradiction! Hence the magician fails and we are ready. $\blacksquare$