Olimpiada Tuymaada Junior 2017 Problema 8

Consideramos el grafo con vértices $A_1,A_2,\dots A_{2015}$, $B_1,B_2,\dots B_{2015}$ y aristas $A_iA _{i+1}, A_iB_i, B_iB_{i+17}$, tomados cíclicamente. ¿Es cierto que 4 policías pueden atrapar a un ladrón en este grafo para cada posición inicial? (Primero los 4 policías hacen un movimiento, luego el ladrón hace un movimiento, luego los policías hacen un movimiento, etc. Un movimiento consiste en saltar desde el vértice en el que te quedas a un vértice adyacente o quedarte en tu vértice actual. Todos conocen la posición de todos en todo momento. Los policías pueden coordinar sus movimientos. El ladrón es atrapado cuando comparte el mismo vértice con un policía.)

23

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados