Problem

Source: Tuymaada 2017 Junior Level

Tags: combinatorics



We consider the graph with vertices $A_1,A_2,\dots A_{2015}$ , $B_1,B_2,\dots B_{2015}$ and edges $A_iA _{i+1}, A_iB_i, B_iB_{i+17} $, taken cyclicaly. Is it true that 4 cops can catch a robber on this graph for every initial position?( First the 4 cops make a move, then the robber makes a move, then the cops make a move etc. A move consists of jumping from the vertex you stay on an adiacent vertex or by staying on your current vertex. Everyone knows the position of everyone everytime. The cops can coordinate their moves. The robber is caught when he shares the same vertex with a cop.) Tuymaada 2017 Q8 Juniors