Problema 10 · Targetes en caixes sense múltiples
Una cadena $2 \mid 4 \mid 8 \mid 16$ obliga; quatre caixes basten.
Resposta entera de 4 xifres com a màximEn Ramon té 20 targetes numerades del 2 al 21 i les vol col·locar en diferents caixes de manera que, si el nombre d'una targeta és múltiple del nombre d'una altra targeta, aquestes dues han d'anar a caixes diferents. Quina és la quantitat mínima de caixes que ha de tenir per tal que això sigui possible?
Solució raonada
Idea clau: les targetes $2, 4, 8, 16$ són múltiples successives les unes de les altres: cada parella d'aquestes quatre ha d'anar separada → calen com a mínim $4$ caixes.
I quatre caixes basten. La clau: si $a < b$ són a la mateixa caixa i $b$ és múltiple d'$a$, aleshores $b \ge 2a$. Agrupem per «zones» on això no pot passar:
Dins de cada caixa, el més gran és menys del doble del més petit ($5 < 2\cdot 3$, $10 < 2 \cdot 6$, $21 < 2 \cdot 11$), així que cap targeta pot ser múltiple d'una altra de la mateixa caixa.