## Ants on a stick

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Zohar
COMMANDER PORN
Posts: 8533
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: Denver

### Ants on a stick

Doesn't sound very appetizing, does it?

Suppose you have a 1 meter long stick. On the stick are ants, randomly placed and facing left or right randomly. Each ant moves at 1 meter per second. Once two ants collide, they reverse directions. When an ant reaches the end of the stick, it falls off.

Find an upper limit for the time it takes for the stick to be clear of ants, regardless of the original setup.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:
solution wrote:1 second, supposing all the direction reversals are instantaneous.

This is because both ants reversing direction is equivalent, when the identity of each ant doesn't matter, to all the ants continuing in their original direction. So since they move at 1 meter per second and the stick is only a meter long, it will be clear of ants in one second.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Steve
Posts: 156
Joined: Sun Mar 25, 2007 1:39 am UTC
Location: University of Virginia
Contact:
And as long as a collision is guaranteed, the lower bound is 1 second as well I believe.
John Hancock

bbctol
Super Deluxe Forum Title of DESTINYâ„¢
Posts: 3137
Joined: Tue Mar 06, 2007 10:27 pm UTC
Location: The Twilight Zone
Contact:
When two ants slam into each other and change direction, it's the same as if they continued past each other. So at maximum, it will be free of ants in one second, as they travel at 1m per second (fast ants!).

SpitValve
Not a mod.
Posts: 5130
Joined: Tue Sep 26, 2006 9:51 am UTC
Location: Lower pork village
Do those solutions assume the ants don't have finite size?

fynch
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC
Contact:
Steve wrote:And as long as a collision is guaranteed, the lower bound is 1 second as well I believe.

The lower bound is instantaneous. What if an ant is randomly placed at the edge facing out?

Patashu
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:
How about solving it for a length of ants l and/or a time taken to reverse after a colission n?

Zohar
COMMANDER PORN
Posts: 8533
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: Denver
Yes, the ants have zero length. It's like that joke about the physicist who was asked to create an ideal horse racetrack. He begins by saying "assume a spherical horse with no legs".

BTW, even if a collision is guaranteed, 1 second isn't a lower bound (for example, a case where the ants start at 30 and 70 cm. of the stick, facing each other, each ant will travel 70 cm. overall, less than one second).
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

tendays
Posts: 957
Joined: Sat Feb 17, 2007 6:21 pm UTC
Location: HCMC
I'd say the lower bound (with at least one collision) is half a second - which is obtained by putting two ants facing each other at the middle of the stick.

You don't need zero-length ants and instantaneous u-turns for these to work - just say that the time needed for a u-turn is equal to the time needed for an ant to walk its own length.

fynch
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC
Contact:
I missed the collision guaranteed... In that case yes, .5 seconds...

Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:
Slight variation:

100 ants from the original problem are walking on a circle of circumference 1 meter. They're evenly spaced, 1cm (along the arc of the circle) apart from each other, in clockwise order, so that #2 is just clockwise from #1, #3 is just clockwise from #2, and #1 is just clockwise from #100, etc. At time t = 0, all prime-numbered ants (#2, #3, #5, #7, ... #97) are walking clockwise, while all other ants are walking counterclockwise. How far from its starting point is ant #1 at time t = 1 second?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
Cosmologicon wrote:Slight variation:

100 ants from the original problem are walking on a circle of circumference 1 meter. They're evenly spaced, 1cm (along the arc of the circle) apart from each other, in clockwise order, so that #2 is just clockwise from #1, #3 is just clockwise from #2, and #1 is just clockwise from #100, etc. At time t = 0, all prime-numbered ants (#2, #3, #5, #7, ... #97) are walking clockwise, while all other ants are walking counterclockwise. How far from its starting point is ant #1 at time t = 1 second?

solution wrote:As seen in the original problem, by modeling the collision of two ants as one walking through the other, we can conclude that after 1 second has elapsed, there will be an ant in each position that there is an ant at t = 0 seconds (though the new ant might be different from the old ant). Also, by this model, at any point in time, 25 ants are walking clockwise and 75 are walking counterclockwise (since there are 25 primes in the first 100 positive integers).

Since when two ants collide they turn around instead of actually passing through each other, ant a will always just clockwise from a-1 and just counterclockwise from ant a+1. After 1 second, ant 1 has shifted counterclockwise by x cm, for some (possibly negative) integer x (since it must occupy the original position of some other ant). Ant 2 must end up 1 cm clockwise from ant 1; since it started 1 cm clockwise from ant 1, it must have also traveled x cm counterclockwise after 1 second. By a simple induction argument, we can show that each ant has shifted counterclockwise by x cm after the one second has elapsed.

Since 75 ants are walking counterclockwise ant 25 ants are walking clockwise at each time t, the total velocity of all ants is 50 m/s counterclockwise at every time t. Thus, after one second has elapsed, the ants will in total have moved 50 m counterclockwise. Hence, each individual ant has moved 50 cm counterclockwise, and so each ant is at the point diametrically opposite from where it started. Specifically, ant 1 is 50 cm along the arc of the circle from where it started, or 1/pi m from its starting point as the crow(fly?) flies.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco
Cauchy wrote:Since 75 ants are walking counterclockwise ant 25 ants are walking clockwise at each time t, the total velocity of all ants is 50 m/s counterclockwise at every time t. Thus, after one second has elapsed, the ants will in total have moved 50 m counterclockwise. Hence, each individual ant has moved 50 cm counterclockwise, and so each ant is at the point diametrically opposite from where it started. Specifically, ant 1 is 50 cm along the arc of the circle from where it started, or 1/pi m from its starting point as the crow(fly?) flies.

Nice use of conservation of momentum. My solution was much more complicated, and was definitely the "wrong solution".
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Posts: 309
Joined: Tue Feb 27, 2007 2:27 am UTC
edit: don't mind me, I was wrong.

Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove
Original question, but when after ants collide, they move at half the speed they where moving at before the collision.

ptveite
Posts: 159
Joined: Tue Dec 12, 2006 3:15 pm UTC
Yakk wrote:Original question, but when after ants collide, they move at half the speed they where moving at before the collision.

How many ants are there? n ants seems like it could take as long as 2^(n-1) seconds

fynch
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC
Contact:
I was going to say, given enough ants it could go for a long time, unless you can show us otherwise.