Help with *Ants riddle*

Discussion in 'Off-Topic' started by EngIntoHW, Sep 5, 2010.

  1. EngIntoHW

    Thread Starter Member

    Apr 24, 2010
    128
    0
    Hey, I read about this riddle but I just can't prove the answer for this riddle (I saw the answer for this, but as said, can't prove it).

    There are 100 ants on a board that is 1 meter long, each facing either left or right and walking at a pace of 1 meter per minute.
    The board is so narrow that the ants cannot pass each other; when two ants walk into each other, they each instantly turn around and continue walking in the opposite direction. When an ant reaches the end of the board, it falls off the edge.
    From the moment the ants start walking, what is the longest amount of time that could pass before all the ants have fallen off the plank? You can assume that each ant has infinitely small length.

    Help me please :)
     
  2. Markd77

    Senior Member

    Sep 7, 2009
    2,803
    594
    I think a minute, the time it takes for an ant to walk from 1 end to the other. All the other possibilities I can think of take less time.
     
  3. jpanhalt

    AAC Fanatic!

    Jan 18, 2008
    5,692
    901
    I agree, 1 minute. Such puzzles are often solved by starting at the end and working forward. You can look at fewer ants, say 10, and get to the same answer. John

    Edit: That advice came from Martin Gardner (http://en.wikipedia.org/wiki/Martin_gardner). I read his column in Scientific American for years.
     
    Last edited: Sep 5, 2010
  4. atferrari

    AAC Fanatic!

    Jan 6, 2004
    2,648
    763
    Hola John,

    You say "starting at the end".

    Do you always know what the end actually is?
     
  5. jpanhalt

    AAC Fanatic!

    Jan 18, 2008
    5,692
    901
    "Depends what you mean by 'know.'" (Bill Clinton)

    I considered changing my comment to starting at the/a final condition and working forward. Gardner presented an interesting puzzle involving pirates killing each other that was solved that way. In the Gardner puzzle, there clearly was a final condition. In this case, "final condition" is not the best word to describe the process, which is why I didn't change my post. The principle is the same though.

    Start with a very simple, final situation (even if it is hypothetical), say just one ant. Then consider two, three, four, etc. You will find that the longest time is 1 minute and adding more ants doesn't change that. I didn't work it out to the full 100 ants, because the pattern and the reason the time didn't change seemed obvious.

    Of course, if that is the wrong answer, I now have a lot of retraction to do.

    John
     
    Last edited: Sep 6, 2010
  6. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Nice solution! It seems correct to me. I see no reason why your approach can't be cast into a formal proof by induction.
     
  7. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    I think this is a nice little gem of a problem.

    Using jpanhalts approach, the answer is clear, and a method of proof can be structured much more easily from that viewpoint.

    In doing that, I noticed an interesting "law of physics" that can be established for the little ants that live in this "plank-world". One way to do a proof is to first prove the law, and then prove the answer using the law.

    This law works for the initial conditions, or for any time later until all the ants fall off the plank. It also works for any number of initial ants. This law can be used to make a trivially simple proof of the answer, but of course, proving the law itself is a necessary first step, and not quite as easy.

    The law is as follows:

    "At any given time, the remaining time it takes for any one of the ants to fall off the plank will be one of the times established by all the ant positions and directions according to the formula time=distance/speed, where distance is the distance to the end of the plank in the direction of walking and speed is the constant speed that all ants walk at."

    What this means is that for every ant, we can establish a time equal to the distance to the end of the plank (in the facing direction) divided by the speed. This time will not necessarily be the time it takes for that ant to fall off (although it could be), but one of the ants will fall off at that time. This means that we can quickly make a table of the times that the various ants fall off, even if we are not sure which ants are destined to fall off at any of those times.

    Hence, not only can we know the time it takes for all ants to fall off the plank, given any particular number, locations and directions of ants, but we can also state that the maximum time for all arrangements will only occur when one of the ants is at one end of the board and facing inward. In such a case the maximum time is one minute for a 1 meter board and 1 m/min speed.
     
  8. Markd77

    Senior Member

    Sep 7, 2009
    2,803
    594
    I wonder what the average time would be if all the ants were positioned randomly. My intuition says it would be slightly over 30 seconds, maybe 40.
     
  9. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    I'd go for the maximum time. All the ants on one end or the other. Two meet in the middle, then off the edge. Total maximum distance, 1½ meters. It can be shorter, but never longer.
     
  10. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Maximum distance is 1 meter not 1.5 meters.

    This is clear from the 1'st law of ant physics stated above.

    The law is clear from a symmetry argument. When two ants meet and change directions, they are actualy indistiguishable from the case where they just pass by each other. Hence, the starting distance from the end determines the time and distance. The maximum distance is 1 meter and maximum time is 1 minute.

    The time is completely dictated by the ant which is furthest from the end, in the direction he is facing. If you consider the case of one ant only, I think the answer is 30 seconds, but if there are more ants, I think the time goes up depending on the number of ants. If there are an infinite number of ants, I think the answer will be 60 seconds because there is bound to be at least one ant very close to one end facing inward.

    For the case of 100 ants, your guess in the 30-40 second range seems reasonable, but my guess would be 40-50 seconds. It shouldn't be hard to check with a calculation or a computer experiment using a random number generator. This could make a good guessing game like the one where you have to guess the number of jelly beans in a jar. The person who guesses correct to the nearest second is the winner.
     
  11. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    I have a feeling that my above posts are needlessly confusing. Let me say something equivalent which reveals the simplicity of the problem.

    This problem is equivalent to the same problem where we replace the statement that "The board is so narrow that the ants cannot pass each other; when two ants walk into each other, they each instantly turn around and continue walking in the opposite direction. " with the statement that "Each ant travels in its own lane unimpeded".

    As long as you don't care which ant is falling off the end of the board at a particular time, the two problems are equivalent. This is assuming that all ants are indistiguishable in that they look the same and act the same. It should be clear that if two ants meet and instantly turn around, it's the same as if they pass each other, and keep walking in the same direction.

    Once you know this, then determining times and distances is trivial.

    I love this problem. It seems complex at first, and then becomes trivial with some thought.
     
  12. jpanhalt

    AAC Fanatic!

    Jan 18, 2008
    5,692
    901
    Yes

    I think the mean of a large number of trials will be 30 seconds, if the beginning distributions are random. The standard deviation around that mean will depend on the starting number of ants. That opinion comes directly from the symmetry argument.

    John
     
  13. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    I think the time for the average ant will be 30 seconds, but when there are many ants on the board and we care about when the last ant falls, the average is not relevant. Only the maximum time for that last ant is relevant. If we look at a random distribution of 100 ants on the board, odds are that one of the ants will have to travel more than 0.5 meters in every sample case considered. This ensures that the time for all ants to fall should be greater than 30 seconds. A case with with 100 ants requiring less than 30 seconds for all ants to fall is less probable than flipping a coin and getting 100 heads in a row.

    The case of 1 ant is simple. The ant will have to travel anywhere from 0 to 1 meter with an average value of 0.5 meters (hence 30 seconds). However with a large number of ants, the average doesn't matter because it is the time for the last ant to fall that matters. I feel that as the number of ants goes to infinity, the time for the last ant to fall goes to 60 seconds because there is bound to be an ant starting near the end of the board and facing the wrong way.
     
    vvkannan likes this.
  14. Markd77

    Senior Member

    Sep 7, 2009
    2,803
    594
    It all makes sense now, I was imagining them all bouncing off each other in the middle and then roughly all heading to the edge. I see now that only the ant nearest the edge that is heading inwards matters.
    Excellent proof steveb!
     
  15. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Thank you for the complement Markd77, but note that I was inspired by jpanhalt's insight.

    Looks like I underestimated the time for a random distribution of 100 ants. I wrote a little Matlab program to do a simulation. I show the code at the bottom, but the answers are as follows for randomized initial condtions.

    1 ant = 30 seconds
    2 ants = 40 seconds
    10 ants = 55 seconds
    100 ants = 59.4 seconds
    1000 ants = 59.94 seconds

    Code ( (Unknown Language)):
    1.  
    2. [FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]clear[/SIZE][/FONT]
    3. [SIZE=2][FONT=Courier New]Ntrials = 10000; [/FONT][/SIZE][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22]% Specify the number of trials[/COLOR][/SIZE][/FONT]
    4.  
    5. [SIZE=2][FONT=Courier New][COLOR=#228b22]% Specify the number of ants[/COLOR][/FONT][/SIZE]
    6. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]Nants = 1000; [/SIZE][/FONT]
    7.  
    8. [/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22]% For each trial, with trial specified as column,[/COLOR][/SIZE][/FONT]
    9. [SIZE=2][FONT=Courier New][COLOR=#228b22]% generate a column vector of length Nants, [/COLOR][/FONT][/SIZE]
    10. [SIZE=2][FONT=Courier New][COLOR=#228b22]% with random numbers between 0 and 1,[/COLOR][/FONT][/SIZE]
    11. [SIZE=2][FONT=Courier New][COLOR=#228b22]% with uniform probability distribution.[/COLOR][/FONT][/SIZE]
    12.  
    13. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]x=rand(Nants,Ntrials); [/SIZE][/FONT]
    14.  
    15. [/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22]% use loops to find maximums[/COLOR][/SIZE][/FONT]
    16. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff]for[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2] jj = 1:Ntrials[/SIZE][/FONT]
    17. [SIZE=2][FONT=Courier New] time(jj) = x(1,jj);[/FONT][/SIZE]
    18. [/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff] for[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2] ii = 1:Nants[/SIZE][/FONT]
    19. [/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff]     if[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2] x(ii,jj) > time(jj)[/SIZE][/FONT]
    20. [SIZE=2][FONT=Courier New]         time(jj) = x(ii,jj); [/FONT][/SIZE][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22]% time for last ant to fall in each trial[/COLOR][/SIZE][/FONT]
    21. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff]     end[/COLOR][/SIZE][/FONT]
    22. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff] end[/COLOR][/SIZE][/FONT]
    23. [SIZE=2][FONT=Courier New][COLOR=#0000ff]end[/COLOR][/FONT][/SIZE]
    24. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]Tavr = sum(time)/Ntrials*60 [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22][FONT=Courier New][SIZE=2][COLOR=#228b22]%average time in seconds[/COLOR][/SIZE][/FONT]
    25. [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/SIZE][/FONT][/SIZE][/FONT]
    26. [/SIZE][/FONT][/SIZE][/FONT][/SIZE][/FONT][/SIZE][/FONT]
     
    Last edited: Sep 7, 2010
  16. jpanhalt

    AAC Fanatic!

    Jan 18, 2008
    5,692
    901
    Opps, I was talking the the average ant. In considering what is the average time for the last ant, I get the same answer. That is, 30 seconds.

    I think we can agree that the board can be represented simply as a time dimension, as shown here:

    [​IMG]

    An ant at either end has a 50:50 probability of taking a minute to drop or "zero time" to drop. (I am not entirely comfortable with "zero time," but this is just a puzzle.) Thus, we get the longest time is 60 seconds; the shortest is "zero"; and the average is 30 seconds. The times for an ant to drop starting at a few other locations is also shown. In each case, the average time is still 30 seconds.

    Now, look at other distributions. For example, if all of the ants were on the right half, randomly half would go left and take more than 30 seconds (i.e., 30 to 60 seconds) to drop and half would go right and take less than 30 seconds (i.e., 0 to 30 seconds) to drop. The average time for all of them to have dropped is still 30 seconds, the last ant must have dropped at an average of 30 seconds too. That is, it ain't over 'till the last ant drops. And, if that "average last ant" drops before the rest drop, then it ain't the last ant.

    John

    Edit: I started this response upon seeing response #13. I will have to think about the intervening comments some more.

    John
     
    Last edited: Sep 7, 2010
  17. jpanhalt

    AAC Fanatic!

    Jan 18, 2008
    5,692
    901
    @steveb,

    I concede. I see your point.

    If you consider that a "zero" dimension for the ants allows more than one to be at any spot, does that change your analysis? The rule only says they can't cross. It doesn't say they can't occupy the same initial spot. John
     
  18. Markd77

    Senior Member

    Sep 7, 2009
    2,803
    594
    Ah, but if they are infinitesimally small and you randomly place a finite number of them on a non quantized space there is zero chance that they will be in the same place.
    :) :)
     
  19. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469

    That's an interesting question. If they start at the same point facing in opposite directions there is no problem because they will immediately separate. If they start at the same point facing in the same direction I still think it is ok if we make a rule that two ants (or more) hitting a single ant (or more) behaves as if all ants just pass each other without touching or changing direction.
     
Loading...