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
Problem
Source: Tuymaada 2017 Junior Level
Tags: combinatorics
27.09.2017 01:58
a few corrections [vertices are 2017 each and not 2015] Consider a graph with vertices $A_1$, $A_2$, \dots, $A_{2017}$, $B_1$, $B_2$, \dots, $B_{2017}$ and edges $A_iB_i$, $A_iA_{i+1}$, $B_iB_{i+17}$ (in cyclic numbering). Is it true that 4 cops can catch one robber on this graph for every initial position of cops and robber? (First all the cops make their moves, then robber makes his move, then again all the cops make their moves, etc.In a move, a person can stay in his/her vertex or jump to any of the neighboring vertices. Everybody knows about positions of all others. The cops can coordinate their moves. The robber is caught if after some move he shares his vertex with some cop). (T.Ball, R.Bell, J.Guzman, M.Hanson-Colvin, N.Schonsheck)
30.11.2017 22:20
First step. The cops separate, so there are 2 cops in A and 2 cops in B. Name the cops in A to be "Cops A1" and "Cops A2", and the cops in B to be "Cops B1" and "Cops B2". Case 1: This is the basic case, it is when the robber move in B. We plan to catch him with Cops B1 and Cops B2. The only thing we need to do is to move Cops B1 and Cops B2 in different direction (clockwise and anti-clockwise). Lets see how this thing works. We let the position in an n-th move is R(n) for the robber, X(n) for Cops B1, and Y(n) for Cops B2, all in mod 2017 and in graph B. When Cops B1 and Cops B2 move in different direction (which means Cops B1 move from X(n) to X(n)+17 (mod 2017) and Cops B2 move from Y(n) to Y(n)-17 (mod 2017) or the opposite), there will be a time when the distance of one (or both) of Cops in B is exactly 17 with the robber, thus if they keep following the path the other Cops in B will also have the distance of 17 or 34 with the robber, and so the robber's only move is to move away to graph A. The explanation of this concept is because of the sequence of multiple of 17 in mod 2017. Each of the 0*17, 1*17, 2*17, ..., 2016*17 stands a different number in mod 2017, because 17 is coprime with 2017, and thus their number in mod 2017 made a cyclically ascending sequence. Case 2: If the robber is in B but then he move to A, so Cops B1 and Cops B2 go to A and imitate his movement (this aims to keep the distance between Cops B1, Cops B2, and the robber to be the same) while Cops A1 and Cops A2 approach the robber from different side of graph A cyclically. Case 3: If the robber is in A but then move to B, so Cops B1 and Cops B2 go back to B, Cops A1 and A2 keep approaching his last position in A (this prevent the robber to move between A and B infinitely many), and wait the robber to make his move. Case 4: If the robber is staying, so if he is in graph A then do the same as Case 2. If the robber is in graph B then just do the same as Case 1. Thus the case is done. There is a guarantee for the glory of the cops at all cases. Sorry if I had bad grammar and by the way I also use this solution in the real Tuymaada 2017.