Olympiad Maths Prep

Track / Stage 6 / 291 of 400 #1291 of 2000

Problem 1291

National olympiad, first round
Number theory Difficulty 6.5 Prove it Nacional OMA · Argentina

Ignacio tiene una hoja de papel. La puede cortar en 6 pedazos o en 8 pedazos, a su elección. Luego, en cada etapa, puede elegir uno de los pedazos existentes y cortarlo en 6 pedazos o cortarlo en 8 pedazos.

a) Decidir si de esta manera Ignacio puede tener, después de alguna etapa, exactamente 24 pedazos de papel.

b) Decidir, si de esta manera Ignacio puede tener, después de alguna etapa, exactamente 32 pedazos de papel.

Si la respuesta es no, explicar por qué y si es sí, indicar cómo debe realizar los cortes.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Comenzamos con una hoja y en cada paso agregamos 55 o 77 trozos. Luego queremos que
a)1+5n+7m=245n+7m=23. Notemos que n4 y m3. a) 1+5n+7m=24 \leftrightarrow 5n+7m=23. \text{ Notemos que } n \le 4 \text{ y } m \le 3.
Consideramos la igualdad módulo 77 y tenemos 5n232 (mod 7)5n \equiv 23 \equiv 2 \ (\text{mod } 7), pero ninguno de los posibles valores de nn (00, 11, 22, 33 y 44) satisface la condición, por lo tanto no es posible.
b)1+5n+7m=325n+7m=31, luego n6 y m4. b) 1+5n+7m=32 \leftrightarrow 5n+7m=31, \text{ luego } n \le 6 \text{ y } m \le 4.
Como en el caso anterior, obtenemos 5n313 (mod 7)5n \equiv 31 \equiv 3 \ (\text{mod } 7). En este caso las soluciones son de la forma n=7k+2n=7k+2, con k=0,1,2,3,4,5k=0, 1, 2, 3, 4, 5 y 66. Resulta entonces que k=0k=0 y m=3m=3, luego 1+52+73=321+5 \cdot 2+7 \cdot 3=32. Es posible obtener 3232 trozos cortando en 66 trozos dos veces y en 88 trozos 33 veces.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.