Let n≥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
Problem
Source: Mexico National Olympiad 2020 P4
Tags: combinatorics, Circular array, vector
12.11.2020 18:29
12.11.2020 23:15
Clearly there is an arc with 3 different objects, be (a1),(a2),(a3) 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 a2 wins with a1, then a2 loses with a3 and a1 wins with a3 So we take a1 to the box of a2 and we have (),(a1,a2),(a3) then we take a2 to the box of a3 and we have (),(a1),(a2,a3) and finally of the box (a2,a3) we take a2 and a1 we take it to that box and it remains (),(),(a1,a2,a3). 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
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.