5

This question is purely a follow-up to Maximum time for ants to fall off stick.

Suppose there are $n$ ants on a stick which has length 10. At any time, the ants may be facing left or right, the initial directions of the ants are arbitrary.

At time 0, all ants start moving in the direction they're facing at speed 1. If an ant reaches the ends of the stick, it falls down (still quite a strange species of ant).

Each time an ant collides with another ant, both ants reverse direction in one unit of time and then continue moving in the new direction.

What is the maximum time an ant can stay on the stick before it falls off?

Clarification regarding ant collisions:

If $X$ encounters $Y$ and $Z$ in the middle of a colliding turn, then $X$ will turn around and leave in 1 time. $Y$ will finish its turn in 0.5 time and then turn around to face $Z$ again. This will take an additional 1 time. $Z$ will finish its turn in 0.5 time and continue on its way.

This makes intuitive sense, by the way, when you remember that $X$ will still be turning when $Y$ finishes its first turn. It couldn't move forward because the path is blocked.

Community
  • 1
MrHen
  • 251
  • 1
  • 6
  • 1
    What's the turning speed? – Kendall Frey Jun 26 '14 at 14:33
  • Probably you can better rephrase it as "both ants reverse direction in one unit of time". Reverse "at speed 1" doesn't make sense. And you also need to change the formulation into turn based, otherwise, you haven't defined what would happen if an ant crashes another ant while turning. – justhalf Jun 26 '14 at 14:35
  • @justhalf: I updated the turning speed note. An ant crashing into another ant while turning would reverse the direction of both ants. The ant already turning would need to finish its turn first and then start its second turn. – MrHen Jun 26 '14 at 15:05
  • What type of world do these "ants" live in? Discrete / Continuous – Adam Speight Jun 26 '14 at 15:28
  • Are all the ants facing the same direction? Or can each ant be facing a different direction? – Adam Speight Jun 26 '14 at 15:36
  • If the ants are not facing towards the end of the stick, how did they turn around without falling off the stick? – Adam Speight Jun 26 '14 at 15:38
  • @AdamSpeight Ants move continuously. The starting position of ants can be any orientation. – MrHen Jun 26 '14 at 18:20
  • What happens if 2 ants met and 3-rd ant meets them... let's say 0.5 time before they must diverge? – klm123 Jun 26 '14 at 21:04
  • If $X$ encounters $Y$ and $Z$ in the middle of a colliding turn, then $X$ will turn around and leave in 1 time. $Y$ will finish its turn in 0.5 time and then turn around to face $Z$ again. This will take an additional 1 time. $Z$ will finish its turn in 0.5 time and continue on its way. – MrHen Jun 26 '14 at 21:08
  • 1
    This makes intuitive sense, by the way, when you remember that $X$ will still be turning when $Y$ finishes its first turn. It couldn't move forward because the path is blocked. – MrHen Jun 26 '14 at 21:09
  • I think you need to include that clarification in the question. – justhalf Jun 27 '14 at 07:32
  • @justhalf: Done. – MrHen Jun 27 '14 at 17:32

1 Answers1

7

The ants-passing-each-other trick still works, with the additional condition that it takes a non-zero amount of time for two ants to pass.

Assuming the passing delay is 1 time unit, the maximum time on the stick is equal to the time to traverse the stick plus the time to pass all the other ants.

Where $t$ is time, $l$ is the length of the stick, $v$ is the speed of the ants, and $n$ is the number of ants:

$t_{max}=\frac{l}{v}+(n-1)t_{pass}$

Plug in some values (I'll take 10 for $n$ and assume 1 for $t_{pass}$):

$19=\frac{10}{1}+(10-1)1$

Kendall Frey
  • 3,383
  • 23
  • 27
  • If an ant is at one end, and all the other ants are coming toward it, it will have to 'pass' them all. – Kendall Frey Jun 26 '14 at 15:38
  • Yet if an ant is at one end, it will just turn once and then keep walking. I would guess the maximum amount of ants to be passed may be somewhere between n/2 and 2Log(n/2). – Dennis Jaheruddin Jun 27 '14 at 08:01
  • 1
    @DennisJaheruddin: If we have n=2m and the m-leftmost ants facing right, and m-rightmost ants facing left, the middle two ants will turn n-1 times. – justhalf Jun 28 '14 at 13:27