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 509
OIM, 1994-P3
En cada casilla de un tablero $n\times n$ hay una lámpara. Al ser tocada una lámpara cambian de estado ella misma y todas las que están situadas en la misma fila o columna (las que están encendidas se apagan y las apagadas se encienden). Inicialmente todas están apagadas. Demostrar que siempre es posible, con una sucesión adecuada de toques, que todo el tablero quede encendido, y encontrar, en función de $n$, el mínimo número de toques para que se enciendan todas las lámparas.
Sin pistas
Sin soluciones
infoSolución. Si $n$ es impar, podemos tocar todas las lámparas de la primera fila (o de culquier fila o columna) y todas quedan encendidas. En este caso, $n$ es realmente el mínimo número de toques ya que, si sólo tocáramos $n-1$ lámparas o menos, entonces habría una fila y una columna en la que no tocaríamos ninguna lámpara. La casilla intersección de esta fila y columna quedaría apagada.
Si $n$ es par, entonces nuestro objetivo se cumplirá si tocamos las $n^2$ lámparas ya que a cada lámpara le afectan $2n-1$ cambios de estado (en realidad, esto también funciona para $n$ impar pero no es óptimo, como acabamos de ver). Veamos que, si no tocamos todas las lámparas, entonces habrá alguna que quede apagada, lo que probará que $n^2$ es óptimo en este caso (observemos que no tiene sentido tocar una misma lámpara dos veces).
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