Deshaw Inc Interview Question Analysts
but you have not thought about putting the robber. You cannt fit the robber here as there is no location(edge) "inside" this square.
I think so too. The cops may never be able to catch the robber, as a long as the robber always makes the right move.
The reason, I think, is because of the 3-dimensionality. At the start, all that the robber has to do is to sit and wait at a vertex. As the 2 cops approach 2 of the adjacent corners, the robber should run in the direction of the 3rd edge. There on it shouldn't be aproblem to keep avoiding the cops.
That's a dumb strategy for the cops.
A------B
|\ /|
| E--F |
| | | |
| G--H |
|/ \|
C------D
Suppose for the moment that the robber is at A and the cops are at D, not H. Working alone Cop #1 can confine the robber to A, E, and the interiors of their incident edges by moving in direction (-dx,-dy,dz) when the robber moves in direction (dx,dy,dz). Since the robber is confined to a tree, Cop #2 easily catches him (this is a topological thing: Cop #2 still wins even if he's been eating donuts and is much, much slower than the robber).
Now, in the actual problem, the cops start at H. Cop #1 should stay at H and Cop #2 should chase the robber. If the robber ever arrives at B, C, or E, Cop #1 begins the previous strategy and is caught. Therefore, the robber is in effect confined to A and its incident edges, which form a tree, so Cop #2 can once again catch him if he does not make a move.
tl;dr: Cops win, even if one of them has been eating donuts and runs arbitrarily slowly.
D'oh, that's not the right direction for Cop #1.
A---B
| |
| |
C---D
Put A at (0,0,z) and D at (1,1,z). Cop #1 should move in direction (-dy,-dx,dz).
Really??? you mean to say one can catch the robber....I don't think so robber will always have three direction to go to. As every one can see the move of every other one, there is no way two cops can catch the robber....... What ever strategy you apply...cops can never catch the robber.
It is not possible to catch him for the specific reason.
Each Edge has 3 different paths
Cops can only block 2 paths
There is a possibility that the cops are never able to catch the thief.
Even if the cops are at the 2 opposite of the cube, thus for sure having 1 cops next to the thief, he would need to move on the thief position.
While he does that move, he walk using 1 path, the thief have 2 paths open to escape during that move...
Knowing that there is 3 paths all the time, it is impossible to catch him.
Unless you claim the movement aren't simultaneous but a turn by turn approach, then you can catch him easily, just get the 2 cops at the 2 opposite point of the cube and you catch him in 1 turn. But it shouldn't be like that from the way the question was initially stated.
A---------B
| \ / |
| E----F |
| | | |
| G----H |
| / \ |
C---------D
If initially 1st cop is at E, 2nd cop at H and the robber at C, the robber will definately be caught by any 1 of the cops.
Explntn:
If the robber runs toward A, 1st cop will also run towards A.
If the robber runs toward D, 2nd cop will also run towards D.
If the robber runs toward G, both the cops (or any 1) will run towards G.
If the robber changes the direction mid way and runs in the oppst dirctn, the cops also will go back.
- Ashutosh April 13, 2010