Nacional 1994 Nivel 1 (P3)

[Dauphineg]

Con $40$ fósforos se forma una figura que es un cuadrado de lado $4$ dividido en $16$ cuadrados de lado $1$, donde cada fósforo está puesto sobre un lado de un cuadrado de lado $1$.
La figura tiene $16$ cuadrados de $1\times 1$, $9$ cuadrados de $2\times 2$, $4$ cuadrados de $3\times 3$ y $1$ cuadrado de $4\times 4$.
Determinar el mínimo número de fósforos que hay que quitar para que la figura resultante no tenga ningún cuadrado de ningún tamaño.

[Gabriel Bernal]

Spoiler: mostrar

Como hay $16$ cuadrados de $1\times 1$ y un fósforo está en a lo sumo $2$ cuadrados de $1\times 1$, se deben sacar sí o sí $8$ fósforos. Además, si se sacan sólo $8$, el cuadrado de $4\times 4$ seguirá estando, ya que los bordes del cuadrado de $4\times 4$ son fósforos que están en sólo un cuadrado de $1\times 1$. Por ende debo sacar al menos $9$. Ejemplo de que se puede hacer así es:

Fósforos.PNG