Escaping the field: Man vs. God There is a man standing inside an arbitrarily shaped field.
Dmitri Papichev
I'll assume the person wants to get as far away from his starting point as he can. In this case he wants to increase his radius every step of the way.
zekaric
If the divine intervention can take any form then the answer is clearly no. The God might decide that the intervention will be of the form of never letting the man move at all, in which case he can never escape the field. QED.
David Clayworth
Of course, the God is almighty, but he just decided to limit his intervention here to changing the direction of the man's move to the opposite. The man always moves, but if the God intervenes, he moves to the opposite of his intended direction.
Dmitri Papichev
"Step 1: Pick a direction and go there. Doesn't matter what God does, he'll be 1 unit from where he was. "
JHY
If the God only either allows the man's own choice, or reverses the direction, then I bow to zekaric's solution. Good puzzle, and a good solution.
David Clayworth
Not a square. More of a spiral around the starting point.
zekaric
Sorry, if you draw a line of the path he takes it'll look like a spiral or spiral in nature depending on how god plays with him. :)
zekaric
I get it now. I was not reading carefully enough and intepreted the new vector is 90 degrees from the last vector.
JHY
Just need to say "finite field" in the problem (may be add "plane" somewhere - I'll explain later) and after some proof zacaric's solution will be ok. Strict proof will give you something like ln(N) distance from starting point at step N, which has no upper limit.
DK
OK, now we know how the man can do that.
Dmitri Papichev
Optimizing is tricky. If you consider a circle, and you start at the center, I think it's clear that Zekaric's algorithm is optimal, and it will take R^2 steps (it's not exponential as DK suggested). But for arbitrarily-shaped regions, it's tougher. I haven't figured it out, but Zekaric's algorithm I think clearly gives only a lower bound; I think you can do better. This is because his algorithm relies on getting away from the starting point, not getting to the closest boundary.
Brian
Sorry, Brian, I'm too lazy to actually go and proof if the distance from starting point in zekaric's algorithm will be big O from sqr(N) or ln(N), not right now anyway. Logarithm just popped up after checking one or two elements in series and as someone noticed here the trajectory will be kind of spiral.
DK
Hmm, sorry again, Brian - I need to learn to read more carefully - you were referring to circular field.
DK
I don't see how you would be able to optimize it. You have a few problems that are undefined.
zekaric
Does anyone mind if we stop calling it God vs. Man? It's really wierd - this is math, not religion. It's just a 2 player game, where player 1 is trying to create a sequence of points p_1, p_2, ... that escapes a region R. At each turn, he creates a unit direction vector e_i, and player 2 chooses either p_i = p_i-1 + e_i or p_i = p_i-1 - e_i (these are vectors).
Brian
Thank you for the pythagorian explanation - it's really good. I've made an error while trying to solve it in a more complex way.
DK
DK: but since your argument about field shrinking punts to zekaric's finiteness argument, you haven't gained anything by introducing the notion of F1, F2, ... .
Brian
And that's not to say that I don't think the field shrinking idea is worthwhile. In fact, it's most interesting in the case where the region is unbounded, and the R^2 algorithm is powerless. But I think we agree that it becomes a hard-core topology problem rather than an interesting riddle.
Brian
ok, let's argue a little ;)
DK
> Zekaric's algorithm was used in my reasoning to prove number of nested fields we build F1 > F2 > F3 ... is finite
Brian
You did a great job solving this Man vs. Wizard :) riddle!
Dmitri Papichev
I'm a bit too tired to write long stuff, so just one line:
DK
Yes, exactly that - min (max (...))
Dmitri Papichev
Well, looks like it's just "yet another strategy", which does not do any good for lot of fields if you use it as it is. Even a simple 10x2 bar field would be a trouble for it if starting point is somewhere in the middle of it.
DK
ok, it doesn't work for any square larger than 1x1 too :(
DK
Can't throw this riddle away from head :)
DK
mmm, scrap that "doesn't work for 1x1 square" comment plesae. I need more sleep.
DK
Um, DK: I don't mean to sound nasty, but your posts barely make sense anymore. And the ones that do make sense seem to be patently false ("[player 2] can keep [player 1] inside any given straight 1m wide corridor").
Brian
Hmm... Min-max algorithm apparently doen't work, as DK clearly demonstrated.
Dmitri Papichev
Brian, I don't mind you sound nasty, especially when you right - it should be 2m (you had that kind of situation considered before - your "|y|<=1" field), my fault.
DK
Can you expand on what "min-max algorithm" is supposed to mean, and why it doesn't work?
Brian
Brian:
Dmitri Papichev
So, can the radar distinguish between the region |y| < 1 (winnable) and |y| <= 1 (not winnable)? Or is there an unstated assumption that makes one of these illegal?
Brian
If I understand your question correctly, the answer is no.
Dmitri Papichev
No, I guess my question isn't very clear. It has to do with this: can the radar distinguish if the boundary is included in the region or not? And as to why it's important, I cited those two regions, one of which is escapable and one of which isn't. And the only difference between these two regions is that the boundary is included in one of them.
Brian
Brian: I think of the regions with the borders exluded, that is, if you got to the border, you successfully escaped.
Dmitri Papichev
Algorithm:
HolyMan
Fog Creek Home |