Timeline for Can the fugitive escape?
Current License: CC BY-SA 4.0
62 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 16, 2021 at 7:27 | answer | added | jcdornano | timeline score: 1 | |
| Apr 25, 2021 at 14:47 | comment | added | jcdornano | Let's say F is p-winning if he's able to anounce the integer $p$ before the game began, and he's aloud to decrease the value of the maximum distance of move at most $p$ time. I'm convinced that it is always possible for the fugitive to $p$-win for some $p$. And I think it may not be to hard to deduce from this a 1- winning strattegy. I posted an answer "by mistake" this morning, because I was on my phone and I miss clicked, I will post it if I can prove the general game, not only the $p$-winning idea that was my first aim (but now I've got ideas to go futher, so I wait a bit before posing) | |
| Apr 24, 2021 at 3:54 | comment | added | Timothy Chow | @Eric The book I mentioned, Graph Searching Games and Probabilistic Methods by Bonato and Prałat, has a whole chapter devoted to cops and robbers, and many other chapters devoted to related games. | |
| Apr 24, 2021 at 2:58 | comment | added | Eric | @TimothyChow Yes, thanks for the link. I found there's a whole genre of well researched games called (infinite) cops and robbers that are isomorphic to the chess version of my game. | |
| Apr 23, 2021 at 23:49 | comment | added | jcdornano | If $C_0$ is the edge of the convex hull of the st $O$ of officers then let's call $C_1$ the edge of the convexe hull of $O- C_{0}$ and repete the process. Then $O$ is the nested union of convex polygons. It may be a good strattegy for F to escape one polygon at a time, as soon as of it stay convexe it is an easy case , the difficulty can come if there is a break of the convexeity, but I feel that it does not seem too problematic. | |
| Apr 23, 2021 at 0:28 | comment | added | Timothy Chow | I just found another MO question that seems very similar. Also there is a book Graph Searching Games and Probabilistic Methods by Bonato and Prałat that seems potentially relevant. | |
| Apr 22, 2021 at 17:08 | comment | added | jcdornano | I'm pretty sure this idea is a good begin... the strattegy for the fugitive would be "in some sens" to go where he will fell less "tension". The tension would be mesured by the repulsion forces and should increse with the intensity of the "total repulsion" (sum of ponctual repulsion) but also with the unstability of the neighbourhoud , so that although the addition of repulsion forces is zéro in an unstable equilibrium, the " tension " should be non zéro. A fine "tension" might be "something like" the average of the modules of repultion forces in a small circle around the fugitive. | |
| Apr 22, 2021 at 16:19 | comment | added | Eric | @jcdornano No, I don't think it works like that. | |
| Apr 22, 2021 at 13:47 | comment | added | jcdornano | Of course If the fugitive is in an unstable equilibrium he can get caught if he follows this strattegy (officer can maintain him not moving!) so let's say that in this case only he will have to move infinitesimally to take a decision. The question if yes or no this strattegy works can be asked... (the way he moves if he is in equilibrium has to be fixed... but maybe, the strattegy is working for any arbitrary move to escape equilibrium...) | |
| Apr 22, 2021 at 13:21 | comment | added | jcdornano | Imagine officer and fugitive are charged particules, all the same sign and intensity. Then what would give the strattegy for the fugitive to move according to his natural motion over repulsion forces? (I had this idea by trying to ponderate each officer according to a fonction of the inverse of its distance to fugitive and rake the barycentral point) i did not investigate, it is just a quick idea^^ | |
| Apr 21, 2021 at 18:35 | comment | added | jcdornano | When I say "Is it équivalent to the problem with continuous (ans Lipzichian) and simultaneouss moves that satisfy the correct conditions for speed (condition on the sum of the norm of speeds)?" I mean instead of dictating $\delta$, the fugitive dictate a neighbourhood around him that if a ploceman gets inside, policemen win | |
| Apr 21, 2021 at 14:58 | comment | added | Eric | @mlk You're right. | |
| Apr 21, 2021 at 11:59 | comment | added | mlk | @Eric No, the direction is the same as the fugitive for all officers "behind" (wrt. to the direction he's moving) the fugitive. For all that are in front of the fugitive (and there is always at least one if the convex hull condition is met) the line each is moving on and the line the fugitive is moving on form the sides of an isosceles triangle, independent of $\delta$. Thus in particular they will meet if they continue in the same direction. | |
| Apr 21, 2021 at 11:32 | comment | added | jcdornano | Is it équivalent to the problem with continuous (ans Lipzichian) and simultaneouss moves that satisfy the correct conditions for speed (condition on the sum of the norm of speeds)? | |
| Apr 21, 2021 at 8:20 | comment | added | Eric | @mlk Yes but when $\delta$ is very small, this doesn't matter much, and they're the same in the limit, right? The fugitive escapes the equilateral triangle in my previous comment, if $\delta$ is sufficiently small. | |
| Apr 21, 2021 at 8:00 | comment | added | mlk | @Eric Maybe you are misunderstanding the proof. They aren't moving straight towards the fugitive, but try to keep the same heading first and only then spend any excess mobility in moving towards the fugitive. If the fugitive always moves in the same direction, this will result in straight lines for the officers as well, not pursuit curves. | |
| Apr 20, 2021 at 3:03 | history | edited | Eric |
edited tags
|
|
| Apr 20, 2021 at 2:24 | history | edited | Eric | CC BY-SA 4.0 |
deleted 126 characters in body
|
| Apr 19, 2021 at 15:09 | answer | added | Pace Nielsen | timeline score: 14 | |
| Apr 19, 2021 at 9:04 | comment | added | Eric | @mlk I think the "if" part of your proof is seriously flawed. For example, if the fugitive is close to the boundary of the hull, your method won't work. Even if the fugitive starts at the center of the hull, there's no guarantee. Let's say $\delta$ is very small, then officers are in fact tracing a pursuit curve (en.wikipedia.org/wiki/Pursuit_curve). For 3 officers on the vertices of an equilateral triangle, the fugitive escapes by walking along the normal to the line connecting 2 officers. For more officers, their movements can probably be manipulated to create a gap, too. | |
| Apr 18, 2021 at 4:04 | comment | added | Eric | @WillBrian If officers could move any tiny bit more, you only need one officer to catch the fugitive, without any fancy formations. | |
| Apr 17, 2021 at 20:25 | comment | added | Pace Nielsen | In the power-one rook version, if two officer rooks can move per turn, then 4 officers can always capture the fugitive. | |
| Apr 17, 2021 at 18:17 | comment | added | Will Brian | @usul: OK, I finally see what you mean -- thanks for the picture -- and I think you're right. The strategy I outlined won't quite work. Still, it seems like a near miss. It seems like it would work if the officers could move just a tiny bit more on every turn. Which I suppose just makes the question, as phrased, all the more interesting. | |
| Apr 17, 2021 at 17:22 | comment | added | Alessandro Della Corte | You wrote: "For that purpose you can also replace the kings with power-one rooks (which can move only one square in four cardinal directions)." In fact the king version and the short-legged rook version are not the same, and neither looks trivial. | |
| Apr 17, 2021 at 17:06 | history | edited | Eric | CC BY-SA 4.0 |
added 6 characters in body
|
| Apr 17, 2021 at 16:45 | history | edited | Eric | CC BY-SA 4.0 |
deleted 156 characters in body
|
| Apr 17, 2021 at 2:36 | comment | added | Eric | @WillBrian The point is the fugitive can turn either left or right. This illustration should make the point clear: puzzling.stackexchange.com/a/12690/68538 | |
| Apr 15, 2021 at 21:30 | comment | added | usul | @WillBrian let us (and others!) continue in chat, try here: chat.stackexchange.com/rooms/123038/fugitive-game | |
| Apr 15, 2021 at 21:23 | comment | added | Will Brian | @usul: The way I'm imagining it, X is moving closer to the point Z as F moves towards the circle containing the officers. This should prevent the angle XFZ from ever getting too close to $\pi/2$. | |
| Apr 15, 2021 at 19:02 | comment | added | usul | Correction: angle FXZ stays at about $\tfrac{\pi}{2} - \tfrac{\pi}{N}$ (I think), while XFZ grows toward $\tfrac{\pi}{2} + \tfrac{\pi}{N}$. Apologies. | |
| Apr 15, 2021 at 18:03 | comment | added | usul | @WillBrian I think the fugitive F can escape: walk directly at some officer X until you are very close, then turn aside and walk out of the convex hull. Some details: As the fugitive walks, the adjacent officer Y on, say, the left, stays relatively far away. Let Z be the midpoint between X and Y. The angle FXZ stays at about $\pi/N$. But the angle XFZ is growing toward $\pi/2 - \pi/N$. Once the fugitive is close enough that the angle XFZ is greater than FXZ, the fugitive simply turns toward Z and leaves. He is closer to Z than any of the officers. | |
| Apr 15, 2021 at 16:42 | comment | added | Will Brian | @Eric: 3. I'm thinking of $\delta$ as being small relative to $1/N$ (something like $1/10N$ or smaller). 1-2. Maybe $2/N$ is too small -- let's change that to $10/N$. Let's say the fugitive is approaching the ring of officers for the first time, so they're spaced evenly along the circle at intervals of $< 2\pi/N$. The fugitive moves to within $10/N$ of the officers, and the closest officer makes a line with the fugitive that's not too far off from normal to the circle (certainly $< \pi/4$). The officer just needs to move in a way that maintains or tightens this angle, and this prevents escape. | |
| Apr 15, 2021 at 14:45 | comment | added | Eric | @WillBrian I don't quite follow this strategy. 1. Why N/2? 2. If $\delta$ is really small, how can the officer match the fugitive's motion, since they will be many moves away to the fugitive's left or right side? 3. How can a small error prevent the fugitive from escaping out of the circle? Are you assuming fixed $\delta$, instead of thinking of it as a function of $N$? | |
| Apr 15, 2021 at 13:43 | comment | added | mlk | @Eric Allowing 2 to move will at least require a different strategy, since their convex hull has no interior. 2 on their own will always loose. Even starting on their connecting line, the fugitive can run perpendicular to it and the best they can do is catch up without getting closer. So you'd somehow need to involve a third stationary policeman as well. This way, they can always keep the fugitive inside their convex hull, but getting it to shrink might be hard. | |
| Apr 15, 2021 at 13:03 | comment | added | Eric | @mlk You can settle for a weaker "if" by just allowing 3 officers to move by $\delta$ each turn, because if the fugitive is in a convex hull, they're in a triangle too. I really wonder if allowing 2 officers to move is enough. (of course, if one officer is enough, the original result is proved) | |
| Apr 15, 2021 at 12:57 | comment | added | Will Brian | If the fugitive is within $2/N$ of the circle containing the officers, then only one officer moves: the officer closest to the fugitive remains on the circle containing all the other officers, and otherwise moves to match the fugitive's motion up to some small error $\eta < \delta$ (i.e., the fugitive, officer, and origin should remain approximately colinear). The small error does not allow the fugitive to escape, but it does allow some leftover motion for the officers on each turn where the fugitive is near the edge. They use this leftover bit to shrink their circle slightly. | |
| Apr 15, 2021 at 12:54 | comment | added | Will Brian | Here's a strategy for the officers that I think should ensure they capture the fugitive when $N$ is big and $\delta$ is small, although I have not proved that it works. Place the $N$ officers evenly around the unit circle. Throughout the chase, the officers always remain on a circle centered at the origin, though this circle may (and should) shrink as time goes on. If the fugitive is at least $2/N$ from the circle containing the officers, then all officers move toward the origin by $\delta/N$. (continued) | |
| Apr 15, 2021 at 9:24 | history | edited | Eric | CC BY-SA 4.0 |
typo rook
|
| Apr 15, 2021 at 5:29 | history | edited | Eric | CC BY-SA 4.0 |
discrete roots
|
| Apr 14, 2021 at 16:16 | history | edited | Eric | CC BY-SA 4.0 |
added 7 characters in body
|
| Apr 14, 2021 at 15:21 | history | edited | Eric | CC BY-SA 4.0 |
edited title; added 10 characters in body
|
| Apr 14, 2021 at 15:14 | history | edited | Eric | CC BY-SA 4.0 |
edited title
|
| Apr 14, 2021 at 15:07 | history | edited | Eric | CC BY-SA 4.0 |
added 5 characters in body
|
| Apr 14, 2021 at 14:59 | history | edited | Eric | CC BY-SA 4.0 |
deleted 4 characters in body
|
| Apr 14, 2021 at 14:51 | history | edited | Eric | CC BY-SA 4.0 |
expand the post to add discrete version
|
| Apr 14, 2021 at 7:43 | history | edited | Eric | CC BY-SA 4.0 |
stylized description to avoid ambiguity
|
| Apr 12, 2021 at 16:30 | comment | added | mlk | Absolute in the sense of compass direction. Draw a line through a policeman and the previous position of the fugitive. Now that policeman moves to the point on the parallel line through the new position of the fugitive that is reachable and closest to that new position, thus ending up in the same direction. If all of them do that, none of them will be further away, but at least one of them will be closer by an amount that can be bounded from below depending on the directions. | |
| Apr 12, 2021 at 16:13 | comment | added | Eric | @mik Can you explain what it means "for the policemen to always keep their absolute direction towards him the same"? | |
| Apr 12, 2021 at 15:56 | comment | added | mlk | Okay, I typed a whole answer until I noticed that I misread the rules... So for posterity: If every policeman could move by $\delta$ each turn, the fugitive gets caught if and only if he starts in the interior of the convex hull of the policemen. The strategy for the "if" is for the policemen to always keep their absolute direction towards him the same. The strategy for the "only if" is to just move away perpendicular from the hull and of course also works for the correct problem. | |
| Apr 12, 2021 at 13:25 | comment | added | Eric | @მამუკაჯიბლაძე I think they're very different games, so probably not. | |
| Apr 12, 2021 at 13:19 | comment | added | მამუკა ჯიბლაძე | Exactly, thanks! I wonder if this one can be answered by somehow reversing that one or something... | |
| Apr 12, 2021 at 13:14 | comment | added | Eric | @მამუკაჯიბლაძე mathoverflow.net/questions/358129/the-lion-and-the-zebras you must have meant this one | |
| Apr 12, 2021 at 11:59 | comment | added | მამუკა ჯიბლაძე | @TimothyChow I've seen somewhere a "dual" game - many sheep that try to escape a single wolf. Cannot even figure out whether it is equivalent, more difficult or less difficult... | |
| Apr 12, 2021 at 1:58 | comment | added | Timothy Chow | The problem seems vaguely reminiscent of the Angel problem but it's not clear to me whether any of the ideas carry over. It can also be thought of as a type of fox game but I don't know of any general theorems about fox games that would be relevant here. | |
| Apr 12, 2021 at 0:53 | comment | added | Eric | @TimothyChow The analysis is trivial (almost) because the fugitive can just move along a spoke that divides two adjacent policemen spokes. If say $\delta=1/(2N)$ and the fugitive takes $N$ moves and stays there, they're safe. (speed of an officer is only $\delta /N$ if all of them choose to move an equal distance toward the origin in each turn) | |
| Apr 11, 2021 at 18:10 | comment | added | Timothy Chow | @Eric Have you analyzed the naive strategy where the police officers are equally spaced around a circle and move directly toward the origin unless they can capture the fugitive immediately? Posting that analysis would improve your question, I think. | |
| Apr 11, 2021 at 14:06 | comment | added | Eric | @BillBradley Yes, it's R2. | |
| Apr 11, 2021 at 14:04 | comment | added | Bill Bradley | Is movement restricted to $R^2$? Or something else? | |
| Apr 11, 2021 at 14:02 | history | edited | Eric |
edit tags
|
|
| Apr 11, 2021 at 12:32 | history | edited | Eric | CC BY-SA 4.0 |
added 26 characters in body
|
| Apr 11, 2021 at 12:17 | history | edited | Eric | CC BY-SA 4.0 |
added 26 characters in body
|
| Apr 11, 2021 at 10:52 | history | asked | Eric | CC BY-SA 4.0 |