1) Supongamos que cada par de fila-columna contenía 4 centavos. Suma el número de centavos en cada par de fila-columna a través de todos los pares de fila-columna. Esto da $4\cdot 36$ centavos. Sin embargo, hemos contado cada centavo varias veces, específicamente $12$ veces (una vez por cada fila y una vez por cada columna). Dividiendo por $12$ obtenemos $12$ centavos en el tablero. Por lo tanto, cualquier disposición con $4$ o menos centavos en cada par de fila-columna no puede tener más de $12$ centavos, ya que agregar un centavo más en cualquier cuadrado romperá la regla.
Como se señala en los comentarios, este mismo argumento puede usarse para mostrar que 5 centavos en cada par de fila-columna no funciona (se encuentran 15 centavos), y por lo tanto, de hecho cualquier disposición requiere al menos 6 centavos en algún par de fila-columna.
2) Generalmente, los enfoques "codiciosos" (donde construyes la respuesta de manera iterativa haciendo la mejor elección en cada paso) funcionan para problemas como este. Si trabajas fila por fila llenando cada fila con 3 centavos de una manera que haga que ninguna columna tenga más de 3 centavos, prácticamente todas las disposiciones posibles funcionan. Por ejemplo, tanto el enfoque de dos bloques de nueve como el enfoque de desplazar la fila por uno funcionan. Notarás que ambos enfoques producen 6 centavos en cada par de fila-columna. Postulo que este es necesariamente el caso, y que 19 centavos requiere al menos 7 en algún par de fila-columna.
