Walking Ant Problem - Part 2

Source: Original problem adapted from the "Ants Problem" (Link removed) at "CMU ACM Programming Contest" . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle . Problem also available at J. Paulson Programming Blog

Problem:


You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction.

Walking Ants Puzzle earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off?

The new problem is :
Given the starting positions and directions of all the ants, which ant(s) are the last to fall off?

Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve.

( Readers Please ignore: Technorati claim: 6QVZ8YSY6XSD )

 Update (24 June 2014):
Solution: Posted by Strilanc and me in comments!

Comments

  1. vijay11:22 AM, August 17, 2013

    We can come up with a solution by DP Recurrence relation.

    ReplyDelete
  2. Stainless...11:23 AM, August 17, 2013

    First, to find out what time does it take for last ant to fall, consider collision as just passage and solve. It should give you time of an ant that falls last. Second, to find which one, count the number of ants in front of it which are walking in opposite direction Say k . The k'th ant in front of it is the last one to fall.

    To know how, draw all ants on a line, on x-axis. Draw lines from each ant with 45d angle in initial direction. Count number of collision that line will have (say k). After separating collisions, it is obviously k'th ant line which is longest.

    ReplyDelete
    Replies
    1. Pratik Poddar1:16 PM, June 24, 2014

      Ameya, The solution is not very clear to me. How would intersections give us which ant goes down last. Look at the solution in my comment. Its awesome.

      Delete
  3. Strilanc12:41 PM, August 17, 2013

    If there are L ants initially moving left and R ants initially moving right then, at the end, L will have fallen off the left side and R off the right side.

    Since ants never walk over each other, the L that fell off the left must the the first L from the left. The last one that fell off to the left is the L'th ant. The next ant is the one that fell off to the right.

    Therefore the last ant to fall off is the L'th or (L+1)'th ant.

    If the leftmost ant is closer to its edge than the rightmost ant to its edge, then the (L+1)'th ant is last. Vice versa it's the L'th ant. In a tie it's both.

    ReplyDelete
  4. Pratik Poddar1:09 PM, June 24, 2014

    Great solution Strilanc.

    Let me explain your solution in greater detail.

    Consider this question: "how many ants fall off to the left?" By the argument from the Ant Walking Problem - I, it's the number of ants L which are initially facing left.

    But which ones? Here's the key observation: the ants can't pass each other! So it must have been the L leftmost ants. So the last ant to fall off to the left is the Lth ant, and the last ant to fall off to the right is the (L+1)st ant, and one or both of those is the last ant to fall off.

    Now the third question, "which side will the last ant fall - right or left?", By the construction in Ant Walking Problem - I, if the leftmost element facing right is closer to the edge than the right most element facing left, the last ant will fall off the right side. If the last ant to fall is on the right side, then the "winner" ant is (L+1)th ant. Else, the "winner" ant in Lth ant.

    Cheers!

    ReplyDelete
    Replies
    1. Pratik Poddar1:15 PM, June 24, 2014

      Just taking care of the corner random case: "... if the leftmost element facing right is closer to the left edge than the right most element facing left to the right edge ... "

      Delete

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more