Ants on a stick

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Ants on a stick

Postby Zohar » Sun Apr 29, 2007 6:52 pm UTC

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

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Postby gmalivuk » Sun Apr 29, 2007 7:14 pm UTC

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)

User avatar
Steve
Posts: 156
Joined: Sun Mar 25, 2007 1:39 am UTC
Location: University of Virginia
Contact:

Postby Steve » Sun Apr 29, 2007 8:53 pm UTC

And as long as a collision is guaranteed, the lower bound is 1 second as well I believe.
John Hancock

User avatar
bbctol
Super Deluxe Forum Title of DESTINYâ„¢
Posts: 3137
Joined: Tue Mar 06, 2007 10:27 pm UTC
Location: The Twilight Zone
Contact:

Postby bbctol » Sun Apr 29, 2007 9:02 pm UTC

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!).

User avatar
SpitValve
Not a mod.
Posts: 5130
Joined: Tue Sep 26, 2006 9:51 am UTC
Location: Lower pork village

Postby SpitValve » Sun Apr 29, 2007 9:37 pm UTC

Do those solutions assume the ants don't have finite size?

User avatar
fynch
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC
Contact:

Postby fynch » Sun Apr 29, 2007 9:44 pm UTC

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?


User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Postby Patashu » Sun Apr 29, 2007 9:55 pm UTC

How about solving it for a length of ants l and/or a time taken to reverse after a colission n?

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

Postby Zohar » Sun Apr 29, 2007 9:58 pm UTC

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

User avatar
tendays
Posts: 957
Joined: Sat Feb 17, 2007 6:21 pm UTC
Location: HCMC

Postby tendays » Sun Apr 29, 2007 10:22 pm UTC

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.

User avatar
fynch
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC
Contact:

Postby fynch » Sun Apr 29, 2007 11:05 pm UTC

I missed the collision guaranteed... In that case yes, .5 seconds...

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

Postby Cosmologicon » Mon Apr 30, 2007 12:31 am UTC

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

Postby Cauchy » Mon Apr 30, 2007 1:09 am 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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby skeptical scientist » Mon Apr 30, 2007 6:25 am UTC

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

Shadowfish
Posts: 309
Joined: Tue Feb 27, 2007 2:27 am UTC

Postby Shadowfish » Mon Apr 30, 2007 8:50 pm UTC

edit: don't mind me, I was wrong.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Yakk » Mon Apr 30, 2007 9:01 pm UTC

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

Postby ptveite » Tue May 01, 2007 4:39 am 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

User avatar
fynch
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC
Contact:

Postby fynch » Thu May 03, 2007 12:46 am UTC

I was going to say, given enough ants it could go for a long time, unless you can show us otherwise.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 14 guests