Problem

Source: IFYM - XI International Festival of Young Mathematicians Sozopol 2022, Theme for 11-12 grade, 4th round p8

Tags: combinatorics, number theory



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$ е възможно това?