Logic Puzzles

[alfonz1986]

@ClamSpam  No, you're sort of on the right lines but doubling the normal takeoff velocity is not whats required here. Also in the swimming pool case, ignore the buoyancy effect, or water density. I could pose it as: imagine yourself standing on a flat treadmill which was spinning at a velocity of 100mph backwards relative to the ground. If you had a handrail next to you, and pulled yourself forward at 10mph. Would the treadmill be able to stop you from doing that? (assume the friction in the wheels is negligible)

I'm really posing these questions to you guys because I regarded epic lemmings players as very logical people who come up with creative solutions to challenging problems. I was interested to see how you all faired at some tough physics/science puzzles.

EDIT: I dont know how the f*** to make it invisible http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

[Johannes]

Since we're getting close to solving the airplane puzzle, here's another involving Lemmings (credit goes to the amazing wu::riddles site).

Somewhere in Northern Eurasia, a group of 20 lemmings is planning a special group suicide this year. Each of the lemmings will be placed in a random position along a thin, 100 meter long plank of wood which is floating in the sea. Each lemming is equally likely to be facing either end of the plank. At time t=0, all the lemmings walk forward at a slow speed of 1 meter per minute. If a lemming bumps into another lemming, the two both reverse directions. If a lemming falls off the plank, he drowns. What is the longest time that must elapse till all the lemmings have drowned?

Hint: Minimal math is required if you make a certain, correct observation.
Edit: Extra credit for anyone who builds an appropriate lemmings level to test this out http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

[ccexplore]

Cool, this is one puzzle I don't remember ever hearing a similar puzzle before, so it's really a new one for me.

Here's my answer.  I feel this is a neat enough problem that I should give others a chance to solve on their own as well, hence spoilers:

All lemmings will have drowned by 100m / 1 m/s = 100 minutes.  Reason: suppose we give each lemming a shirt with a different number, and stipulate that whenever 2 lemmings bump into each other, in addition to both reversing their directions, they also exchange each other's shirts (instantaneously).  It should be obvious that this rule about shirts have no impact to their actual movements on the plank, and therefore is equivalent to the original situation.

Now imagine that given the same starting positions, facing directions, and shirt assignments, we now change the rule so that whenever 2 lemmings bump into teach other, they don't exchange shirts, and instead of reversing directions they just pass through each other.

Hmm...wait a minute.  They describe the exact same situation!  At every point in time, for each position in situation #1 that has a lemming, in situation #2 you also have a lemming in same position facing same direction, with same shirt color.

Now the answer should be obvious.

[edit: I made a minor edit about 10 seconds after initial posting, to correct a silly brainfart http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />]
[edit2: minor clarifications]

[Johannes]

Spot-on. Must have been too easy http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

I remember the first time I saw this puzzle, and I quickly filled a sheet of paper with some possible scenarios, without really getting anywhere except horrific formulas. The simple math hint gave me the little nudge in the right direction I needed to rethink the problem.

[ccexplore]

Part of it is I think because it's easy guess at the right answer when you consider small number of lemmings (or equivalently, starting arrangements where most lemmings drown almost immediately, leaving only a few that actually stays around for a while).  And

the symmetrical nature of how 2 lemmings interact with each other strongly suggests to me it's the key to why the answer should play out the way it does.  And with a little effort along that line of thought, I was able to come up with a really simple argument to illustrate the equivalences.

[alfonz1986]

Invis My gut instinct is 100m, so 100 minutes. I ran through a few possible scenarios in my head like 2 lemmings facing toward each other at x=0m and x=100m. They would meet at 50m and deflect, so time would be 100 minutes. 

EDIT: I didn't read your hints before coming to this conclusion http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" /> I will just read it now.

[ccexplore]

I'm really posing these questions to you guys because I regarded epic lemmings players as very logical people who come up with creative solutions to challenging problems. I was interested to see how you all faired at some tough physics/science puzzles.

It's nice to think that the skills translate across disciplines that directly, but from personal experience I don't think my adeptness at lemmings even translate to adeptness at other games like chess or even Sokoban that have strong mental components.

I think it's conceivable that given an "epic" lemmings player vs someone really bad at it, there is a higher chance that the former person has greater rate of success at correctly answering any given physics/science/math/logic puzzle than the latter.  But that's very different from comparing one individual's rate of success in one domain vs another.

There has also been relatively well-documented cases of puzzles that defy even otherwise highly competent people in fields of mathematics etc.  Like the http://en.wikipedia.org/wiki/Monty_Hall_problem" class="bbc_link" target="_blank">Monty Hall problem.

[alfonz1986]

Funny you mention the monty hall problem, I was just going to post that as the next puzzle - moving from physics to maths!  http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

[Clam]

Oh ok, I think I get the airplane puzzle now.

The conveyor belt pushes on the wheels, but this doesn't necessarily push the plane backwards since the wheels can just spin. So the conveyor belt is a complete red herring and the plane can just take off as normal (possibly with some extra wear on the tyres).

The tricky part here, which threw me off, is that if you have a plane sitting stationary on the conveyor belt, and then start the belt running, the plane will move backwards. But, once you start applying thrust (which comes from the engines/propellers and doesn't go through the wheels), this doesn't hold any more. If you replace the conveyor belt with something that imparts a force on the whole plane (like maybe a giant electromagnet? NOT wind force though, since that will generate lift), then the plane will need to be capable of doing twice its take-off speed.

[alfonz1986]

Good job  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />

The plane will take off just as normal (as proven by mythbusters) the only difference is that the wheels spin 2x as fast as they would if they were on a normal runway.

[Simon]

Alright. Does each puzzle appear to be solved and acknowledged? (plane, and 100 meter stick)

I have the following one, and for once, it's not one you will find on every riddle site. I knew the question for a while, and worked out the (surprisingly easy) proof today after giving it a proper shot, so it should be doable. I have no clue how easy this is for people who aren't used to tackling math problems, so I will give hints generously if necessary.


Consider the sequence (a_n) for n = 0, 1, 2, 3, 4, ..., with possible values only 0 and 1 for each a_n, constructed as follows:

• If n = 3k for some integer k, then a_n = 0.
• If n = 3k + 1 for an integer k, then a_n = 1.
• If n = 3k + 2 for an integer k, then a_n = a_k.

Thus, the sequence starts as follows: 0 1 0 0 1 1 0 1 0 0 1 0 0 1 ... The bold digits come from the third rule, there's nothing special to them. It's just to visualize the rule.

We define a triple to be any non-empty substring of the sequence (a_n) together with two repetitions of itself immediately following it. E.g. 101010 somewhere in the sequence is a triple, but 0010 is not, since the second repetition of 0 isn't immediately after the 00.

Show that there are no triples in the sequence (a_n). http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

-- Simon

[finlay]

OK... let's ignore the third digit in the sequence for now.
0 1 x 0 1 x 0 1 x 0 1 x 0 1 x 0 1 x 0 1 x
we can trivially conclude that there are no 2 digit triples by noting that for any n=3k or n=3k+1, a_n=a_n+3, whereas we need it to be equal to a_n+2. This would be true wherever you start... the three possible triplets are:
0 1  x 0  1 x
1 x  0 1  x 0
x 0  1 x  0 1
, all of which contain x 0 and 0 1 as one of their two digit segments, which are an invalid mismatch because 1≠0.

For three digit triplets, the possibilities are
01x 01x 01x
1x0 1x0 1x0
x01 x01 x01
Here we have to say that they're invalid because you never have the same x three times in a row, because the x's are in the same distribution as the sequence itself – ie there must be a 1 and a 0 at least every 3 digits. we can say the same thing about 1 digit triplets – you'll never get the same digit three times in a row because there can be a maximum of 2 1s or 0s in a row.

I'm sure there must be some kind of inductive proof at this point. For 4 digit triplets, for instance, the possibilities are
01x0 1x01 x01x
1x01 x01x 01x0
x01x 01x0 1x01
; here we can see that the sets 01x0 and 1x01 must occur in any 4 digit triplet sequence and are trivially a mismatch. similarly, for 5 digits, the sets that comprise any triple (in any order) are
01x01 x01x0 1x01x
ie there must be a substring that starts with 0 and one that starts with 1. We can similarly eliminate any n-digit triple where n=3a±1 for integer a

Um... yeah, and then... with n=3a triples, the x's in the sequence become important, but we know that they're in the same distribution as the main sequence, so an n=3a digit triple becomes equivalent to an n=a digit triple...

Something like that... I'm not very eloquent at maths.

[Simon]

Yes, this is it! You've made all the necessary observations and linked them together properly.

The only thing left to make it super-formally correct would be to organize the "something like that". However, this is minor work (only hard if one doesn't do maths regularly), the main work is finding the underlying idea, which you have.

-- Simon

[finlay]

It has been a while, yeah. I had a false start on a maths degree, which I didn't enjoy, so I mostly stay clear of it these days – but I still have a few of the basic techniques there. (I changed to a linguistics degree in 2007, and finished last year)

[ccexplore]

Yeah, I suspect those without a math background (or theoretical computer science, which is really just a branch of discrete math) will be at a slight disadvantage.  The structure of the sequence doesn't directly correspond to everyday experiences, even though it is quite elementary in terms of induction/recursion.

Here's a hint that I think might help, for those not used to the general reasoning of mathematical induction:

The 3k+2 part of the definition leads to this very special property about the sequence.  First, lay out the sequence in this special tabular format:

a0 a3 a6 a9 ...
a1 a4 a7 a10...
a2 a5 a8 a11...

Here's what it looks like from a0 to a29 for example:

0  0  0  0  0  0  0  0  0  0
1  1  1  1  1  1  1  1  1  1
0  1  0  0  1  1  0  1  0  0

The key is to notice that the recursive 3k+2 definition (which says a2 = a0, a5 = a1, a8 = a2, etc.) means that remarkably, the bottom row of numbers (a2, a5, a8, ...) is actually a copy of the original sequence of a0, a1, a2, ...

The tabular layout also helps with visualizing what happens when you try to layout a candidate triple, by observing what happens with an element, its first repeat, and its second repeat when laid out in this table (in particular, which horizontal rows each winds up at).