IMO Shortlist 2021 Problema C7
Considera un tablero cuadrado de $3m \times 3m$, donde $m$ es un entero mayor que $1$. Una rana se encuentra en la celda inferior izquierda $S$ y quiere llegar a la celda superior derecha $F$. La rana puede saltar desde cualquier celda a la siguiente celda a la derecha o a la siguiente celda hacia arriba. Algunas celdas pueden estar pegajosas, y la rana queda atrapada una vez que salta a una celda pegajosa. Un conjunto $X$ de celdas se llama bloqueante si la rana no puede llegar de $S$ a $F$ cuando todas las celdas de $X$ están pegajosas. Un conjunto bloqueante es mínimo si no contiene un conjunto bloqueante más pequeño. (a) Demuestra que existe un conjunto bloqueante mínimo que contiene al menos $3m^2 - 3m$ celdas. (b) Demuestra que cualquier conjunto bloqueante mínimo contiene como máximo $3m^2$ celdas.
11
0
Inicia sesión para agregar soluciones y pistas