Olimpiadas de Matemáticas
Página de preparación y problemas
Competiciones
| OME Local |
| OME Andaluza |
| OME Nacional |
| OIM |
| IMO |
| EGMO |
| USAMO |
| ASU |
| OMCC |
| Retos UJA |
Buscar problemas
La base de datos contiene 2434 problemas y 940 soluciones.
Problema 581
Determinar todas las parejas de enteros positivos $(m,n)$ para los que es posible pintar de rojo algunas casillas de un tablero de $m$ filas y $n$ columnas de manera que todas las columnas tengan la misma cantidad de casillas rojas y no haya dos filas con la misma cantidad de casillas rojas.
pistasolución 1info
Pista. Distingue los casos $n\lt m$, $n=m$ y $n\gt m$. El principio del palomar puede ser útil para descartar directamente alguno de estos casos.
Solución. Vamos a pensar que $m$ está fijo, de forma que hay que decidir para qué valores de $n$ se puede conseguir la coloración que nos piden (en función de $m$). Vamos a demostrar que la respuesta es $n\geq m$ para todo $m$ y también $n=m$ cuando $m$ es par.
- Comenzamos observando que no puede ser $n\lt m$ ya que entonces hay $m$ filas y cada una tiene entre $0$ y $n-1\lt m-1$ filas coloreadas; por el principio del palomar, debería haber dos filas con el mismo número de casillas coloreadas.
- Consideremos ahora el caso $n=m$, en el que tenemos que el número de casillas coloreadas en las distintas filas debe ser $0,1,2,\ldots,m-1$ en algún orden, luego el número total de casillas coloreadas es $0+1+2+\ldots+(m-1)=\frac{(m-1)m}{2}$. Como cada columna tiene el mismo número de casillas coloreadas, este número debe ser $\frac{m-1}{2}$, que solo es entero si $m$ es impar. Deducimos así que la coloración es imposible si $n=m$ es impar. El caso par, por el contrario, si se puede colorear: podemos dejar la primera fila vacía, en la segunda pintar la casilla de más a la izquierda, en la tercera las $m-1$ casillas de más a la derecha, en la cuarta las dos casillas de más a la derecha, en la quinta las $m-2$ de más a la derecha, y así sucesivamente. En la figura superior vemos esta coloración para $(m,n)=(9,9)$.
- Vamos a ver ahora que en el caso $n\gt m$ la coloración siempre es posible. Si $m$ es impar, basta seguir la estrategia descrita en el párrafo anterior (la diferencia es el número de casillas pintadas en cada fila no recorrerá todos los valores entre $0$ y $m-1$). Si $m$ es par, entonces podemos hacer lo mismo eliminando la primera fila en la que no estaba pintada ninguna casilla. En la figura central vemos esta coloraciones para $(m,n)=(7,10)$ y en la inferior para $(m,n)=(6,10)$ a modo de ejemplo.
Si crees que el enunciado contiene un error o imprecisión o bien crees que la información sobre la procedencia del problema es incorrecta, puedes notificarlo usando los siguientes botones:
Informar de error en enunciado Informar de procedencia del problema
Informar de error en enunciado Informar de procedencia del problema
José Miguel Manzano © 2010-2025. Esta página ha sido creada mediante software libre