35
$\begingroup$

Suppose there are $n$ ants on a stick which has length 1. At any time, the ants may be facing left or right, the initial directions of the ants are arbitrary. Each ant can be modeled as a point in the stick.

At time 0, all ants start moving in the direction they're facing at speed 1.

Each time an ant collides with another ant, both ants reverse direction instantly and continue moving in the new direction.

If an ant reaches the ends of the stick, it falls down (quite a strange species of ant).

Now, you are observing this stick full of ants, starting at time 0. You are very interested of one ant, which appears in a distinct color from the other ants, so you focus your eyes just on that particular ant.

What is the maximum time you'll be watching that particular ant until it falls off the stick?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What about this situation > ant going right, < ant going left.. >>>>><<<<< $\endgroup$
    – Adam Speight
    Commented Jun 26, 2014 at 13:55
  • $\begingroup$ @AdamSpeight you can run the simulation and see for yourself :) $\endgroup$
    – Tallmaris
    Commented Jun 26, 2014 at 14:11
  • 1
    $\begingroup$ @AdamSpeight: That sort of confusion is what makes this riddle interesting, and as Tallmaris said, try it! =) $\endgroup$
    – justhalf
    Commented Jun 26, 2014 at 14:21
  • $\begingroup$ @justhalf I did below $\endgroup$
    – Adam Speight
    Commented Jun 26, 2014 at 14:23
  • $\begingroup$ I added a follow-up question that changes the turning speed to 1. Not sure how this site feels about things like this but, hey, here it is: puzzling.stackexchange.com/questions/1790/… $\endgroup$
    – MrHen
    Commented Jun 26, 2014 at 14:32

3 Answers 3

Reset to default
40
$\begingroup$

And the answer is:

Surprisingly, it's 1, that is, it's the same as if nothing happens when the ants collide, and this doesn't depend on $n$.

Explanation:

The phrase that says you're watching a particular ant is just a distraction so that people will think that there is complexity in this riddle, while in fact it's very simple. When two ants collide and each reverses its direction, position-wise it's the same as if each ant simply continues moving in the original direction. So the maximum time is when there is an ant at on end of a stick facing the other end. Since the maximum time an ant can be in the stick is 1 (from one end to the other), therefore by time 1 all ants will already fall off the stick, including the particular ant that you're watching.

Alternative explanation:

Imagine that each ant holds a number, and when two ants collide (and reverse their directions), they will exchange the number. Now the crucial observation is: the numbers will never change its direction. So the maximum time a number can be on the stick is 1 (the numbers are always moving on the same direction with the same speed). So by the time 1, all numbers will have fallen down. Since every number is held by an ant, when there is no number, there is no ant either. Therefore by the time 1, all ants will have already fallen from the stick, including the particular ant you are watching.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think this is the right answer, but as it is not explicitly mentioned that the point where the ant is has nonzero width, one could adjust the solution for that case. The solution you give should then be reduced with the size of the ant in question. $\endgroup$
    – Dennis Jaheruddin
    Commented Jun 26, 2014 at 22:11
  • 4
    $\begingroup$ Hmm, I thought the concept of point already convey dimensionless entity? Point is defined as "that which has no part". At either case, even if the ant has width, it doesn't change the answer, consider the case where there is only one ant at the end of the stick facing the other. The ant width is irrelevant, if we assume the point to represent the ant's location (and to determine when it would fall) is the middle of the ant. $\endgroup$
    – justhalf
    Commented Jun 27, 2014 at 1:02
  • $\begingroup$ To complete the answer, note that the given maximum is also possible. It happens when your very special ant starts from the left end and all ants are moving right. $\endgroup$
    – Florian F
    Commented Oct 12, 2022 at 7:12
  • $\begingroup$ @FlorianF this isn't sufficient? "So the maximum time is when there is an ant at on end of a stick facing the other end. Since the maximum time an ant can be in the stick is 1 (from one end to the other),". But yeah, I guess I can be more explicit about it. An easy example is to just have one ant. $\endgroup$
    – justhalf
    Commented Oct 12, 2022 at 17:27
  • $\begingroup$ What is asked is the maximum, i.e the highest value among all the possible starting situations. Just showing the value cannot be exceeded is an upper bound. $\endgroup$
    – Florian F
    Commented Oct 12, 2022 at 17:46
11
$\begingroup$

@justhalf is correct but here is a visual aid. The spots on the stick are labeled 0-9 and ants facing right are > and ants facing left are <.

0123456789
>        <
 >      <
  >    <
   >  <
    ><
    <>
   <  >
  <    >
 <      >
<        >

Note that the ants appear to "pass through" each other which was @justhalf's point. Two ants colliding mean they have each traveled half of the distance between them. They then turn around and walk back over that exact same distance. There will never be a case where an ant will have to walk past 5 to get to another ant and collide and, once it does, it will only have 5 more spaces to walk before it falls off of the stick.

Here is another example with three ants:

0123456789
> >      <
 > >    < 
  > >  <   
   > ><    
    ><>    
    <> >  
   <  > > 
  <    > >
 <      > 
<        >

The ant that starts at 0 still turns around at the same spot and it still looks like the ants just walk through each other. It doesn't matter how many ants are added to the stick, the most one ant will ever have to travel is 10 spaces.

Improve this answer
$\endgroup$
1
2
$\begingroup$

The answer is N, the length of the stick (which is 1 in this question).

The complexity is that you're being distracted by the fact that they're bumping into each other while in reality nothing happens.

So you'd have to look for the maximum distance an ant has to travel for it to fall off, which would be on either sides of the stick.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By N I'm sure it means the length of the stick, right? $\endgroup$
    – justhalf
    Commented Jun 26, 2014 at 15:27
  • $\begingroup$ The stick has length 1. Not n, which is the number of ants. $\endgroup$
    – smci
    Commented Nov 3, 2014 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.