Re: Ants puzzle
- From: Ross <rmillika@xxxxxxxxxxx>
- Date: Tue, 4 Nov 2008 11:08:58 -0800 (PST)
On Nov 4, 10:18 am, nikl...@xxxxxxxxx wrote:
Pangolini sprinkles some ants onto the pole of length L meters. They
immediately start scampering along the pole in random directions. If
two ants run into each other then they both instantaneously reverse
their directions and are now moving away from each other. An ant can
change direction many times. Eventually, all of the ants will fall off
one or other end of the pole. If each ant travels at a speed of one 1m/
s, what is the maximum time until all ants have fallen off?
Answer>http://www.cs.cmu.edu/puzzle/solution9.pdf
Imagine that each ant carries a distinct flag as it scurries along.
Whe two ants meet they exchange flags. Thus the flags proceed
uniformly in one direction along the pole. The ants fall with the
flags and so it takes a maximum of L secs for all the flags (and the
ants) to fall into the buckets.
i have a few questions based on this puzzle.
Suppose there are n ants on pole of length L , 2n<L.
The ants from left to right has speeds 1,2,3,4,...n m/s. what is the
maximum time until all ants have fallen off ?
There are only a few cases to check. First is if all the ants start
going right and number 1 is at the left end of the stick, it travels
for L seconds. All the high speed ants are problems and need to be
sent off the right end. The other possibilities to check are
1) Can ant 1 just bounce off ant 2 and travel further than L? If 2
starts at the right end and goes left, they will meet at L/3 and fall
off at 2L/3, worse
2) Can ant 1 bounce off 2 after 2 bounces off 3? If 1 and 2 start at
the left and 3 starts on the right, 2 and 3 meet at 2L/5 and they all
fall too early. So I suspect the general solution is for ant 1 to
traverse the whole length of the bar, taking L seconds.
What if the speeds are v1,v2,v3...vn ?
a) v1<v2<v3<...<vn
b) v1<v2<v3..<vi > ...vj > ....>vn
How do we formulate this question so that i can get an answer ? Any
elegant ways of formulating this question.
Again I would bet on letting the slowest ant walk the whole length of
the bar
.
- Follow-Ups:
- Re: Ants puzzle
- From: James Waldby
- Re: Ants puzzle
- References:
- Ants puzzle
- From: niklaus
- Ants puzzle
- Prev by Date: Re: "I only truly understood this material when I started teaching it."
- Next by Date: Re: Is one-to-one mapping valid for comparing infinite-sized sets?
- Previous by thread: Ants puzzle
- Next by thread: Re: Ants puzzle
- Index(es):
Relevant Pages
|
