Ants Revamped
June 14th, 2007
Please make sure you have read (and solved) the original Ants riddle before reading on!
Here are two sequel questions to the original Ants riddle:
- Which is the last ant to fall off the stick?
- What is the maximum number of ant collisions possible?
I want to thank Danny Valevsky for bringing these to my attention!
August 25th, 2007 at 4:31 pm
(Refering the 2nd Sequel).
Obviously, the outer ants, has at most 1 collision.
The second ant, has at most 3 collisions (colliding with the 3rd one, then with the 1st, then with the 3rd one again, and then falls).
But one of these collisions was already counted, giving 2 more collisions.
The third ant, has at most 5 collisions (4th,2nd,4th,2nd,4th,fall), giving 3 more collisions.
Eventually we’ll get that if the following initail state is used (face direction written):
R…RL…L
(with 50 R’s and 50 L’s)
This will cause 1+2+..+49+50+49+…+2+1=50^2=2500 collisions.
August 25th, 2007 at 6:15 pm
Nadav,
That is absolutely correct. Another (easier?) way to get 2500 relies on the original solution to the riddle. Instead of counting collisions for specific ants, I count collisions for “virtual ants” (the ghost ants in the solution of the original riddle). It is evident that each collision of the real ants is counted as a “pass-through” of the ghost ants. So given the arrangement R…RL…L there are obviously 50*50=2500 collisions.
The first sequel can be answered as follows. First, lets figure out which is the last ghost ant to fall of the stick. It is obviously the ant that is farthest away from the end of the stick its looking at. So all we have to do now is match this virtual ant to a real ant. That is easy. Say the last virtual ant will fall off the right side of the stick. We can count how many ants will fall of the right side (the number of virtual ants to fall off the right side is the same as the number of real ants to fall off the right side!). Say there are k ants that will fall of the right. Then the real ant to fall of the right is the ant that is k’th from the right! Its orientation is not relevant.
December 26th, 2007 at 3:05 pm
I would like to point out that this way you can easily determine the time of falling of any ant in the initial configuration. Suppose our ant is k’th from the right. According to what You said, we find k’th ant walking to the right, this is the matching “ghost ant”. We check her distance from the right edge – after passing this distance the k’th ant from the right will fall.
The same goes with the left side.