AoPS - Problem

Problem

Source: Mexico National Olympiad 2020 P4

Tags: combinatorics, Circular array, vector

plagueis

12.11.2020 01:01

Let $n\ge 3$ be an integer. In a game there are $n$ boxes in a circular array. At the beginning, each box contains an object which can be rock, paper or scissors, in such a way that there are no two adjacent boxes with the same object, and each object appears in at least one box. Same as in the game, rock beats scissors, scissors beat paper, and paper beats rock. The game consists on moving objects from one box to another according to the following rule: Two adjacent boxes and one object from each one are chosen in such a way that these are different, and we move the loser object to the box containing the winner object. For example, if we picked rock from box A and scissors from box B, we move scossors to box A. Prove that, applying the rule enough times, it is possible to move all the objects to the same box. Proposed by Victor de la Fuente

kankan

12.11.2020 18:29

We see that once a box contains a rock, a piece of paper, or a pair of scissors, it is always possible to "lose" against any object, since all three cases for what that object is are covered. If we have a box with all three objects (call it box

$1$ ) next to a box with one object (let it be a pair of scissors for the sake of simplicity, and call the box box

$2$ ), we can perform the following algorithm to move all the objects into the box

$2$ : Compare the scissors in box

$2$ to the paper in box

$1$ . The paper and scissors are now in box

$2$ . Compare the paper in box

$2$ to the rock in box

$2$ . There is now a piece of paper, a pair of scissors, and a rock in box

$2$ . Compare the rock in box

$2$ with the scissors in box

$1$ . All objects are now in box

$2$ . We see that we have now arrived at the same situation with a box with all three types of objects next to a box with a single object, so we can see that continuously applying this formula results in all of the objects being put in the same box. We now only need to prove that such a box can be constructed. We observe that if we have the three objects consecutively anywhere on the ring, then it is possible to put them in the same box by the following algorithm: Compare the middle object with the object in the group of three that loses to the middle object. Compare the middle object with the third object, which results in a loss. Compare what used to be the middle object with the only object still in what was the middle box. Now, all three objects are sitting in one box. Choosing a group of three consecutive objects yields either two objects of the same type surrounding an object of another type, or three objects of different types. We attempt a proof by contradiction: For the sake of contradiction, assume all consecutive groups of three are of the first kind. As these groups overlap, if three objects are in an

$aba$ pattern, then the next object in a consecutive group of

$4$ must be a

$b$ to complete a

$bab$ pattern. This implies that only two types of objects are present, which contradicts the problem statement. Thus, there must be a group of three consecutive different objects, so a box containing all three types of objects is constructible, and so it is possible to collect all objects into the same box.

MiltonMath12

12.11.2020 23:15

Clearly there is an arc with $3$ different objects, be $(a_1),(a_2), (a_3)$ the different elements. Clearly the one in the center is going to lose with one of the two adjacent ones since each one loses with one and wins the other, wlog $a_2$ wins with $a_1$ , then $a_2$ loses with $a_3$ and $a_1$ wins with $a_3$ So we take $a_1$ to the box of $a_2$ and we have $(),(a_1, a_2), (a_3)$ then we take $a_2$ to the box of $a_3$ and we have $(),(a_1), (a_2, a_3)$ and finally of the box $(a_2, a_3)$ we take $a_2$ and $a_1$ we take it to that box and it remains $(),(),(a_1, a_2, a_3)$ . With this, no matter who touches the next box, we can guarantee that we will go through the rest of the objects to the following boxes, as we wanted to demonstrate

cursed_tangent1434

04.05.2024 19:04

Solved with MathLuis. Today was a very bad gsolve day. After being carried on 13RMM2 we proceeded to individually clown on this problem for over an hour. We say that a box is R if it contains a rock, S if it contains a scissor and P if it contains a paper. We first prove the following trivial claim. Claim : There must exist 3 consecutive boxes which are R , S and P (in some order). Proof : Consider any two consecutive boxes of different types, say R and S. The neighbor of R must be S or P since no two consecutive boxes have the same item in it. If we don't have an R-S-P chain then it must be S, the neighbor of that must be R and so on, until we eventually reach a P (since we are garuanteed there are atleast one box of each type) at which point a R-S-P chain must clearly exist. Now, consider such an R-S-P chain and provide the following algorithms. Algorithm : (RSP box)We can always create a box containing a rock/paper/scissors which has two consecutive empty boxes as its neighbors, by the given algorithm. WLOG, assume the R-S-P chain is in this order (the other cases P-R-S and S-R-P are entirely similar). Then, we move the P to the S box, and then the S to the R box, and finally P to the R box as well (since now there is a scissor in it). Thus, we can create such a series of boxes as desired. Algorithm : To reach a single box which has all the item, we consider the following algorithm. Simply consider the non-empty neighbor of the RSP box. WLOG, say it has a paper. Then, we move first R to this box. Then, we can move all scissors as well. Then, finally we can move all paper. Thus, the previous RSP box was empty and we have 3 empty boxes in a row. We continue likewise until all the items are moved into one box and we are done.