5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What's the turning speed? $\endgroup$ – Kendall Frey Jun 26 '14 at 14:33
  • $\begingroup$ 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. $\endgroup$ – justhalf Jun 26 '14 at 14:35
  • $\begingroup$ @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. $\endgroup$ – MrHen Jun 26 '14 at 15:05
  • $\begingroup$ What type of world do these "ants" live in? Discrete / Continuous $\endgroup$ – Adam Speight Jun 26 '14 at 15:28
  • 1
    $\begingroup$ 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. $\endgroup$ – MrHen Jun 26 '14 at 21:09
7
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ If an ant is at one end, and all the other ants are coming toward it, it will have to 'pass' them all. $\endgroup$ – Kendall Frey Jun 26 '14 at 15:38
  • $\begingroup$ 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). $\endgroup$ – Dennis Jaheruddin Jun 27 '14 at 8:01
  • 1
    $\begingroup$ @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. $\endgroup$ – justhalf Jun 28 '14 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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