The three coin denominations used in Coinistan have values $7$ cents, $12$ cents and $23$ cents. Fareed and Krzysztof notice that their two Coinistan coin collections have the same number of coins and the same total value, but not the same number of $7$-cent coins. What is the smallest possible value of Krzysztof's collection?
Ans. 192 cents.
Source: MathCounts, 2021
We need to minimize the value, so it looks like one person will have no coins of one denomination (for example no $7$-cent coins, but a positive number of $12$– and $23$-cent coins). The other person will have no coins of $2$ denominations and a positive number of coins of the third denomination (for example some positive number of $7$-cent coins only).
I drew up a list of products of $7$, $12$, and $23$ with residuals in mod of the other $2$ numbers. So for example I wrote all the residuals of products of $7$ and $23$ in $\pmod {12}$ and so on for each pair of coins.
Eventually I looked at my list of residuals of products $7$ and $23$ and wrote down the combinations that resulted in a sum that was equivalent to $ 0 \pmod{12}$. So for example, in my list I had seven $7$-cents and one $23$-cent coin yields $72$ cents which can be replaced with 6 $12$ cent coins for the same value. But not the same number of coins. ($8$ versus $6$.) I continued down my list until I found that eleven $7$-cent coins and five $23$-cent coins yields a value of $192$ cents, and can be exchanged for sixteen $12$-cent coins. Same number, same value.
This process was time-consuming, and I'm wondering if I'm missing an insight that would save me time here. Thank you!
Best Answer
The only way to get an exchange equation is to rewrite some numbers of low and high coins as the (sum of the numbers) middle coins. This means you want to solve $$7x+23y=12z,\ \ x+y=z.$$ That is, $7x+23y=12(x+y),\ (23-12)y=(12-7)x.$ So it is $11y=5x$ with smallest solution $x=11,y=5.$ This gives the value $7\cdot 11+23 \cdot 5=192=12 \cdot 16.$ Note that as desired both are the same number of coins, i.e. $11+5=16.$