A horizontal stick is one metre long. Fifty ants are placed in random positions on the stick, pointing in random directions. The ants crawl head first along the stick, moving at one metre per minute. If an ant reaches the end of the stick, it falls off. If two ants meet, they both change direction. How long do you have to wait to be sure that all the ants have fallen off the stick?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Dunno if it counts as duplicate, but the same question exists on puzzling.stackexchange $\endgroup$– DenDenDoNov 25, 2014 at 9:41
-
1$\begingroup$ Is it a one dimensional stick, or a topological cylinder? "Random directions" seems like confusing wording if it is one-dimensional. $\endgroup$– Tim SeguineNov 25, 2014 at 10:03
-
4$\begingroup$ @TimSeguine your quibble could be answered by 10 seconds' thought about what either of the options you put forward would imply for the question. $\endgroup$– jwgNov 25, 2014 at 13:36
-
$\begingroup$ @jwg If you think so. I only posted that because I came to the "right" conclusion after reading the question, then the accepted answer in their entirety 3 times. If you consider that clarity, then we have most likely have different definitions of clarity. It seems to me that this was the source of some of the initial confusion people were having with the accepted answer. $\endgroup$– Tim SeguineDec 4, 2014 at 7:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
One minute at most. Imagine that ants "go through" each other. Whether the ants bounce off each other or walk past each other without changing direction has the same end effect: we have two ants approaching each other, then they meet, then they diverge from each other with that same speed of $1\text{m}/\text{min}$. So just assume that they do not bounce, but instead they keep walking the same direction, so it will take at most $1$ minute before they all fall off the edge.
Judging from the comments, it seems people disagree with the above argument, or have difficulty following/understanding it, so I offer a different interpretation. Say each ant carries a piece of paper with a written number on it. (You may call that piece of paper a baton, think of a relay race.) At the beginning all ants are numbered (from $1$ to $n$), and each ant holds a piece of paper with its own number on it. When two ants meet, they exchange their pieces of paper, and then bounce from each other. Note that while ants change direction when they bounce, the pieces of paper do not change direction. Thus these pieces of paper go with constant speed and direction $1 \text{m}/\text{min}$, so all the pieces of paper would fall off the stick in less than a minute. But, if there are no pieces of paper left on the stick, there are no ants either.
Just a comment on the first approach (when you could think ants pass by each other, instead of bouncing). Imagine that all ants look alike so much that you can't really tell them from each other. So two ants meet and bounce. But how could you tell, if you can't tell which ant is which? Perhaps you thought they bounced, but in reality each continued in its path without changing direction, passing by each other, and you do not know which is the case since these ants look so identical that you can't tell what exactly happened. Say ant A was going to the right towards ant B, and ant B was going to the left towards ant A. They meet and at the next moment you see them diverging from each other but you can't tell which ant is ant A and which ant is ant B. Perhaps the ant that now goes to the left is ant A, perhaps it is ant B. If it is ant A then they must have bounced, but if it is ant B then they must have passed next to each other without changing direction. But, it doesn't matter, since the "end result" is the same: immediately after they meet, we have two ants diverging from each other whether they bounced or they passed by each other. So assume now you have a different problem, in which ants do not bounce, but instead pass by each other (so each ant just keeps going, without changing direction). Clearly in this version of the problem all ants clear the stick in at most one minute. But, if you can't tell ants from each other, then you can't tell the two problems from each other either, so the answer to your original problem is at most a minute.
Since you put forward the name of Einstein in one of the comments, I feel entitled to involve physics in my answer. If the ants are particles, then they bounce from each other. But, if the ants are waves, then they "go through" each other, or pass next to each other. So, does light consist of particles, or waves, was Newton right (with his corpuscular theory of light), or was Huygens right (with his wave theory of light), and how is it that both theories are right?
-
1$\begingroup$ If you have 1 ant looking forward in the beginning of the stick and 49 looking backward somewhere in the end, then the first ant will stay on the stick for at least 100 minutes. $\endgroup$ Nov 24, 2014 at 17:56
-
1$\begingroup$ @AndreiRykhalski all ants are moving...you can not keep rest of 48 ants fixed. $\endgroup$ Nov 24, 2014 at 18:00
-
2$\begingroup$ @AndreiRykhalski If we assume that the ants take negligible amount of time to turn and move in the other direction, it will take at most one minute. This is because there will be some ant out of those 49 ants that is at the forefront. This will crash into the one ant that is coming from the other direction, and then all of them will be moving in one direction after which they all fall down. $\endgroup$– adijoNov 24, 2014 at 18:00
-
$\begingroup$ @adijo: one will always be going in the other direction (until it falls off). Collisions are irrelevant: you might as well assume that they pass right through each other - the effect is the same. $\endgroup$– NickDNov 21, 2019 at 15:55
$\begingroup$
$\endgroup$
2
This should help arrive at the answer. Let's first consider the shortest amount of time you'd have to wait. Assuming the ants were evenly distributed, and each ant faced the nearest edge, you'd have to wait 30 seconds. This is because the farthest an ant would have to walk is 50cm.
Now this should help see what the longest path an ant would need to walk is. Assume an ant starts at Edge A and faces Edge B. If this ant walks all the way to Edge B (which takes one minute), you can be sure that there are no ants behind this ant. Now let's say this ant bumps into something right at Edge B and has to turn around. We now know that the ant will fall off Edge A after one minute. So this ant walked two minutes and we know the ruler is empty. The problem here is that when this ant gets to Edge B there's nothing to bump into because all of the ants have already fallen off at Edge B. We know this because if any were going the opposite direction, this ant would have bumped into one beforehand.
If all of the ants are facing the same direction (a 2 in 2^50 chance), you'll see one ant walk the whole length of the ruler. You know this takes one minute. The question then becomes, what's the maximum distance an ant can walk if not all ants face the same direction. In this scenario, if an ant starts at Edge A facing Edge B, this ant can only get as far as the middle of the ruler without bumping into another ant. If the ant gets past the middle, that means all of the ants in front of it didn't turn around. But we assumed at least one ant was going the opposite direction. So assume the ant does get to the middle and bumps into another ant. Because this ant started at Edge A, and made it to the middle, we know there are no ants behind it, so it has an unimpeded path back to Edge A. This total journey takes half a meter twice, or one minute.
Finally, what about the ant it bumped into at the middle of the ruler? There's no difference between that ant and the ant that started from Edge A. That ant walks for one minute.
-
$\begingroup$ 30 sec is not really the shortest time, I think?! Consider an arrangement of ants just 1 mm apart, all facing the nearest end. It will take the last one much less than 30 sec to fall off. Otherwise, your analysis is correct. $\endgroup$– ysapNov 25, 2014 at 12:39
-
$\begingroup$ @ysap I was assuming the ants were evenly distributed to try to make a point about how the ants move. I should have mentioned what you say in your comment though. $\endgroup$ Nov 25, 2014 at 13:55