Esteban the alchemist have $8088$ copper pieces, $6066$ bronze pieces, $4044$ silver pieces and $2022$ gold pieces. He can take two pieces of different metals and use a magic hammer to turn them into two pieces of different metals that he take and different each other. Find the largest number of gold pieces that Esteban can obtain after using the magic hammer a finite number of times. $\textbf{Note:}$ If Esteban takes a copper and bronze pieces, then he turn them into a silver and a gold pieces.
Problem
Source: 2022 Centroamerican and Caribbean Mathematical Olympiad, P5
Tags: combinatorics, magic
01.12.2022 16:33
Solved with mxlcv. Observe that Esteban cannot convert all pieces to gold, since in the last move, something other than gold must have been created. We claim that the maximum number of gold pieces he can obtain is $10 \cdot 2022 - 2$. We say that $(a, b, c, d) \equiv (a_1, b_1, c_1, d_1)$ if it is possible to start with $a$ copper pieces, $b$ bronze pieces, $c$ silver pieces, $d$ gold pieces and through some applications of the magic hammer, convert them into $a_1$ copper pieces, $b_1$ bronze pieces, $c_1$ silver pieces, and $d_1$ gold pieces. Observe that this is an equivalence relation since the steps are reversible. Observe that the operations are now like adding vectors $v \in \{-1,1\}^4$ with sum of coordinates zero. For now, write $n = 2022$ and observe that performing $(-1, +1, -1, +1)$ $2n$ times yields $(2n, 5n, 0, 3n)$. Now we add $(-1, -1, +1, +1)$ $2n$ times to obtain $(0, 3n, 2n, 5n)$. This after applying $(+1, -1, -1, +1)$ $2n$ times yields $(2n, n, 0, 7n)$. Finally, applying $(-1, -1, +1, +1)$ $n$ times we obtain $(n, 0, n, 8n)$. Now we can perform $(-1, +1, -1, +1)$ a total of $n/2$ times to obtain $(n/2, n/2, n/2, 17n/2)$. Claim: $(a, a, a, b) \equiv (a-1, a-1, a-1, b+3)$ if $a > 2$. Proof: Apply $(-1, -1, +1, +1)$, $(-1, +1, -1, +1)$, $(+1, -1, -1, +1)$. $\square$ Thus eventually, we can reach $(2, 2, 2, 10n-6)$. Now perform $(-1, -1, +1, +1)$, $(+1, -1, -1, +1)$ and then $(-1, +1, -1, +1)$ twice to obtain $(0,2,0,10n-2)$. Hence $(4n, 3n, 2n, n) \equiv (0,2,0,10n-2)$. Observe that for any two kinds of pieces, say silver and gold, their combined sum is invariant modulo $2$. Thus, if it were possible to obtain $10n-1$ gold pieces, then the sum of gold pieces and some other type of piece would be $10n-1$ which is odd; a contradiction since there are an even number of pieces of each kind at the start. Hence the maximum number of gold pieces Esteban can create is $10 \cdot 2022 - 2$.
01.12.2022 17:58
Represent the state as a quadruple $(C, B, S, G)$. Observe the sequence of transformations, where we are allowed to freely permute the coordinates of the tuple: \begin{align*} (a + 2, x + 2, 0, 0) &\to (a + 1, x + 3, 1, 1) \to (a, x + 2, 2, 2) \to (a + 1, x + 1, 1, 3) \\ &\to (a + 2, x + 2, 0, 2) \to (a + 3, x + 1, 1, 1) \to (a + 4, x + 2, 0, 0) \end{align*} Where $a, x, y, z \ge 0$. Applying this sequence of transformations repeatedly we may turn $8086$ copper pieces, $6064$ bronze pieces and $4042$ silver pieces into gold pieces, leaving us with the state $(2, 2, 2, 20214)$. Now perform the operations \[(2, 2, 2, 20214) \to (1, 1, 3, 20215) \to (2, 0, 2, 20216) \to (1, 1, 1, 20217) \to (0, 0, 2, 20218)\] So $20218$ is achievable, we now show that this is the maximum. Notice that each operation changes the parity of the number of pieces of all types, so they're always either all even or all odd. Thus it's impossible to have $20219$ pieces of one type since it would be accompanied by a type with $0$ pieces. Furthermore notice that any operation always leaves pieces of at least two different types, so it's impossible to ever get all of the pieces to have the same type, discarding $20220$. We conclude that $20218$ is the maximum.
02.12.2022 16:42
This problem was proposed by Colombia. It was created by Juan David Restrepo (supercan31415) with a bit of my help. Hopefully you enjoy the problem as much as I do.