Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

G
Topic
First Poster
Last Poster
cop vs robber in a maze
JGeneson   16
N Nov 21, 2017 by JGeneson
Let $R$ be a connected region in the plane. Suppose that the cop is a segment of length $x$ and the robber is a segment of length $y$.

The cop starts inside $R$ (so we assume that a segment of length $x$ fits somewhere inside $R$), as does the robber. Based on $R$, $x$, $y$, and the initial positions, does the cop catch the robber if both use optimal play?

A good place to start might be regions $R$ where all sides are parallel to the coordinate axes.

How does the result change if the cop and robber are circles or squares instead of segments?

What if the game is played inside connected regions in space?
16 replies
JGeneson
Aug 22, 2017
JGeneson
Nov 21, 2017
graph pursuit paper
JGeneson   0
Nov 1, 2017
The first paper from this CrowdMath project is now on arxiv: https://arxiv.org/abs/1710.11352

There are many more unsolved problems about graph pursuit algorithms and visibility graphs that you can still work on. See this page for a partial list of open problems.
0 replies
JGeneson
Nov 1, 2017
0 replies
No more topics!
a