Twins in a Maze

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
6453893
Posts: 557
Joined: Wed Dec 13, 2006 2:40 am UTC
Location: Australia

Twins in a Maze

Postby 6453893 » Mon Jan 31, 2011 6:41 am UTC

I thought of this last night as I fell asleep, and I don't know the answer or if there even is a (foolproof) one, but the question intrigues me.

You and your identical twin are dropped into a maze of unknown (but finite) size and design. Assume the maze has no exit, or that its exit is hidden from you, until you find your twin. You must therefore devise a method of navigation that ensures you will find your twin. You and your twin know that, being identical in mind and body, each will arrive at the same method as the other. You cannot call out to one another, leave markings or a trail. The maze may contain loops. Time is not a factor. Is it possible to establish a formula that will necessarily lead you to your twin, while preventing both twins, for instance, getting caught circling the same part of the maze?

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Twins in a Maze

Postby ++$_ » Mon Jan 31, 2011 8:03 am UTC

Spoiler:
You can reach any point in the maze with BFS or iterated DFS. However, it might happen that your twin, doing the same algorithm, never manages to get into contact with you (i.e. you always miss each other), so the algorithm needs an adjustment.

If you have a method to generate random numbers, then you can randomly search for one hour or sleep for one hour, with equal probability. With probability 1, there will come a time where you search for enough consecutive periods to explore the entire maze, while your twin sleeps during that same time period. Then you will come across your twin. This assumes that you have a method for ensuring that your sleep time is in a compact subset of the positive reals (it doesn't need to be precisely 1 hour).

If you don't have even such a crude method to tell time, but you do know for certain that the maze is planar, then you can begin by searching the entire maze and memorizing its layout in two dimensions. Then, you travel to the boundary of the maze, flip a coin, and travel clockwise or counterclockwise according to the flip until you have made one complete circuit. Then you flip again, and so on. With probability 1, you and your twin will eventually meet.

I wonder if there is a method that works for non-planar graphs.

If you don't have a method to produce random numbers, then you will never be able to find each other in the worst case. You might start out at opposite sides of a perfectly circular, featureless maze, and since you must take the same actions at any given time, you will remain at opposite sides of the circle forever.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Twins in a Maze

Postby jaap » Mon Jan 31, 2011 8:55 am UTC

6453893 wrote:Is it possible to establish a formula that will necessarily lead you to your twin, while preventing both twins, for instance, getting caught circling the same part of the maze?
I don't think so.
Spoiler:
Imagine a maze which has 180 degree rotational symmetry, with the twins in opposite spots. If they do the same movements, they will see exactly the same things and remain on opposite sides of the maze. If they have identical deterministic strategies only dependent on what they see of the maze, then (assuming the symmetric maze does not have a path through its centre) they cannot meet.
The only way I can see to break this symmetry is either to introduce some randomness, give them compasses, or have one twin be the mirror image of the other in strategy.

One strategy could be for both twins to fully explore the maze with the usual right hand rule (I am assuming they have perfect memory or can draw the map as they go, and so can recognize when they return to a location they've been before), and then meet at the point closest to the centre. If there is no unique central location, then they could:
1. Choose the most Northern (if they both have a compass)
2. Visit each central location in turn, one twin going clockwise around the centre, the other anti-clockwise.
3. Visit each central location in turn, in a random order.

User avatar
Adacore
Posts: 2755
Joined: Fri Feb 20, 2009 12:35 pm UTC
Location: 한국 창원

Re: Twins in a Maze

Postby Adacore » Mon Jan 31, 2011 1:52 pm UTC

Yeah, I think that's right:
Spoiler:
Obviously if you can come up with any way to differentiate the twins, the problem becomes trivial - one twin just has to stand there while the other performs a comprehensive search. Again, with randomness the probability rapidly approaches (although can never be exactly) 1 that you find the twin after you make a random choice - but the whole premise is that the twins, being identical, would make the same random choice.

As ++&_ and jaap say, With true identical twins dropped opposite each other in a rotationally symmetric maze, you'll never meet unless a path goes through the centre. The simplest version of this is a single circular loop - you will always be exactly opposite your twin. You'll even, after some brief exploration, know exactly where your twin is, and yet be completely unable to ever meet him.

For non-symmetric mazes*, it's easy enough to (as a first pass at a solution), use the pattern of junctions you encounter to define some kind of key if whatever optimised first search routine fails to result in a meeting. For example, assuming a grid-based maze, the possible junctions are left turn, right turn, left T-junction, right T-junction, crossroads and cross T-junction - 6 possibilities. Just use a system in base-6 to encode the maze along the exploration path from whatever algorithm you're using, then use the final answer to determine whether you stay put or explore for each given 'round' of exploration (so, for example, 'odd number J1 explores, even number J1 stays put'). This could take ages, if the maze was very similar from each of your start points, but it would always work.

*I think this works in symmetric mazes with a drop-point that isn't opposite your twin. The 'exactly opposite in a rotationally symmetric maze' thing is actually a very small subset of all possible maze designs and starting locations.

Final note: obviously for certain mazes (of the labyrinth variety), a meeting is inevitable in the first exploration pass.

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Re: Twins in a Maze

Postby undecim » Mon Jan 31, 2011 4:31 pm UTC

Spoiler:
If the maze is rotationally symmetrical, and you and your twin start in place that is similar, then you can never find one-another without something like a compass, or a landmark that is not in the center of the maze (for example, if the maze has no roof, you can determine from the sun/stars what direction you are facing).

Therefor, without some additional information/ability, there is no algorithm that will always allow you to find your twin. This assumes that there is no path through the center, otherwise the twins would meet there. For any maze with a path through the center (symmetrical or not), the twins can just explore the maze and determine where the center is and meet there.


EDIT: Heh... Accidentally hit Quote instead of Edit without realizing.

Solution for any non-rotationally-symmetric maze of any shape with a finite size and resolution:
Spoiler:
Caveat: This assumes that the twins have the ability to retain a map of the maze and make arbitrarily precise calculations and measurements. This might including using measurement tools, record-keeping tools, and/or superhuman mental abilities.

Let w be the maze wall.

1) Explore and map the maze (there are known algorithms for this); If there is any part of the maze that cannot be explored, consider all of it to be on w.
2) Circumscribe the maze in circle c, with radius r, centerpoint b.
3) For the nth repetition of this step (starting with 0) consider all circles concentric to c with radius mr/2^n for all integers m>0=>2^n. Determine the largest of these circles d for which the intersect of the set of points on d and the set of points on the maze wall w is not rotationally symmetric. If no such circle exists, repeat this step. (This step loops infinitely for a rotationally symmetric maze
4) Find the largest arc a on d with no points on w (i.e. the biggest gap in the walls on d). If such an arc does not exist, go to step 4a. Otherwise, go to step 5
4a) Let s be the set of arcs on d which contain no points on w (i.e. all the gaps in the walls on d). If the maximal elements of s are rotationally symmetric (i.e. we cant use them to orient), reconsider all elements of s to also be on w and go to step 4 (i.e. fill in the gaps in the walls on d) . Otherwise, go to step 4b
4b) Reconsider all elements of s to be on w (i.e. all the gaps in the walls on d), and the rest of the points on d to not be in w (i.e. erase anything on the circle we didn't just fill in). Go to step 4.
5) Consider the "top" of the maze to be the point on the ray from b though the middle of a which intersects c.
6) Go to the leftmost of the topmost reachable points of the maze.

In a nutshell, this algorithm explores the cave and deterministically (so that it can't be affected by a twin's original orientation) picks a circle to work with, then deterministically picks a point on that circle to orient the twins and have them meet at the upperleftmost point in the maze.

The wording on 4*) is probably confusing, but basically, it's just picking an arc a on the circle d based on the maze walls. If someone knows an easier way to explain what is going on, or an easier way to deterministically pick a point on the circle, please say so.
Blue, blue, blue

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Twins in a Maze

Postby redrogue » Mon Jan 31, 2011 11:19 pm UTC

Assuming the maze has intersections (and is non-symmetrical):
Spoiler:
Perform a comprehensive search, noting the location of three-way, four-way, five-way, ... n-way intersections as separate groups. Choose the group with the shortest non-cyclical route that travels through its intersections (one with clear end nodes), using the highest index in case of ties (e.g., 6-way beats 5-way). Walk that path from end to end, repetitively.

My twin will choose the same path, if there are multiple shortest paths. We'll meet along the path eventually.


Although...
Spoiler:
If my twin and I would reach the same solution, why can't I just perform a comprehensive search, choose "the best intersection to meet" and wait there for him to show up. He should choose the same intersection as well, right?

That seems too simple.


A better solution is as follows (again, assuming non-symmetrical):
Spoiler:
Perform a comprehensive search. Group intersections as above. Start with 3-way intersections, find the geometric center of them. Choose the intersection furthest from that center and meet there.

If there is no such intersection, try 4-way intersections, then 5-way... and repeat to N-way. If that fails, group 3&4 way, then 3&5... etc. Eventually, I should find a unique intersection furthest from the geometric center of the others.
Is 'no' your answer to this question?

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: Twins in a Maze

Postby dedalus » Tue Feb 01, 2011 4:25 am UTC

Spoiler:
Completely map the maze (as was said before), then circumscribe it in the smallest possible circle (or n-dimensional sphere). Move as close as possible to the center of the circle. This should work unless theres multiple points closest to the center which are separated by a wall. Beyond this you'd need either a means of randomisation or an external reference.


A simple map that I think is impossible to find your twin on without reference to an external source or some means of randomisation is:
Spoiler:
A circle divided into four equal quadrants by a cross, with space to walk between the edges of the cross and the circle.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Re: Twins in a Maze

Postby undecim » Tue Feb 01, 2011 4:30 am UTC

redrogue wrote:Although...
Spoiler:
If my twin and I would reach the same solution, why can't I just perform a comprehensive search, choose "the best intersection to meet" and wait there for him to show up. He should choose the same intersection as well, right?

That seems too simple.


Spoiler:
You can't just say "my twin would choose the same spot" because that's not necessarily true. His/her original position in the maze may predispose any subjective decision, so if you don't have some objective way to determine where to meet, you don't know for sure that your twin will choose the same place.
Blue, blue, blue

Superisis
Posts: 48
Joined: Fri Sep 17, 2010 8:48 am UTC

Re: Twins in a Maze

Postby Superisis » Tue Feb 01, 2011 3:05 pm UTC

Adacore wrote:Yeah, I think that's right:
Spoiler:
Obviously if you can come up with any way to differentiate the twins, the problem becomes trivial - one twin just has to stand there while the other performs a comprehensive search. Again, with randomness the probability rapidly approaches (although can never be exactly) 1 that you find the twin after you make a random choice - but the whole premise is that the twins, being identical, would make the same random choice.

As ++&_ and jaap say, With true identical twins dropped opposite each other in a rotationally symmetric maze, you'll never meet unless a path goes through the centre. The simplest version of this is a single circular loop - you will always be exactly opposite your twin. You'll even, after some brief exploration, know exactly where your twin is, and yet be completely unable to ever meet him.

For non-symmetric mazes*, it's easy enough to (as a first pass at a solution), use the pattern of junctions you encounter to define some kind of key if whatever optimised first search routine fails to result in a meeting. For example, assuming a grid-based maze, the possible junctions are left turn, right turn, left T-junction, right T-junction, crossroads and cross T-junction - 6 possibilities. Just use a system in base-6 to encode the maze along the exploration path from whatever algorithm you're using, then use the final answer to determine whether you stay put or explore for each given 'round' of exploration (so, for example, 'odd number J1 explores, even number J1 stays put'). This could take ages, if the maze was very similar from each of your start points, but it would always work.

*I think this works in symmetric mazes with a drop-point that isn't opposite your twin. The 'exactly opposite in a rotationally symmetric maze' thing is actually a very small subset of all possible maze designs and starting locations.

Final note: obviously for certain mazes (of the labyrinth variety), a meeting is inevitable in the first exploration pass.


Spoiler:
Couldn't the twins move arbitrarily via a coin flip (both will think of the same strategy, being twins, but the randomness of their walk will be different) ? Wont that give a markov chain with a state that would be both twins in the same area . Since the chain is closed and there is infinite time wouldn't they eventually meet? Am I missing something?

User avatar
Adacore
Posts: 2755
Joined: Fri Feb 20, 2009 12:35 pm UTC
Location: 한국 창원

Re: Twins in a Maze

Postby Adacore » Tue Feb 01, 2011 3:47 pm UTC

In any maze with no rotational symmetry:
Spoiler:
Something akin to what redrogue said should work. If you use an algorithm to decide which intersection was the 'best' based purely on the actual topography of the maze (not influenced by the starting points), both twins can just meet at that intersection as soon as they have performed a complete exploration of the maze. Devising the algorithm itself such that it works for any given maze might be tricky, though. An obvious first step might be 'junction with the most paths meeting' or 'junction with the shortest distance to reach every other point in the maze'. Then just keep adding rules until you get to a unique solution.

So that leaves us with a situation where we know it's impossible (given no random choice) with similar starting locations and any form of rotational symmetry, but definitely possible (in a relatively short finite time) where there is no rotational symmetry at all.

And for all mazes:
Spoiler:
The remaining problem, then, is solving the case where there is rotational symmetry and non-similar drop points. In that case, it's a case of either working out which twin waits and which searches, or determining search patterns that are guaranteed to overlap based on the original start positions. Or, I suppose, if you can mark your start position somehow, then once you've explored the maze you'll know the start position of your twin. At that point you can use the same system as for non-symmetric mazes, determining which start point is 'best' to meet at by some algorithm or, if the start points are rotationally similar, give up (or resort to randomness, if that's allowed - with only two points to choose from the odds of both ending up at the same place approach 1 very fast). If marking is not allowed, I imagine the 'best' algorithm to determine when and how to search is extremely tedious.

A full solution algorithm, then, will probably have three sections once the maze is fully explored: in the case where there is infinite rotational symmetry (a circle), give up; where there is no rotational symmetry, go to the 'best' meeting point; where there is rotational symmetry of any other variety, either choose the 'best' start point to meet (if you can mark start points) or perform a series of optimised searches based on your start point.

Superisis:
Spoiler:
There was no statement of infinite time, afaik. Actually, I read it as being a finite-time problem, in that you probably want to find your twin before you run out of food/water, or die of old age, or the universe ends.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Twins in a Maze

Postby redrogue » Tue Feb 01, 2011 5:54 pm UTC

I'd assume infinite time.

This would be a great problem for robotics -- contestants will be provided two identical robots, and you must provide a single piece code that will be copied onto each by the event organizers, before they are dropped randomly into a closed maze. You win when the robots meet.

undecim:
Spoiler:
I realized after I wrote that that "my twin will naturally choose the same path" is not true either, depending on the order points are found. For instance, I could have this scenario:

axxx
xoox
xoox
xxxb

A and B are intersections. X's are paths, O's are solid walls. If I find A first and my twin finds B first, I might always miss my twin.
Is 'no' your answer to this question?

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Re: Twins in a Maze

Postby undecim » Tue Feb 01, 2011 6:42 pm UTC

redrogue wrote:undecim:
Spoiler:
I realized after I wrote that that "my twin will naturally choose the same path" is not true either, depending on the order points are found. For instance, I could have this scenario:

axxx
xoox
xoox
xxxb

A and B are intersections. X's are paths, O's are solid walls. If I find A first and my twin finds B first, I might always miss my twin.


Spoiler:
This is rotationally symmetric.


Edit:

seems to me it all just comes down to
Spoiler:
Picking a place to meet. This is possible for any non-rotationally-symmetric maze with no path through the center. In the case of such a symmetric maze with no center path, some outside source of information needs to be used. For example:
  • A Compass
  • A non-central landmark.
  • randomness

Though I've gotten to thinking about the case of the rotationally symmetric maze as well. You can have a high probability of finding your twin if you rest for td/u where m is the amount of time it takes your pre-determined exploration algorithm to explore the maze from the worst-case position, d is the distance from the center of the maze when you started (which you can determine after one exploration), and u is some unit of measure. After that rest, you explore the maze once, then rest for t(r-d)/u, where r is the radius of the circle that circumscribes the maze (i.e. the farthest distance one can be from the center). Provided the difference in you and your twin's distance from the center is not exactly the same, you can repeat this, halving u each time and eventually find each other. If your d's are the same, you will repreat this cycle ad-infinitum.

You could also speed it up by determining the shortest cyclic path in the maze (with some other metrics to discern equal-length paths) and treat that as the only part of the maze.

Another option is to determine a place for the symmetry to start (e.g. a triangle might "start" at the corners), and use something like the algorithm above to determine your distance from the start of the rotational symmetry (e.g. in radians). Combined with the "distance form the center" metric above, you could give each point in the maze a metric that is unique, except for its symmetric points. Which means that unless you and your twin start in symmetric locations, you will eventually find each other.


(P.S: Is there a word for a rotationally-asymmetric object that can be duplicated to create a rotationally-symmetric object? for example, 3 congruent lines, or 3 congruent pairs of lines at 60° vertices can make an equilateral triangle.)
Blue, blue, blue

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Twins in a Maze

Postby redrogue » Tue Feb 01, 2011 11:11 pm UTC

undecim wrote:
Spoiler:
This is rotationally symmetric.

Sorry. I intended that to refer to a portion of the maze, not the entire maze. Assume other paths and intersections exist.

For symmetrical, 2D, non-mobius mazes lacking teleporters:
Spoiler:
Find the path that travels along the outermost perimeter of the maze, as well as the shortest path from the perimeter to your starting point. Walk the perimeter, deviating only to take that path back to your starting point and out to the perimeter again. If you and your twin have different length deviation paths, you should eventually run into each other.
Is 'no' your answer to this question?

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Twins in a Maze

Postby imatrendytotebag » Wed Feb 02, 2011 3:46 pm UTC

Everyone's stated that there are algorithms for exploring and mapping the maze, but I'm not convinced. Maybe if they're planar, but consider the following two mazes:

1- A single path with a circle centered on it (think the London Underground logo). The ends of the path are connected to each other (if you like, the maze is on the surface of a cylinder)

2- The same maze as in 1, but with TWO circles.

How could somebody in the maze differentiate between these two mazes with no method of marking?

(Note for all you topologists out there: Supposing the person has a very poor internal sense of distance and direction and so cannot distinguish between homeomorphic mazes, then he should also be unable to distinguish between a maze which is a covering space for another maze.)
Hey baby, I'm proving love at nth sight by induction and you're my base case.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Twins in a Maze

Postby redrogue » Wed Feb 02, 2011 4:37 pm UTC

...which is why I specified '2D, non-mobius mazes lacking teleporters' in my above solution. :)

For your cylinder problem, wouldn't two circles require a larger diameter cylinder? I know that the slight difference in curves between 999 linked underground symbols and 1000 on a cylinder will probably indistinguishable for humans, but I could probably figure out 1 vs 2. Assume the maze is solved by a robot that's really good at measuring things (but terrible at marking). Many of the solutions work as well in three dimensions as they do in two.

I've been assuming planar mazes, but I do realize that some of my solutions don't really work even on a figure of eight racetrack shaped maze, with a bridge in the middle. See my last spoiled answer, and you'll quickly realize it doesn't work (hence, 2d).

Mazes with teleporters, however, break everything. Do I have one maze that teleports me around inside it? Or two identical maze sections next to each other, and teleport back and forth? :)


Side note:
For symmetrical mazes with mirrored starting positions, it kind of strikes me as similar to the dining philosophers problem. It's maddening, but I keep feeling like there could be a solution for the ring-shaped maze that relies on resource synchronization.
Is 'no' your answer to this question?

Superisis
Posts: 48
Joined: Fri Sep 17, 2010 8:48 am UTC

Re: Twins in a Maze

Postby Superisis » Thu Feb 03, 2011 2:40 am UTC

Adacore wrote:Superisis:
Spoiler:
There was no statement of infinite time, afaik. Actually, I read it as being a finite-time problem, in that you probably want to find your twin before you run out of food/water, or die of old age, or the universe ends.


It said in the original post that time was not a factor.

User avatar
Adacore
Posts: 2755
Joined: Fri Feb 20, 2009 12:35 pm UTC
Location: 한국 창원

Re: Twins in a Maze

Postby Adacore » Thu Feb 03, 2011 5:26 pm UTC

Oh yeah, sorry Superisis, I fail at reading :oops:

If the maze is in any kind of curved space environment, such that a straight path can form a loop (or, equivalently, there are teleporters), then it is indeed impossible to map the maze accurately without the ability to mark locations. With 'conventional' topology, I think it should always be possible to map a maze, though.

The figure-8 racetrack maze is a rotationally symmetrical 3-dimensional maze with no path through the centre and, thus, cannot be solved, unless you have gravity to define 'up' in one of those dimensions, in which case it's trivially solved by saying 'go to the highest point', or similar.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Twins in a Maze

Postby Yakk » Thu Feb 03, 2011 5:44 pm UTC

So I was trying to figure out how to exploit symmetry failures in physics in order to get one Twin to go left and the other Twin to go right at some point. Sadly, I think Noether says that rotational momentum being conserved means I'm screwed, right?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Twins in a Maze

Postby WarDaft » Thu Feb 03, 2011 7:51 pm UTC

All they need is some QM hijinks, keep doing trials and their odds of not breaking symmetry drop off toward 0. Given truly infinite time, there's no need for special equipment, as quantum events with vanishingly small chances of happening will eventually probably happen, like an electron tunneling and resulting in a neuron taking slightly longer to fire eventually building up to a completely different mind state.

That's assuming that they're molecule for molecule fundamentally identical in the first place, otherwise, they can just guess meeting points at random and despite being twins they will actually guess differently eventually.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Adacore
Posts: 2755
Joined: Fri Feb 20, 2009 12:35 pm UTC
Location: 한국 창원

Re: Twins in a Maze

Postby Adacore » Fri Feb 04, 2011 10:28 am UTC

But with that sort of probabilities, they could just stand there and wait for the maze to ablate/decay/randomly disappear and then just walk towards each other.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Twins in a Maze

Postby WarDaft » Fri Feb 04, 2011 8:07 pm UTC

The odds of the maze decaying before they do is low, a single molecule out of place triggering a diverging chaotic system in the brain is a much safer bet.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

bobleboffon3
Posts: 38
Joined: Fri Jul 16, 2010 7:35 am UTC

Re: Twins in a Maze

Postby bobleboffon3 » Sat Feb 05, 2011 4:51 am UTC

Spoiler:
The way I see it, for the twins not to be able to meet up somewhere, 3 conditions need to be there.

1) The maze must have rotational symmetry
2) The twins must have no way to differenciate each other/talk beforehand
3) The twins must have no way to figure out a random number/event

If any of these 3 conditions misses, they can do it.

It's not very hard to simulate a random event in my opinion. All they need is something ( they have food/water right? Or one of their shoe, or a hair, anything ) to throw on the ground and if it's this side of an imaginary line, they stand still for an hour, if it lands on the other side they move for an hour. If they don't meet, they try again with a day, then a week, then a month, and so on. They'll meet at some point.

If they have absolutely no way ( or are forbidden ) to use such tactic to figure out a random event, then won't meet up in a rotationnaly symmetrical maze, even with infinite time.

Lucia
Posts: 95
Joined: Sun May 09, 2010 1:35 am UTC

Re: Twins in a Maze

Postby Lucia » Sat Feb 05, 2011 9:04 am UTC

It's always possible if there's a unique location in the maze. Even if it is rotationally symmetrical, if you can reach the centre it's possible. If the maze consists of a single path in a loop, with those conditions, it is impossible. If it's possible to reach the centre, you meet there. If there is a single unique feature, you meet there.
Wildhound wrote:Nobody ever sigs me. I think it's because I never say anything clever.

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Twins in a Maze

Postby t1mm01994 » Sat Feb 05, 2011 10:14 am UTC

Lucia wrote:It's always possible if there's a unique location in the maze. Even if it is rotationally symmetrical, if you can reach the centre it's possible. If the maze consists of a single path in a loop, with those conditions, it is impossible. If it's possible to reach the centre, you meet there. If there is a single unique feature, you meet there.

Agreed. As such, no 1 should be reworded.

capn_slimes
Posts: 7
Joined: Sun Feb 06, 2011 4:07 am UTC

Re: Twins in a Maze

Postby capn_slimes » Sun Feb 06, 2011 4:10 am UTC

You all seem to be missing the 'shout really loudly where you are going' option...

d0nk3y_k0n9
Posts: 97
Joined: Sun May 03, 2009 4:27 pm UTC

Re: Twins in a Maze

Postby d0nk3y_k0n9 » Sun Feb 06, 2011 3:35 pm UTC

capn_slimes wrote:You all seem to be missing the 'shout really loudly where you are going' option...


That doesn't work... since both twins have to have the same way of acting and making decisions, if your strategy is to "Shout where you're going and go where the other guy says he'll be if you hear him," then you'll each either end up:

a) Not hearing each other and just going where you originally intended.
b) Both hearing each other and each going to where the other originally intended to.
c) One hearing and the other not and ending up at the same place.

Since the twins are identical and therefore would shout at the same volume and have the same ability to hear, we can rule out c) and thus, it wouldn't work.

capn_slimes
Posts: 7
Joined: Sun Feb 06, 2011 4:07 am UTC

Re: Twins in a Maze

Postby capn_slimes » Sun Feb 06, 2011 6:18 pm UTC

Spoiler:
d0nk3y_k0n9 wrote:That doesn't work... since both twins have to have the same way of acting and making decisions, if your strategy is to "Shout where you're going and go where the other guy says he'll be if you hear him," then you'll each either end up:

a) Not hearing each other and just going where you originally intended.
b) Both hearing each other and each going to where the other originally intended to.
c) One hearing and the other not and ending up at the same place.

Since the twins are identical and therefore would shout at the same volume and have the same ability to hear, we can rule out c) and thus, it wouldn't work.


Well, the first option would be 'head toward the sound'. That would at least remove the possibility of not meeting in a rotationally symmetric maze when they are not in diametrically opposed positions (as long as they are in earshot, obviously). For example, in a thin circular maze they could be 90 degrees apart and still not meet, unless they shouted. If they are 180 degrees apart, they're still screwed though. But I get your point. It's actually worthless for them to shout where they are going - just shouting is enough.

It just seems to me that a search algorithm should be based on maximising the probability of them perceiving each other rather than just meeting, and that perception doesn't have to be sight.

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Twins in a Maze

Postby balr » Sun Feb 06, 2011 7:16 pm UTC

The original rules state that: You cannot call out to one another, leave markings or a trail.

So shouting is ruled out.

But it is physically impossible, given the problem states that the twins are human, (the problem is posed for You and your identical twin) not to leave a trail. Again, the problem statements says: Time is not a factor. It must follow that there are water supplies, food caches, any medicines that I and my twin need, etc.

We will disturb those supplies and caches in using them. We will leave spoor. It would be physically impossible not to.

So the problem perhaps needs to be reframed: you and your twin are disturbing the caches and leaving spoor; but neither of you are intentionally leaving messages in those ways.

And that may lead to a more interesting question: can either of us deduce the other's whereabouts / break the symmetry by analysing the spoor and disturbances

capn_slimes
Posts: 7
Joined: Sun Feb 06, 2011 4:07 am UTC

Re: Twins in a Maze

Postby capn_slimes » Sun Feb 06, 2011 8:57 pm UTC

balr wrote:The original rules state that: You cannot call out to one another, leave markings or a trail.


I should really learn to read some time soon. :oops:

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Twins in a Maze

Postby quintopia » Thu Feb 10, 2011 1:00 am UTC

Given that both twins have an unbiased coin, the graph they are in is connected, then a working strategy is: decide on some method using the coin to pick directions uniformly at random to go at interesections, and use it at every intersection. With probability 1, the twins will meet eventually. (This is true no matter what method they come up with to convert coin flips to directions, but this fact is trivial and obvious.)

EDIT: Note that by intersections here, I meant to include the twin's starting position as well. In the perfect circle scenario, the twins will have no indication of whether or not they have returned to their starting point, so in undifferentiated mazes, they must stop and change directions every now and then. They can do so as often or as little as they like, and they will still eventually meet.

A more interesting problem is this: Given a particular graph, how long will it take them?
Relevant: http://www.sciencedirect.com/science?_o ... archtype=a
Last edited by quintopia on Thu Feb 10, 2011 1:06 am UTC, edited 1 time in total.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Twins in a Maze

Postby Yakk » Thu Feb 10, 2011 1:01 am UTC

quintopia wrote:Given that both twins have an unbiased coin, the graph they are in is connected, then a working strategy is: decide on some method using the coin to pick directions uniformly at random to go at interesections, and use it at every intersection. With probability 1, the twins will meet eventually. (This is true no matter what method they come up with to convert coin flips to directions, but this fact is trivial and obvious.)
And false. Well, true in non-degenerate cases.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Twins in a Maze

Postby quintopia » Thu Feb 10, 2011 1:07 am UTC

Yakk wrote:
quintopia wrote:Given that both twins have an unbiased coin, the graph they are in is connected, then a working strategy is: decide on some method using the coin to pick directions uniformly at random to go at interesections, and use it at every intersection. With probability 1, the twins will meet eventually. (This is true no matter what method they come up with to convert coin flips to directions, but this fact is trivial and obvious.)
And false. Well, true in non-degenerate cases.

Which cases?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Twins in a Maze

Postby Yakk » Thu Feb 10, 2011 1:07 am UTC

quintopia wrote:
Yakk wrote:
quintopia wrote:Given that both twins have an unbiased coin, the graph they are in is connected, then a working strategy is: decide on some method using the coin to pick directions uniformly at random to go at interesections, and use it at every intersection. With probability 1, the twins will meet eventually. (This is true no matter what method they come up with to convert coin flips to directions, but this fact is trivial and obvious.)
And false. Well, true in non-degenerate cases.

Which cases?

Turn right if it lands heads.
Turn right if it lands tails.

That is one of the degenerate cases. (it relies on quibbling about what uniformly at random means -- picking one direction with probability 1 is uniformly at random over that one direction -- which is pretty silly quibble).

Another, less ridiculously quibbly, degenerate case is a maze with no intersections at all. Just a loop.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Twins in a Maze

Postby quintopia » Thu Feb 10, 2011 1:12 am UTC

I covered the undifferentiated maze case in my edit which you posted before I could slip in. The other thing I agree is quite the splitting of hairs.

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Twins in a Maze

Postby t1mm01994 » Thu Feb 10, 2011 9:41 am UTC

as pointed out before:

bobleboffon3 wrote:
Spoiler:
The way I see it, for the twins not to be able to meet up somewhere, 3 conditions need to be there.

1) The maze must have [no uniquely identifiable point.]
2) The twins must have no way to differenciate each other/talk beforehand
3) The twins must have no way to figure out a random number/event

If any of these 3 conditions misses, they can do it.

It's not very hard to simulate a random event in my opinion. All they need is something ( they have food/water right? Or one of their shoe, or a hair, anything ) to throw on the ground and if it's this side of an imaginary line, they stand still for an hour, if it lands on the other side they move for an hour. If they don't meet, they try again with a day, then a week, then a month, and so on. They'll meet at some point.

If they have absolutely no way ( or are forbidden ) to use such tactic to figure out a random event, then won't meet up in a rotationnaly symmetrical maze, even with infinite time.

User avatar
EdgarJPublius
Official Propagandi.... Nifty Poster Guy
Posts: 3726
Joined: Tue Oct 09, 2007 4:56 am UTC
Location: where the wind takes me

Re: Twins in a Maze

Postby EdgarJPublius » Mon Feb 14, 2011 11:31 pm UTC

Hows this:
After mapping the maze, each twin should assign a unique number to each intersection (I don't think it should matter how this is done as long as each intersection has a unique number, each twin can give each intersection different numbers and this will still work)
Then, Each twin should choose an intersection, wait there for a reasonable amount of time based on the size of the maze, perform an exhaustive search of the maze and then choose another intersection (one which they have no visited before this cycle) and repeat the process. If they do this at every intersection without meeting their twin (shouldn't be possible except in some degenerate cases) repeat the process visiting each intersection in a different order.
Either each twin will eventually choose the same intersection, or one twin should be waiting during a period when the other twin is searching (assuming that at least two different orderings of the points will take different amounts of time to complete)

This should suffice for most possible, finite mazes with a few easily predictable exceptions (I.E. a maze with no intersections) which should be solvable using some other simple rule-set.

There is a solution for the circular maze with different drop points, but I'm out of time and having trouble thinking it all the way through. Basically, you perform an iterating, asymmetrical search and eventually each twin should end up at the same point at the same time, even if both twins use the same pattern.
Roosevelt wrote:
I wrote:Does Space Teddy Roosevelt wrestle Space Bears and fight the Space Spanish-American War with his band of Space-volunteers the Space Rough Riders?

Yes.

-still unaware of the origin and meaning of his own user-title

User avatar
cjdrum
Posts: 113
Joined: Sun Dec 12, 2010 4:51 am UTC
Location: BACK

Re: Twins in a Maze

Postby cjdrum » Tue Feb 15, 2011 1:03 am UTC

For a circular maze without intersections:
Spoiler:
Both would travel in the same direction, being twins.
They work out whether or not to walk based on a coin flip - Heads they walk 10 paces, Tails they wait for 10 seconds.
Eventually, one will see the other from behind, and will run to meet them (as they can't talk, right?), and they can leave.
More chance involved:
Spoiler:
If each had a 100-sided die, they could use that to determine how many paces they should walk.
if roll < 50:
----imagine walking 100 paces
----roll again
if roll >= 50:
----walk the amount of paces that you rolled
----roll again
I'm not sure how well these would work... But they should be fine. After all, they have infinite time.
:shock:

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Twins in a Maze

Postby t1mm01994 » Tue Feb 15, 2011 7:16 am UTC

EdgarJPublius wrote:-snip-
Then, Each twin should choose an intersection, wait there for a reasonable amount of time based on the size of the maze, perform an exhaustive search of the maze and then choose another intersection (one which they have no visited before this cycle) and repeat the process. If they do this at every intersection without meeting their twin (shouldn't be possible except in some degenerate cases) repeat the process visiting each intersection in a different order.
Either each twin will eventually choose the same intersection, or one twin should be waiting during a period when the other twin is searching (assuming that at least two different orderings of the points will take different amounts of time to complete)
-snip-

So, you haven't given them the random number, they can't talk on beforehand, but if the maze is exactly rotationally symmetric, your twins are screwed.

User avatar
EdgarJPublius
Official Propagandi.... Nifty Poster Guy
Posts: 3726
Joined: Tue Oct 09, 2007 4:56 am UTC
Location: where the wind takes me

Re: Twins in a Maze

Postby EdgarJPublius » Tue Feb 15, 2011 9:11 am UTC

Only under certain, degenerates cases which can be generalized to the featureless circle problem.

I think the featureless circle problem is solvable, at least in theory.
Each twin has a choice at any given moment to move clockwise, counter-clockwise or to stop and wait.
In the degenerate case, the twins tend to choose the same action at the same time and so can never meet.
However, the twins can choose to communicate in binary by making a complete clockwise circuit equal to 0, and a complete counter-clockwise circuit equal to 1. If the twins decide to send different messages, or to send the same message at different times, then they will meet, but once again, there's the degenerate case where both twins decide at the same time to send the same message.

However, since the twins will only not meet if they both decide to send the same message at the same time, then each twin can know what the other twins message was (it was the same as his own) In this way, the twins can communicate even while they are circling without ever meeting.
Then, in order to resolve the degenerate case, a message must be sent which will cause the twins to meet in some way, either by responding differently to a question, or by agreeing on a meeting place in some way.
Roosevelt wrote:
I wrote:Does Space Teddy Roosevelt wrestle Space Bears and fight the Space Spanish-American War with his band of Space-volunteers the Space Rough Riders?

Yes.

-still unaware of the origin and meaning of his own user-title

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Twins in a Maze

Postby Yakk » Tue Feb 15, 2011 12:39 pm UTC

Why would they respond differently to a message sent by the other twin?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 12 guests