Edit: Lots of the responses were welcome, but none really gave me anything conclusive and I eventually lost interest in this problem. I have now released some of the responses I had below, and will try to get all the ones I was emailed online at some point. The experiment was to do with intuition regarding the “angel problem” which has been solved but have variants that have not. When this was published I was thinking about the ‘timebomb angel problem’ in 2D, and the below problem is the same problem in 1D. The keen reader will be able to find the solution online, so I won’t post it here and spoil the problem for other people wishing to try.

I have started having a few thoughts that have led me to propose a quick experiment which could be helpful in solving a problem I’ve been working on. If you (a mathematically inclined blog reader) have about 10 minutes free right now and are keen to try a nice problem, read on. Otherwise, stop reading and come back later when you have a little bit of time.

Basically I need you to try the following problem more-or-less immediately (no subconscious thinking time!) for ONLY 10-15 MINUTES and then send me a quick email (my @cam.ac.uk address is tl309) detailing your thoughts on the problem. You don’t have to have solved it. What I’m really interested in is your reaction to the problem and the heuristics going through your mind. How you *feel* after 10-15 minutes of work could be immensely useful to know, and if I get enough responses I’ll post the interesting ones in a later post explaining what I’m trying to do.

**Problem: ***Imre got lost on the way to his office and has found himself wandering along the infinitely long corridor in the Centre for Mathematical Sciences. The floor is covered with large tiles such that the corridor is only one tile wide but there are infinitely many stretching in both directions. Imre’s arch-enemy (whom we shall denote Ermi) has rigged up the corridor with teleporters so that if Imre is on certain tiles at certain times he is transported to a faraway nightmarish universe where the axiom of choice is false.*

*Imre takes one second to move one tile in either direction (though he could just pause and wave his arms for a second instead). Owing to power limitations (and his unsophisticated doom teleporter software), each second Ermi can program just a single teleporter to activate for just one second at some specified point in the future (so he *could* keep one teleporter activated for the entire time, or could activate lots of teleporters simultaneously but only for a very short period of time at a specified point quite far away in the future). There is a time delay, so Ermi can’t turn any teleporters on instantly (so Imre will always get a chance to move out of the way if a teleporter is activated where he is standing). Is it possible for Ermi to trap Imre, or can Imre evade him forever (if whenever Ermi programs a teleporter Imre knows about it)?*

If you’ve seen and thought about an equivalent problem before, please don’t tell anyone else for the time being (and don’t bother sending me an email). Otherwise, enjoy, and I’ll be interested in hearing your thoughts (obviously, once you’ve sent me the email, feel free to try solving the problem ;)).

Tom.

Edit: It would actually be ok if you just posted a “comment” underneath this thread instead of emailing. I was worried about people reading what other people had written, but since I can wait until I publish the comments publically this isn’t an issue.

## 8 comments

Comments feed for this article

October 10, 2009 at 11:25 am

SahlHello,

The problem was difficult but in the first 10 minutes, I first tried to draw an image of the situation in my brain and then draw a simplified diagram (that is tiling squares in a horizontal line which are touching). Once reading the question, I believed that I would be unable to make much progress because I had tried to solve previous Game Theory problems but could hardly solve them. What I then did was fixed the starting point of Imre and tried finding the best strategy which both Imre and Ermi could take.

Sahl

October 10, 2009 at 2:43 pm

RachaelThis is a rather stange, but interesting problem – and it seems to be more about logic than hardcore maths! (not a complaint). Ignoring amusing thoughts about the way the problem is put; I mostly felt that the problem would be realtively simple once thought about in the right way. My first thoughts were with only one teleport activated at once – it took a while for activating several at the same time to occur to me. In that situation, clearly Imre cannot be trapped. After mentally playing around with this, I thought about using lots at once. Obviously, it is impossible to activate all of an infinate number of telelports at once within these rules. I then had the thought that this is basically a case of Ermi trying to predict where Imre will go, and/or force this. This brought me onto a side track of how much Imre knows about what teleports will activate when. I thought about activating a few at once to try and force Imre into a particular place, but as Imre could move out of the way while this was being programmed it probably wouldn’t work with the number needing to be activated at once. My gut feel at the end of that was that it isn’t possible to create a foolproof trap this way.

November 1, 2009 at 8:55 pm

gowersOK here goes. I’ll write my thoughts in real time.

Obvious thought: it’s no good Ermi hitting the square Imre’s actually on.

It feels impossible for Ermi to win, so let me try a strategy for Imre.

Hmm. Two extremes occur to me. One is where Imre just chooses a direction and marches off in that direction. But if Ermi knows that’s what Imre is going to do then he can make a trap — I won’t bother with the easy details. The other extreme is a random walk, but then he hangs around too long near the origin and again a trap is possible.

From that we learn that Imre must move fast — basically his average speed must be close to 1.

Can I make that a lemma? Maybe I need to take more account of what Ermi is doing.

Can Ermi slow Imre down using only half his moves and then use the other half to nail him? No, doesn’t obviously work because if Imre is slowed down to half speed and Ermi has only half his moves then it doesn’t obviously favour Ermi.

Does a randomized strategy work? Or what if Ermi concentrates on a particular stretch of tiles some way away and attempts to make sure that Imre will not be able to cross it? In fact, can Ermi at least confine Imre to a finite region about 0? Let’s try that.

Let’s make Ermi try to stop Imre getting past 10 or -10. Every time Imre is on a positive tile, Ermi will prepare a trap on squares 8,9,10. What’s more, he will do it on the assumption that Imre is going to go directly towards those squares, aiming to get them to fire at the moment Imre lands on 9.

That seems hopeless, unfortunately, because Ermi needs to get three tiles to fire at once. So Imre can just head to 7, wait for them to fire a few times, or something like that.

I feel as though if I didn’t have the time pressure I could make more progress with this problem.

What would a randomized strategy be? Something like picking a point uniformly at random from all the points at distance at most 100 from Imre and getting it to fire at some random moment that’s roughly comparable to, but usually a bit smaller than, the distance from Imre. I’m not sure how the probabilities would work out there, but perhaps one could show that with probability 1 this strategy would eventually succeed in trapping Imre. (The rough idea would be that Imre’s progress would be slowed just enough for it to work. It’s tempting to go deterministic if Ermi gets into a winning position, but if that happens with probability 1 then with probability 1 Ermi will do the winning moves eventually so we don’t have to complicate things.)

OK I’m out of time.

Two things that may slightly affect my answer. One is that I had an enforced break of a few minutes in the middle of what I was writing above, when I had to feed a bottle of milk to my almost-two-year-old son. I tried not to think about the problem but couldn’t quite banish it from my mind entirely. Secondly, I have in the past thought a lot about the angels and devils problem. It’s not equivalent, but it means that I had certain ideas for this problem that I wouldn’t have had nearly so quickly if I hadn’t had that experience in the past.

November 6, 2009 at 9:47 am

Carnival of Mathematics #59 « The Number Warrior[…] Speaking of puzzles, Tom Lovering wants you to participate in a problem solving experiment involving an infinite hallway. […]

November 10, 2009 at 1:30 am

Andrew MWI’m a total amateur, but my thoughts…

I’m not sure Ermi is ever ‘guaranteed’ of succes, but if he has infinte ‘time’ then couldn’t he just activate the teleporter on the tile adjacent to Imre every time – assuming Imre is moving around, then Ermi is more or less guaranteed of success in the long run. If Imre isn’t moving around, then Ermi knows how to get him moving! So I would say yes, in the long run, Ermi is ‘assured’ of success (even if not technically guaranteed). I’m thinking limits here – as the limit of t goes to infinity, Ermi’s chances of success approach 1.

How do I feel?

A little perplexed. And I’m not sure I understood the question properly, particularly the bit about “so Imre will always get a chance to move out of the way”- can Imre hear the thing turning on or something? I assume not, and that there is only a 1 second “lead time” in turning the teleporter on?

November 13, 2009 at 4:10 am

SueSaved by a phone call. I have to head home. Worked on it for maybe 5 minutes. Got nowhere. It seems impossible to trap, but I often think impossible too soon. Will look forward to hearing more. Heuristics? Hmm… Drew a diagram. Can’t see any way to simplify. Seems like I’m trying to set dreaded teleporters (DTs) at a distance that gives me enough time to set lots of seconds on each one, and somehow then start working inward. This seems like a flimsy start.

December 15, 2009 at 5:47 pm

Adam StephanidesYour experiment is probably over, but in case it’s not, I’ll give it a shot.

My approach wasn’t particularly rigorous. I visualized the problem as an infinite chessboard with Imre moving one step each “turn,” either vertically or diagonally, and Ermi blocking off one square per turn. First I tried to think of a strategy to capture Imre. My first try was to construct a blockade at some point in the future (without taking Imre’s movements into account). But a blockade at a single moment, say n sections in the future, doesn’t work because it would require activating 2n+1 teleoporters whereas Ermi will only have time to activate n. Then I thought of whereever Imre is, activate that teleporter at some point in the future, since such moves would probably be the most efficient move-by-move. But Imre can easily evade that by moving constantly in one direction.

So then I switched to showing that Imre could always escape. At first I had some vague thoughts about always moving away from the “center of gravity” of the upcoming activated tiles, or some kind of strategy based on Imre being able to move “outside the range” (i.e. where it is impossible to reach a given square) of enough tiles. Then, while picturing Imre’s possible trajectories as a tree, it occurred to me to use Konig’s lemma. I would just need to show that there were an infinite number of positions Imre could reach, which could be done by showing that for any n, Imre could last at least n seconds. But then I realized that a naive application of Konig’s lemma wouldn’t work, since at any second Emri has an infinite number of possible moves. I briefly tried to think of some way of salvaging Konig’s lemma. But time was running out, so instead I thought of approaching it by induction: “if Imre can always last n seconds then he can always last n+1 seconds.” I started by trying to think of the positions in which Imre was immediately blocked (obvious), then the positions in which he was blocked after 1 second, etc. but I didn’t get far before my time ran out. Though I didn’t solve it, it seemed more likely to me that Imre can always escape.

March 17, 2010 at 2:19 pm

BrookI think it’s impossible, but have no real idea how to show this. After n goes Imre can be on any of 2n + 1 places and Ermi can only of covered n. Whats more, this means either to the left or the right of the start half of the squares at least are free. By always going to places where more squares seem to be free, it seems like you have enough freedom – somewhere the density of bad squares will be less than half – If you are there by choosing left, right of stop you won’t get hit.

Just ideas…