MathDB
Problems
Contests
International Contests
Baltic Way
2019 Baltic Way
8
8
Part of
2019 Baltic Way
Problems
(1)
62 cops chase a visible robber on a graph with 2019 vertices
Source: 2019 Baltic Way P8
11/18/2019
There are
2019
2019
2019
cities in the country of Balticwayland. Some pairs of cities are connected by non-intersecting bidirectional roads, each road connecting exactly 2 cities. It is known that for every pair of cities
A
A
A
and
B
B
B
it is possible to drive from
A
A
A
to
B
B
B
using at most
2
2
2
roads. There are
62
62
62
cops trying to catch a robber. The cops and robber all know each others’ locations at all times. Each night, the robber can choose to stay in her current city or move to a neighbouring city via a direct road. Each day, each cop has the same choice of staying or moving, and they coordinate their actions. The robber is caught if she is in the same city as a cop at any time. Prove that the cops can always catch the robber
combinatorics