Twenty ants live on the faces of an icosahedron, one ant on each side, where the icosahedron have each side with length 1. Each ant moves in a counterclockwise direction on each face, along the side/edges. The speed of each ant must be no less than 1 always. Also, if two ants meet, they should meet at the vertex of the icosahedron. If five ants meet at the same time at a vertex, we call that a collision. Can the ants move forever, in a way that no collision occurs?
Problem
Source: 2018 FKMO Problem 6
Tags: combinatorics, geometry, 3D geometry, icosahedron
sansae
25.03.2018 10:46
I think the answer is negative.. If not, can anyone show me an example?
MNJ2357
25.03.2018 12:25
Does anyone have solutions??
drkim
26.03.2018 01:32
I had an incorrect solution, but hopefully the new solution is correct. First observation: if more than two ants meet at a vertex, but not all five of them, then they should be able to speed up/slow down so that the actually don't meet. So the question is equivalent to whether it is possible that no ants meet at all. Second observation: we may only record which side the ant is currently on. If the ants do not meet, no two ants will be on the same side, and we can arbitrarily speed up/slow down the ants so that each of the ant passes through a vertex exactly when we want. Then the data of a "configuration of ants" is a choice of an edge for each of the faces, no edge is chosen twice, and ants moving around can be interpreted as the following "operation": for a face $\sigma$, if the edge $e^\prime \in \partial \sigma$ right next (in the counterclockwise direction) to the chosen edge $e \in \partial \sigma$ is not chosen by the face adjacent to $\sigma$ containing $e^\prime$, then we change to chosen edge of $\sigma$ from $e$ to $e^\prime$. Third observation: if it is true that the ants cannot move forever, then there should be an invariant that is monotone as time passes. So either there is an example of a sequence of these operations, or there is a monotone invariant. Well, it turns out that there is such an invariant. Here is a construction. For a configuration, consider the directed graph $G$ that has vertices the centers of faces $\{\sigma_1, \ldots, \sigma_{20}\}$ and an edge from each $\sigma_i$ to $\sigma_{f(i)}$ if the two faces are adjacent to each other with common edge $e$, such that $e$ is the chosen edge of $\sigma_i$. So this is a graph such that each vertex (or face of the icosahedron) has out-degree $1$. Because of this, there exist cycles in this graph. Recall that we are working on a icosahedron, our path can actually be thought as a path on the icosahedron. Thus a cycle $C$ divides the icosahedron into two pieces, one such that the path is counterclockwise on the boundary, and the other such that the path is clockwise on the boundary.
Define $\operatorname{vol}(C)$ as the number of vertices in the counterclockwise part. Then we consider the positive integer
\[ V = \min_C \operatorname{vol}(C). \]The claim is that this number strictly decreases if an edge on the minimal cycle moves to the next one. To see this, note that after an operation this path $C$ is broken, because one edge is changed, but then following the path leads to a cycle with smaller volume. Clearly it is impossible that this number decreases infinitely.
For each cycle $C$, denote by $C^\circ$ the region such that $C$ is counter-clockwise with respect to $C^\circ$. Let us say that $C$ is minimal if $C^\circ$ does not contain any other cycles, and maximal if the complement of $C^\circ$ is cycle-free. (A cycle is both maximal and minimal if and only if it is the only cycle.) We are only going to focus on cycles that are either minimal or maximal. Also, denote by $\operatorname{vol}(C)$ the number of vertices (of the icosahedron) that are in $C^\circ$. (If you're looking at the dual of the icosahedron, this is the number of pentagons in the region.) Let us analyze when minimal/maximal cycles appear or disappear. Note that whenever we do an operation, at most one cycle disappears, and at most one cycle appears. Here is the result: (1) When we move an edge that is not part of a minimal/maximal cycle, but a new cycle appears, the new cycle cannot be maximal. Note that it is possible that some minimal/maximal cycles might no longer be minimal/maximal due to the introduction of a new cycle. (2) When we move an edge that is part of a minimal/maximal cycle, either (i) the original cycle is removed and no minimal/maximal cycle appears, or (ii) there is a new minimal/maximal cycle that has strictly smaller volume. (3) In (2), if we move an edge that is part of a minimal cycle, there is always going to be a new cycle, and this new cycle is going to be minimal.
(1) When we move an edge that is not part of a minimal/maximal cycle to the next edge, and a new cycle appears. I claim that this cannot be a maximal cycle. Suppose that the new cycle $C = v_0 \to \cdots \to v_{n-1} \to v_0$ is the new cycle, where we changed $v_0 \to w$ to $v_0 \to v_1$. In this case, $v_0 \to w$ should be pointing to the complement of $C^\circ$. Then following the path $v_0 \to w \to \cdots$ should have given us a cycle $B$, before doing the operation. There are two possible scenarios: (i) either $B : v_0 \to w \to \cdots \to v_0$ contains $v_0$, or (ii) $B$ is disjoint from $C$. (i) If $B$ contained $v_0$, then the cycle would have looked like
\[ v_0 \to w \to w_1 \to \cdots \to w_k \to v_l \to \cdots \to v_{n-1} \to v_0. \]By our assumption, $B$ should not be maximal/minimal, and so there should be a cycle on both sides of $B$. In this case, when we do the operation and form $C$, these two cycles will still lie on both sides of $C$, and so $C$ is neither minimal nor maximal. (ii) If $B$ is completely disjoint from $C$, then it is contained in the complement of $C^\circ$. But then, after changing $v_0 \to w$ to $v_0 \to v_1$, we see that $B$ is still a cycle, contained in the complement of $C^\circ$. Therefore the new cycle $C$ cannot be maximal.
(2) When we move an edge that is part of a minimal/maximal cycle. Clearly, this cycle is going to be destroyed, but there is a possibility that a new minimal/maximal cycle appears. Suppose that the original cycle $C$ disappears, and a new cycle $C^\prime$ appears. If $C : v_0 \to \cdots \to v_{n-1} \to v_0$ was the original cycle, and we moved $v_0 \to v_1$ to $v_0 \to w$, then $v_0 \to w$ should lie in $C^\circ$. Because there is a new cycle $C^\prime$, the new edge $v_0 \to w \to \cdots$ should be part of $C^\prime$, and so $C^\prime$ should be in $C^\circ$. Therefore $(C^\prime)^\circ \subset C^\circ$, thus $\operatorname{vol}(C) > \operatorname{vol}(C^\prime)$. In other words, a cycle either disappears or is replaced with a cycle with smaller volume.
(3) In (2), suppose we move an edge that is part of a minimal cycle. Here, I claim that a new cycle is always going to be created, and it is always going to be minimal. This is fairly straightforward to see. If $C : v_0 \to \cdots \to v_{n-1} \to v_0$ was the original cycle, and we moved $v_0 \to v_1$ to $v_0 \to w$, then $v_0 \to w$ should lie in $C^\circ$. Then $v_0 \to w \to \cdots$ is now going to be a cycle that is minimal.
After all this work, let me write down the invariant. Consider first \[ X_1 = \sum_{C \text{ maximal}} \operatorname{vol}(C). \]By (1), maximal cycles cannot spring up from doing the operation not on minimal/maximal cycles. By (2), if we do the operation on a maximal cycle to get another cycle, we are only going to possibly get a cycle of smaller volume. By (3), if we do the operation on a minimal cycle, then we get a minimal cycle. This implies that if we do the operation on a non-maximal cycle, then we can only hope to get a non-maximal cycle. Therefore $X_1$ can never increase. Moreover, it has to strictly decrease whenever we do an operation on a maximal cycle. This shows that $X_1$ should decrease to $0$ if the ants are to move infinitely. This shows that eventually, there are going to be no maximal cycles. Note that there are always going to be cycles in a graph with out-degree $1$, and then, there is always going to be a cycle that is either maximal or minimal. This shows that there exists at least one minimal cycle. Now consider \[ X_2 = \min_{C \text{ minimal}} \operatorname{vol}(C). \]By (1), new minimal cycles can spring up, but that only decreases $X_2$. By (2) and (3), if we remove a minimal cycle, it is going to give rise to a minimal cycle with smaller volume. This shows that $X_2$ never increases, and it has to strictly decrease whenever we do an operation on a minimal volume minimal cycle. This contradicts $X_2 \ge 0$. Note that this argument works for any planar graph (embedded in $S^2$).
shjeong0947
26.03.2018 09:52
the answer is "no" proof sketch 1. first, we define 'count'. At the initial state, let the count 0. If any ants are on a vertex, we add 1 at the count. If the ant is not on the vertex, we can assume that ant is in the midpoint of the edge. At each count, there exist at least one ant in a vertex, and the other is in the midpoint of an edge. 2. There is a finite number of states of the location of ants. And it is easy to show that there are different count with the same state. Let's define the interval between two states 'period'. 3. Assume we can locate the ants without collision. Then, if we repeat the period, there is no collision. We can assume that one second passes when count increases, and then speed of the ant is rational number. Since the size of the period is finite, it is easy to show that we can make the speed an integer number. 4. Lets made the contradiction. We use double counting in the period. We count A=two triangle that share one edge and the point in the edge which (left triangle's ant goes to the edge earlier than right triangle-the other case). 5. When we count on the vertex, we use (mod3), and we can recongnize that total number of A is positive.(This holds because there is no collision, and 3 is the only multiple of 3 which is smaller than 5) However, when we count in respect to the edges, the total number of A is zero. So, contradiction. I think step5 is the hardest, but it is not so hard when we know the way to solve this solution. Sorry for my poor English, I may edit if you cant understand this sketch of the solution.
Grim-the-Ripper
27.03.2018 13:33
This is a nice problem! Though I'm not sure if the following solution works and/or if it is a repeat of the above. First, perform the same reduction as drkim in post #6 to get the equivalent formulation of the question where there are no ants meeting at a vertex at all. Consider projecting the icosahedron onto a plane via the Schlegel Diagram. Then basically now 19 ants - which we shall henceforth call small ants - still crawl on the edges of their respective faces in a counterclockwise fashion while the last ant - which we shall henceforth call big ant - crawls on the outer, biggest triangle in a clockwise fashion. This next part may be a bit difficult to follow; drawing diagrams would likely help. But now, consider the trajectory of the big ant. It overlaps with the trajectory of 3 other small ants. Consider one particular edge of the triangle trajectory of the big ant and the small ant whose trajectory shares that edge $ e $. But note that the small ant is traversing in the opposite direction of the big ant. In other words, during the whole duration while the big ant was travelling on $e$, the small ant would have to had stayed on the part of its trajectory - call this section the good trajectory - that does not contain $e$. But these are the only two ants whose trajectory contain $e$; meaning that we can just let WLOG the big ant eat up the small ant, i.e. instead of traversing $ e $ it now traverses the good trajectory. By our arguments this new trajectories have one less ant and there would still be no ants meeting at vertices. We can keep iterating this process (a subtle note is that sometimes we will have to consider the trajectory big ant sharing 2 edges with a small ant but the same argument still holds; we always remove the shared edges in their trajectories in our operation). In the end we'll end up with one triangle and one big ant and one small ant crawling on it. They would then have to meet at some point. By problem conditions this has to be at a vertex, and we are done.
gajae
17.06.2018 21:14
sadly I think I find a case.
CBMaster
02.05.2024 16:06
This problem is from Peter Winkler's book Mathematical Puzzles; A Connoisseur's Collection. See problem name "Bugs on a Polyhedron", p82. Quote: Associated with each face of a solid convex polyhedron is a bug which crawls along the perimeter of the face, at varying speed, but only in the clockwise direction. Prove that no schedule will permit all the bugs to circumnavigate their faces and return to their initial positions without incurring a collision. Collision means two or more bugs meet in single edge or vertex. Note that if some bugs collide in vertex $v$ at some moment, but at that moment there was an edge $e$ adjacent to $v$ such that no bugs on $e$ move toward to $v$, then bugs can slightly change their speeds so that no two collide on vertex $v$. So the statement 'collision must occur' means that at some moment there exist a edge that contain some bugs moving toward to each other, or vertex $v$ that all edges adjacent to it contain bugs moving toward to $v$. This is why our FKMO problem and above problem are same. According to the book, this problem is suggested in Anton Klyachko's paper "A Funny Property of Sphere and Equations over Groups", Communications in Algebra, Vol. 21, No. 7 (1993).