PUMaC 2023 · 个人决赛（A 组） · 第 2 题
PUMaC 2023 — Individual Finals (Division A) — Problem 2
题目详情
- On an infinite triangular lattice, there is a single atom at a lattice point. We allow for four operations as illustrated in Figure 1. In words, one could take an existing atom, split it into three atoms, and place them at adjacent lattice points in one of the two displayed fashions (a “split”). One could also reverse the process, i.e. taking three existing atoms in the displayed configurations, and merge them into a single atom at the center (a “merge”). Figure 1: The four possible operations on an atom. Assume that, after finitely many operations, there is again only a single atom remaining on the lattice. Show that this is possible if and only if the final atom is contained in the sublattice implied by Figure 2. 1 Figure 2: The possible positions for the final atom is the green sublattice. The position of the original atom is marked in purple.
解析
- On an infinite triangular lattice, there is a single atom at a lattice point. We allow for four operations as illustrated in Figure 1. In words, one could take an existing atom, split it into three atoms, and place them at adjacent lattice points in one of the two displayed fashions (a “split”). One could also reverse the process, i.e. taking three existing atoms in the displayed configurations, and merge them into a single atom at the center (a “merge”). Figure 1: See Individual Finals Problems document for diagram. Assume that, after finitely many operations, there is again only a single atom remaining on the lattice. Show that this is possible if and only if the final atom is contained in the sublattice implied by Figure 2. Figure 2: See Individual Finals Problems document for diagram. Proposed by Michael Cheng and Steven Wang Solution: First we show that the sublattice is the only possible loci for the final atom. Consider the following numbering/weighting of the lattice: Figure 3: Weighting of lattice It is easy to check that any of the operations does not change the total weight of the atoms. Therefore the final atom must appear on a lattice point with weight 1. Similarly one can rotate ◦ ◦ this picture by 60 or 120 , and one can conclude that only points of the given sublattice are possible final positions of the atom. 3 Remark. It might be of interest how one can come up with the weighting above. In fact, to obtain an invariant one needs the “local ratios” of the weights to be translational invariant (i.e. at each lattice point, the ratio of its weight to the six nearby ones is the same everywhere). Thus the entire weighting is defined by two numbers as exampled below: Figure 4: Labelling with indeterminants We then want − 1 − 1 − 1 − 1 α + βα + β = β + α + β α = 1 . There are six pairs of solutions, but they all give Figure 3 under rotational and reflectional symmetry. Now we return to the other direction of the proof. By rotational symmetry, it suffices to con- struct a sequence of moves that move the original atom 4 units to the right. The construction can be fun whilst mildly infuriating. One possible sequence is as follows (the original at purple, and the target at green): 4 Figure 5: Step 1: apply the blue split. Figure 6: Step 2: apply the orange split. At this stage, we observe a maneuver that we call the “propagation lemma:” 5 Figure 7: The “propagation lemma”. Apply the blue split and then the orange merge to move the purple pair to the right by one unit. This allows us to simultaneously move a pair of atoms spaced 2 units apart along the line they are on. Using this 4 times on the result of Figure 6 we can obtain the following: Figure 8: Step 3: apply the “propagation lemma” twice on the top row, and twice on the bottom row. 6 Figure 9: Step 4: apply the orange merge to get the purple atom. Now we apply Steps 1-4 to the left-most atom (purple in Figure 9), treating it as the starting point: Figure 10: Step 5: repeat step 1-4 on the left-most atom, which replaces it with three new atoms on the right, indicated by the purple arrows. Finally, we use two merges to achieve our goal! 7 Figure 11: Step 6: apply the blue merge and then the green merge to get the desired green atom. No other atom is left on the lattice and we are done. 8