Timeline for Randall Munroe's Lost Immortals
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Sep 22, 2015 at 13:29 | history | protected | Lucia | ||
| Oct 15, 2014 at 15:29 | comment | added | Timothy Chow | @rghthndsd : Please feel free to post a solution to your version of the problem! | |
| Oct 15, 2014 at 5:31 | answer | added | dotdashdashdash | timeline score: 11 | |
| Oct 15, 2014 at 2:04 | comment | added | Brendan Long | This reminds me of the Tortoise and Hare cycle detection algorithm. | |
| Oct 15, 2014 at 0:51 | comment | added | Steven Stadnicki | I don't think you need 'trails can be destroyed' - here's another more-precise formulation of the problem: each person has a finite number of (either directioned or directionless) objects, labeled $1$ through $n$ (and distinct from the other person's objects). Each person has some finite viewing distance $d$; they can see everything within $d$ and nothing outside it. What constraints on $d$ and $n$ allow the two to meet, and how does the meeting time depend on $d$ and $n$? | |
| Oct 14, 2014 at 21:35 | comment | added | rghthndsd | "unlimited ability to leave a trail behind" I think this assumption completely changes the nature of the question. Monroe's algorithm takes into account that a trial could be destroyed or there may be certain locations where trails can't be left. I find the question to be much more interesting if the trails have a certain probability that they have been destroyed, and that this probability increases with time. | |
| Oct 14, 2014 at 21:16 | comment | added | Steven Gubkin | @TimothyChow Okay, I have done it. | |
| Oct 14, 2014 at 21:15 | answer | added | Steven Gubkin | timeline score: 15 | |
| Oct 14, 2014 at 20:53 | comment | added | Timothy Chow | @StevenGubkin : Why not post an answer? | |
| Oct 14, 2014 at 16:15 | comment | added | usul | If they can write arbitrary messages this might be too easy for them: Each player continually writes her entire strategy on the ground. Once you cross another's path, you simply compute where they will be at all points in the future and pick a meeting point. (This should work because once you read their strategy, you also know when they will next cross your path or if they have already done so, and you know how they will react.) | |
| Oct 14, 2014 at 16:12 | comment | added | usul | I think the most fun question is when the strategies must be symmetric (otherwise it is like they agree beforehand to synchronize) and they must meet as quickly as possible, in expectation, subject to an upper bound on travel speed $v$. So, when both players follow the same strategy, what is the optimal strategy and how long will it take them to meet on the unit sphere? | |
| Oct 14, 2014 at 16:06 | comment | added | Steven Gubkin | Another solution, this one which works even if the other person does not have a strategy, but assumes you can see a finite distance away. From where you start, make a bunch of circles by slicing planes through the circle perpendicular to the radius pointing at you. Make the distance between the circles small enough that you can see from one circle to the next. Walk each circle twice, leaving the message "do not cross this circle" along each path. You should eventually trap the other player between two circles, and you will find them on the second pass around the circle. | |
| Oct 14, 2014 at 15:58 | comment | added | Steven Gubkin | @FrançoisG.Dorais If they can talk before hand, have them agree that one of them will stay put on their geodesic once they have completed a full revolution, and the other will come find them on their geodesic once they intersect it. | |
| Oct 14, 2014 at 15:58 | comment | added | Joonas Ilmavirta | @FrançoisG.Dorais, that depends on the rules. If person A stops when his geodesic meets the other one and person B keeps going forever, they will meet relatively quickly. I assume that the players can agree on a strategy before being thrown to the planet, but if the two players have to make their strategies independently, the problem is harder. | |
| Oct 14, 2014 at 15:50 | comment | added | François G. Dorais | @StevenGubkin: I think they need to agree on speeds that are linearly independent over $\mathbb{Q}$ to ensure a close encounter. | |
| Oct 14, 2014 at 15:34 | comment | added | Steven Gubkin | If they are allowed to talk before hand, just "follow a geodesic" will give a win. Any two geodesics must intersect. | |
| Oct 14, 2014 at 15:34 | comment | added | Yemon Choi | This reminds me of stuff I saw on "stochastic rendezvous problems", see wikipedia.org/wiki/Rendezvous_problem - although the versions I've seen don't allow one to leave markers | |
| Oct 14, 2014 at 15:31 | history | edited | Timothy Chow | CC BY-SA 3.0 |
added 7 characters in body
|
| Oct 14, 2014 at 15:26 | history | asked | Timothy Chow | CC BY-SA 3.0 |