| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
[This is presented as a game whose rules are peculiar, but the result is
a mathematical beauty. It appeared in print (Scientific American?) some
years ago, and has a common theme with Note #542. If anyone can find the
original and help me with the description, I would certainly appreciate
it.]
Two cars (the cops' car and the robbers' car) are moving in a city that's
laid out in a grid. The cops are trying to catch the robbers, and the robbers
are trying not to be caught.
The robbers' car is slower than the cops' car, but the cops obey the city's
traffic rules: left turns and U-turns are prohibited.
The rules are:
* The robbers can move one intersection in any direction (ahead,
left, U-turn, or right) when it's their turn.
* The cops can (i) go ahead two intersections, or (ii) turn right
and then go two intersections when it's their turn.
* If the cops ever get within one block (including diagonally)
of the robbers, the cops catch the robbers and win.
* If the robbers can stay uncaught for a long time (say 10000 turns),
they win.
* The cops move first; then moves alternate.
Example:
^
x C x x x x x
^
x x x x x x x
x x x x x R x
x x x x x x x
x x x x x x x
Cops move:
x x x > C > x x x
x x x x x x x
x x x x x R x
x x x x x x x
x x x x x x x
Robbers move:
x x x > C > x x x
x x x x x x x
x x x x x x x
x x x x x R x
x x x x x x x
Cops move:
x x x x x > C > x
x x x x x x x
x x x x x x x
x x x x x R x
x x x x x x x
Robbers move:
x x x x x > C > x
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x R x
Cops move:
x x x x x x x
x x x x x x x
v
x x x x x C x
v
x x x x x x x
x x x x x R x
Robbers move:
x x x x x x x
x x x x x x x
v
x x x x x C x
v
x x x x x x x
x x x x R x x
Cops move and catch robbers:
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x
v
x x x x R C x
v
QUESTION: Are there any initial positions that allow the robbers to get
away? And if so, what are they?
John
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 550.1 | The roots... | MODEL::YARBROUGH | Fri Aug 01 1986 12:50 | 12 | |
This game was, I believe, invented by Rufus Isaacs, who wrote a
book entitled "Differential Games". He used it as an example in
a course he taught (I was a student) at UCLA in the late '50's,
and it appears in the book. (By the way, I have mentioned this before
in the note on the Cat-and-mouse game.) The book appears to be out
of print but there is a copy in the MIT Lincoln Lab Library. Probably
also in the Widener Library at Harvard.
This game is a discrete example of a class of games that Isaacs
calls Pursuit Games. The solution(s) to the continuous class of
such games involves the solutions of a set of O. D. E.'s that Isaacs
spells out in his book. The theory is of great value in Air Warfare.
| |||||
| 550.2 | try one | GALLO::JMUNZER | Tue Aug 19 1986 13:31 | 17 | |
Who wins in this starting position?
x x x x x x x x x
x x x x x x x x x
^
x C x x x x x R x
^
x x x x x x x x x
x x x x x x x x x
(Assume infinitely many intersections in all directions.)
John
| |||||
| 550.4 | robbers escape mostly | HERON::BUCHANAN | procrastinated laziness | Wed Apr 13 1988 12:05 | 57 |
> Who wins in this starting position?
>
>
> x x x x x x x x x
>
> x x x x x x x x x
> ^
> x C x x x x x R x
> ^
> x x x x x x x x x
>
> x x x x x x x x x
>
>
> (Assume infinitely many intersections in all directions.)
The robbers win, as they do for almost all starting positions.
The following map shows the positions for which the cops *do* win. The cops
are at the origin, C, facing North. A number in a square indicates the number
of cop moves it takes to win. I have made the perhaps pedantic assumption
that if at the start of the game, with the cops to move, the robbers are on or
adjacent to the cops, they are *not* immediately caught. Reversing that
assumption makes no difference to the map except to the numbers in the 3x3
square around C, which would all be 0.
T = 10, E = 11, C = 8
. . . | . . . . . . . .
. . . | 8 E . . . . . .
. . . | 5 8 . . . . . .
. . . 3 4 7 T . . . . .
. . . 2 3 4 7 . . . . .
. . 1 1 1 3 6 9 . . . .
. . 1 1 1 2 3 6 . . . .
. . 1 1 1 1 1 5 8 . . .
- - E C 1 1 1 2 3 - - - ^
. 9 8 5 1 1 1 3 4 5 8 . |N
. . 7 4 3 2 3 4 7 8 E . |
. . T 7 4 3 6 7 T . . .
. . . 8 5 6 9 . . . . .
. . . E 8 . . . . . . .
. . . | . . . . . . . .
*
What goes against my intuition on this one is that there's no problem
getting near to the robbers, even if they're a zillion cells away, in whatever
direction they are, because the cops can go much faster. It's the putting (in
the golfing sense) that presents the problem, with the robbers just being
nimble enough to avoid capture, as they orbit round the zone marked out above,
always being able to stay clear of it.
| |||||
| 550.5 | 70 < infinity | VINO::JMUNZER | Thu Apr 14 1988 13:24 | 8 | |
Andrew:
Nicely done. It's always a shock when a pattern starts to move
out into the plane (or whatever space) and then stalls. Now could
we get some little cops and robbers to whiz around Lynn's floor
(542.*)?
John
| |||||