How Many Cops to Catch a Robber? | Infinite Series

How Many Cops to Catch a Robber? | Infinite Series


100 thoughts on “How Many Cops to Catch a Robber? | Infinite Series

  1. The left diagram has girth 5, and every vertex is connected to 3 others, so its cop# >= 3 by theorem stated earlier. Place 1 lazy cop at top, 2 more at bottom. The only possible starting places for the robber are the 2 arms of the pentagram. Top cop moves down to close off the robber's only exit (eg if robber started on right, cop moves left). Now that the robber is trapped, the best he can do is wait for the inevitable – the cop grabs him in 2 more turns. Since 3 >= lazy cop# >= cop# >= 3, both cop #s are 3.

    The right diagram has no pitfalls, so cop# >= 2. Place 2 lazy cops in opposite corners, and 1 in the middle. No matter where the robber starts, he will be caught on the 1st cop move. Alternatively, place 1 regular cop in top right, another in bottom left. Only possible starting place for robber is middle. Top cop moves left, bottom cop moves up. There is nothing the robber can do. Thus, 3 >= lazy cop# >= cop# = 2.

    If you think about it, the right diagram is equivalent to rooks on 3×3 chessboard — they can move arbitrarily far horizontally/vertically, but not diagonally. Note that no matter how you arrange 2 rooks, there will be at least 1 hole that they can't reach (at least 1 column they can't cover, at least 1 row they can't cover; intersection is this hole). With lazy cops (ie only 1 rook moves), I strongly suspect that this hole can't move diagonally, so the robber can stay in the hole indefinitely. Thus, I conjecture lazy cop# to be 3.

  2. Zugzwang. Always funny to find common german words in science. Zug = move, Zwang = Pressure. Unter Zugzwang setzen = force somebody to decide.

  3. What if the cops consistently fail to recognise the robber because he is rich and the function of the police is to protect his personal property?

  4. I was going to bring up the research team looking at this topic at my university but then they mentioned Professor Sullivan right at the end. Pretty cool.

  5. If a totally connected graph has uncountably many nodes can the cop win if they don't accept the axiom of choice?

  6. 5:01 Cops has no Timemachinse => 4D Doctor Wins… Troll
    6:18 in the infinite line it's infinite Cicles so the Rober Wins… Math… Troll
    8:11 I think intuitive NOT Calculated Pentagon 2/4 Square 2 / 3 Pleas correct me
    8:40 Zugzwang is a german word (and pronaunced vary wrong) and more importent for Mühle "Nine Men's Morris" then Chess

  7. Also in the last episode I immediatly thought of this board game: https://en.wikipedia.org/wiki/Scotland_Yard_(board_game). Anybody know it?

  8. I can prove that it needs a non-deterministic Turing Machine with polynomial bounded working memory to know if k cops can get the robber. Thus this is a R-class problem, not a RE-class. It might be easier than R, but I have no proof of it yet

  9. I never took a class in graph theory. Do planar graphs have to be finite? You can easily construct an infinite graph that is robber win for any number of cops. You make it like a fractal, where you start with a single cycle. Then for each point on the first cycle, they all branch out into disjoint cycles. The pattern continues, and for any number of cops, the robber just has to pick a cycle far enough down so that the cops can never reach him.

  10. Are we going to do higher dimensional cops and robbers; It seems almost kinda mandatory at this point; But I can already tell it will be pretty similar, or well actually you could just flatten the skeleton of the 3D shape onto a 2D plane… thus any dimension; Just keep flatting it until it's 2D.
    Nevermind.

  11. I think an interesting variant to explore would be where any of the cops could arbitrarily be misaligned with the other cops. That is, how many cops n are required for a graph to guarantee that any of the distinct n are able to catch the robber. I would presume under this variant, a misaligned cop would be unknown and would behave optimally for a true cop but would not move to capture a robber on an adjacent vertex. Of course, then this may inform the robber and other cops which cop/s is/are misaligned, which could change their strategy in the middle of the pursuit… Thinking of trying to solve this mathematically seems complicated lol

  12. @6:30 Hey! If the robber chooses "the infinite" branch, it will take him infinite turns to get caught, in other words that would be never/undefined/etc… or am I missing something?

  13. The Robber knows where he is at all times. He knows this because he knows where he isn't. By subtracting where he is from where he isn't or where he isn't from where he is, whichever is greater, he obtains a difference, or deviation…

  14. On the infinity tree, it does not matter where the cop start, the cop will win, being at the base is only for the quickest capture no matter where the robber begins.

  15. Another variant. Suppose we replace the cop with a mad bomber. The bomber wants to blow up an arbitrary point on a graph. However, the bomber must remain on the point for at least n turns to succeed. The bomber will win if there exists a move that will allow him to do this. The cops will win if either they capture the bomber our can prevent the bomber for an arbitrarily long time from setting the bomb.

  16. About an infinity tree graph: What if the robber chose last branch. Isn't that branch infinitely long? Doesn't it take infinitely many time to a cop to catch a robber? Will immortal cop EVER catch robber?

  17. A colleague of mine did her thesis on cops and robbers on infinite graphs. It's a bit technical, but interesting. She deals with things like how hard it is for the robber to find a winning strategy in a cop win graph. The definition she uses is that if the robber can evade capture forever, he wins. http://opencommons.uconn.edu/dissertations/1463/

  18. Can we define a doomsday clock for the robber in infinite graphs (similar to that mentioned in the infinite chess video) and if yes, are there graphs with a doomsday clock of omega^2 or higher?

  19. If the branch is infinitely long, then how could it be Cop Number 1? The robber would always be 1 step ahead. It's like the cycle one right?

  20. Another variant it to have edges which can only be traversed by either cops or robbers. Or a variant where you cannot immediately move back on an edge. Or where n cops may make m moves among them on their turn (if m == 1, we have lazy cops). You can also have variants where you have more than 1 robber, and all robbers must be captured at the same time.

  21. Very nice video. In the imperfect information version, I think there could be several definitions of the cop number but if we define it as the number of cops needed to win with probability 1 eventually, I think I can show that it is never larger than the usual cop number. Basically, if the cops have a winning strategy for the perfect information game, I think they can win the imperfect information game as well by guessing what the robber does. If they guess right they should win within the same time it takes in the perfect information game. If they don't win within that number of moves they just start again by guessing where the robber is and what he is doing. Repeating this enough times they should eventually guess correctly for long enough to catch the robber.

    In fact the above reasoning suggest that you might as well only keep the robber ignorant, and let the cops have perfect information, unless you impose a bound on the number of moves before you declare the game ended with a robber win if he is still on the run.

    I end this comment by noting that cycles still have cop number greater than 1. With just one cop, the robber remains still until they see a cop when he moves away. Clearly the cop will never win this game.

  22. I can think of several more variations of the game: In the imperfect information version you could force each cop to move independently because they can't share information.

    In the original version you could designate a hide-out vertex and the robber wins if he reaches that vertex when a police is not there. The cop number in this version is a most 1 more than in the normal version since a cop could just be stationed at the hide-out but in some graphs it won't increase at all.

    Finally there is American Cops and Robbers, where the police just shoot the robber instead of chasing him.

  23. Seems like an interesting variant would be to give the Graphtopia PD a limited budget such that the cop could only play for n moves – then a question would be for a given cop win graph is there a strategy for the robber to outlast the cop (complicated I guess because it would depend on starting positions…)

  24. i'm going to give you a problem, solve it if you can ,if p(n)=nth prime, then prove that for arbitrary large n , p(n+2)-p(n)>=6, this means that for arbitrary large n p(n+2)-p(n) can't be less than 6, p(n+3)-p(n)>=8, p(n+4)-p(n)>=12 ,.. and so on , i can prove that

  25. Hey, speaking of tree… it's a little Numberphile-y, but is there any chance you could do a video on Tree 3? Nobody else is touching it, and I haven't found anything lay enough to get even the foggiest notion.

  26. The infinite graph thing is wrong.
    The thing is, the assumption is always that they are using the optimal strategy.
    The robber does not have an optimal strategy, since whatever decision he makes, there are infinite others that could have given him a longer time before being cought.

  27. You still did not explain where there is information not known by both but that can be discovered by the other one

  28. This is basically an explanation of the mechanics behind the board game "Scotland Yard." Fun game, but it can be SUPER HARD!

  29. Hi, one question, in the case of a infinite branched tree would it have one branch with infinite nodes and in this case the robber would be chased infinitely but just in this branch ?

  30. Here's a realistic variant: Both cop and robber have stamina with a maximum of n, and when they don't move, they recover it fully. When their current stamina is 0, they must stop to recover stamina to their max.

  31. I've heard of a hypercube; now I think I know what one is. Perhaps you could do an entire video on hypercubes — if they're sufficiently interesting or useful.

  32. What about a Cop with a roadblock? How many roadblocks would a Cop need to win?
    Cops can place a roadblock on an adjacent path instead of moving.

  33. Seems like the graph theory used here could be applied to search and sorting algorithms to shorten computation times. Can you suggest any further reading? (Preferably for the not good at reading set theoretic notation and has lots of pictures and analogies). Thanks!

  34. 6:32 Why does he have to start on one of the finite branches? There's no rule about it. Can't he start on the infinityth point on the infinityth branch branches, and never get caught?

  35. couldn't the robber start at the second node of the branch of length ω and survive for ω turns and die of natural causes ω-robber lifetime turns before getting caught

  36. Here's my version with 4 NEW rules:
    Rule #1:
    For a graph with a positive number of vertices, the number of numbers (x) in a game cane be:
    0 <= x <= v – 2 <= 9
    for a graph with 11 vertices or less
    where "v" is the number of vertices

    Rule #2:
    If any non-number player lands on a vertex already occupied by a number, that number and ONLY that number is out,
    The game is called "reduced" if all the numbers are out.

    Rule #3:
    There can only be three numbers or less if the graph is infinite.

    Rule #4:
    The numbers in the game are consecutive and positive numbers.

  37. 2:00 – That one lone node on our left is known as 'the hideout'. No cop ever thinks of looking there.

Leave a Reply

Your email address will not be published. Required fields are marked *