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.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ What's the turning speed? $\endgroup$
    – Kendall Frey
    Commented Jun 26, 2014 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
    Commented Jun 26, 2014 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
    Commented Jun 26, 2014 at 15:05
  • $\begingroup$ What type of world do these "ants" live in? Discrete / Continuous $\endgroup$
    – Adam Speight
    Commented Jun 26, 2014 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
    Commented Jun 26, 2014 at 21:09

1 Answer 1

Reset to default
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$

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 26, 2014 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
    Commented Jun 27, 2014 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
    Commented Jun 28, 2014 at 13:27

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.