Prueba de Selección de Equipos de Alemania 2022 Problema 3
3 Considere un tablero cuadriculado de $3m\times 3m$ , donde $m$ es un entero mayor que $1.$ Una rana se sienta en la celda de la esquina inferior izquierda $S$ y quiere llegar a la celda de la esquina superior derecha $F.$ La rana puede saltar de cualquier celda a la celda siguiente a la derecha o a la celda siguiente hacia arriba. Algunas celdas pueden ser pegajosas , y la rana queda atrapada una vez que salta a una de esas celdas. Un conjunto $X$ de celdas se denomina bloqueante si la rana no puede llegar a $F$ desde $S$ cuando todas las celdas de $X$ son pegajosas. Un conjunto bloqueante es minimal si no contiene un conjunto bloqueante más pequeño. Demuestre que existe un conjunto bloqueante minimal que contiene al menos $3m^2-3m$ celdas. Demuestre que todo conjunto bloqueante minimal contiene a lo sumo $3m^2$ celdas.
0
0
Inicia sesión para agregar soluciones y pistas