wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> PLEASE HELP. Lemmings problem.
        
(Message started by: kookies on Dec 7^th, 2006, 6:53pm)

Title: PLEASE HELP. Lemmings problem.
Post by kookies on Dec 7^th, 2006, 6:53pm

Is it not simply 100 seconds?
I did 100 m / 1 m / s
is this correct?

Title: Re: PLEASE HELP. Lemmings problem.
Post by Whiskey Tango Foxtrot on Dec 7^th, 2006, 7:18pm

What if they bump into each other and reverse directions?

Title: Re: PLEASE HELP. Lemmings problem.
Post by Icarus on Dec 7^th, 2006, 7:28pm

For those who are wondering what this is about:

Lemming Drownings: (http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml#lemmingDrownings)

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?

And WTF brings up a valid point: Some lemmings are likely to reverse course several times because they keep bumping into others, covering the same length of board many times over. Only when you figure out how to account for this can you be sure you have the correct answer.

Title: Re: PLEASE HELP. Lemmings problem.
Post by flamingdragon on Dec 7^th, 2006, 8:26pm

So, has anyone figured out how to acount for it?

And I have an answer:

Hit the nuke button, maximun time=5 seconds. ;D

I used to love nuking all my lemmings, that was a fun game. ;D

Title: Re: PLEASE HELP. Lemmings problem.
Post by towr on Dec 8^th, 2006, 1:10am

Hint: [hide]all lemmings are equal, and none are more equal than others[/hide]

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 8^th, 2006, 2:40am

I think what towr is hinting at is that the process would look exactly the same if [hide]instead of "bouncing" off each other, the lemmings "slid" past each other.(Or think of each lemming holding a seed that they exchange on each bump and think about the journey each seed takes).[/hide]

[hide]Looking at it that way, you can just think of each lemming walking in one direction until it falls off. Obviously, the longest any can take is 100 minutes[/hide], which is the answer kookies would have got if they had used the correct units.

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 8^th, 2006, 2:44am

Follow on: describe the probability distribution of the time until the plank is empty.

Title: Re: PLEASE HELP. Lemmings problem.
Post by towr on Dec 8^th, 2006, 3:35am

on 12/08/06 at 02:44:38, Miles wrote:

Follow on: describe the probability distribution of the time until the plank is empty.

One description might be ugly..

Another, [hide][int]₀¹ max( x_1..20) d x_1..20[/hide] * 100 minutes

Title: Re: PLEASE HELP. Lemmings problem.
Post by kookies on Dec 8^th, 2006, 3:55am

Well see i used common sense
I pretended there was 2 lemmings
then 3.
I saw the MAXIMUM amount of time will ALWAYS be 100 seconds. All right. THanks guys.

Title: Re: PLEASE HELP. Lemmings problem.
Post by THUDandBLUNDER on Dec 8^th, 2006, 4:08am

on 12/08/06 at 03:55:54, kookies wrote:

I saw the MAXIMUM amount of time will ALWAYS be 100 seconds.

No, it will be 100 MINUTES.

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 8^th, 2006, 4:45am

If T is the time (in MINUTES ;)) until the plank clears, then for n lemmings p(T<t) is [hide](t/100)^n because each lemming must be t metres or less from the end of the plank it is facing for T to be <t[/hide].

This is an easy function to differentiate to get the prob density function for T. From this, the expected value of T is [hide]100n/(n+1)[/hide] which gives just over 95 minutes for 20 lemmings.

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 8^th, 2006, 4:52am

And the variance of T is [hide]100^2 * n / (n+1)^2 / (n+2) [/hide] which gives a st. dev. of T for 20 lemmings of 4.5 minutes.

Title: Re: PLEASE HELP. Lemmings problem.
Post by jollytall on Dec 8^th, 2006, 5:58am

The original riddle is so easy because when they meet they simply turn back and continue with the same speed. What if they turn back and continue with half speed?

Title: Re: PLEASE HELP. Lemmings problem.
Post by Grimbal on Dec 8^th, 2006, 6:00am

on 12/08/06 at 02:40:38, Miles wrote:

[hide](Or think of each lemming holding a seed that they exchange on each bump and think about the journey each seed takes).[/hide]

Hey, what is that disgusting thing about [hide]exchanging seeds[/hide]?

Anyway, one question remains: how long does it take for a lemming to drown?

Title: Re: PLEASE HELP. Lemmings problem.
Post by Icarus on Dec 8^th, 2006, 8:21pm

The seed idea is an alternate way of seeing why the collisions don't change the outcome. Instead of asking how long it takes for all the lemmings to fall off, ask how long it takes for all the seeds to fall off the plank. Since each seed falls off with a lemming, the last seed and the last lemming leave together. So the time is the same for both.

But unlike the lemmings, which are constantly turning around and covering the same territory over again, the seeds always move in the direction they started in. Whenever two lemmings meet, they exchange seeds. So if lemming A carries seed a to the right, and lemming B carries seed b to the left, and they meet, A leaves carrying seed b to the left, while B leaves carrying seed a to the right. Even though A, B change direction, the seed a continues moving right, and seed b continues to move left.

Since the seeds move in a straight line to the ends of the plank, the longest one can take is 100 minutes. Since the lemmings go over with the seeds, the longest one can take is also 100 minutes.

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 11^th, 2006, 2:01am

on 12/08/06 at 06:00:08, Grimbal wrote:

Hey, what is that disgusting thing about exchanging seeds?

The disgust is down to your perception :o. I wanted to choose something small that a lemming might realistically be carrying, and the idea of them exchanging seeds seemed suitably cute.

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 11^th, 2006, 7:35am

on 12/08/06 at 05:58:58, jollytall wrote:

The original riddle is so easy because when they meet they simply turn back and continue with the same speed. What if they turn back and continue with half speed?

Consider placing all the lemmings as close as possible to each other at one end of the plank, with the first ten from the end facing away from the end and the other ten facing the other way. Lemming number 11 will be involved in 19 bounces in quick succession (this is can be seen by sketching displacement-time plots and looking at the intersections, easiest if you consider the “no loss of speed” case first, but I think it carries over to the more general case possibly requiring a little care in the exact placing of the lemmings). So lemming 11 will end up travelling at a speed of (1-r)^19 where r is the proportional reduction of speed on each bounce, with pretty much the whole plank ahead of him (the other lemmings will either be busy dropping off the plank behind him or marching at progressively higher speeds ahead of him), and that will take him 100/(1-r)^19 minutes.

For the halving case (r = 0.5), this gives a time of 99.75 years (roughly 52 million minutes). Can anyone come up with an initial configuration that takes longer? (Come on, it’s just asking for someone to get it over the 100-year figure!).

Title: Re: PLEASE HELP. Lemmings problem.
Post by Miles on Dec 11^th, 2006, 7:38am

Sorry, 99.68 years if you properly allow for leap years.

Title: Re: PLEASE HELP. Lemmings problem.
Post by SMQ on Dec 11^th, 2006, 9:08am

on 12/11/06 at 07:35:16, Miles wrote:

Can anyone come up with an initial configuration that takes longer?

No. Using a method similar to the original solution it's simple to show that 19 collisions is the maximum possible, and we know from the original solution that the maximum possible total path length is the full length of the board, so no improvement in either speed or distance is possible.

--SMQ

Title: Re: PLEASE HELP. Lemmings problem.
Post by Grimbal on Dec 11^th, 2006, 9:52am

Hm... If the lemmings have different speeds, they could bounce into each other while walking in the same direction. Could it be used to add some more bounces?
And when it happens, will they both change direction? If so, it would be interesting to make it happen just before they fall off the ledge.

Title: Re: PLEASE HELP. Lemmings problem.
Post by jollytall on Dec 11^th, 2006, 10:22am

I agree with SMQ. If you look at the last one, he either falls down without one bounce (if goes the wrong way), or after one bounce (the one he bounced with will be slower than him, because that had at least one bounce before, so he cannoth be "caught"). Once the first fell down the second will become first and will fall down in one bounce. He could have before max two bounces, so the total number of bounces is max 3. And so on, No. 10 will fall down after max 19 bounces. No. 11 is already No. 10 from the other end.

And again the max way travelled is one length of the plank.

Title: Re: PLEASE HELP. Lemmings problem.
Post by rewolfe on Jun 6^th, 2009, 6:18pm

The trick is to notice that two lemmings bumping into each other and changing direction has exactly the same effect as the two lemmings passing each other at constant speed. So effectively each lemming walks in his original direction to the end of the board. Max 100 min.