Counting Coins and Their Values

There are positive integers $t,u,v,w,x,y,z$ such that

$t+u+v+w+x+y+z=N\\ t+2u+5v+10w+20x+50y+100z=M.$

The task is to show that there are integers $a,b,c,d,e,f,g$ such that

$a+b+c+d+e+f+g=M\\ a+2b+5c+10d+20e+50f+100g=N.$

Suffice it to take $a=100z,$ $b=50y,$ $c=20x,$ $d=10w,$ $e=5v,$ $f=2,$ and $g=t.$ Then certainly,

$a+b+c+d+e+f+g=M.$

In addition,

$\begin{align} &a+2b+5c+10d+20e+50f+100g\\ &\qquad\qquad=100z+100y+100x+100w+100v+100u+100t\\ &\qquad\qquad=100(t+u+v+w+x+y+z)=100N. \end{align}$

Let vector $c = (1,2,5,10,20,50,100)^T$ and $\mathbf{1} = (1,1,1,1,1,1,1)^T$. Then the original problem is that if there exists $x \in \{1,0\}^7$ such that

\[ c^Tx = M \quad \text{and} \quad \mathbf{1}^Tx = N \], then there also exists $y$ such that \[ c^Ty = 100N \quad \text{and} \quad \mathbf{1}^Ty = M. \]

To see this, let diagonal matrix $H = \text{diag}(100, 50, 20, 10, 5, 2, 1)$ and $\tilde{x}$ be the "mirrored" version of $x$, i.e., $\tilde{x}_1 = x_7$, $\tilde{x}_2 = x_6$ and so on. One can verify that:

\[ c^T H\tilde{x} = 100 \cdot \mathbf{1}^T\tilde{x} = 100\cdot \mathbf{1}^T x = 100N \]

and

\[ 1^T H\tilde{x} = 1^T (100\cdot H^{-1} x) = c^Tx = M \]

In other words, $y$ should be set to $H\tilde{x}$ to satisfy this relationship.

To begin, we show that the statement is true for all possible cases where $N=1$. Indeed, the following table shows that if $N=1$ coin is valued at $M=x$ cents, then we can find a (uniform) combination of $M=x$ coins with a total value of $N=1$ dollar by taking $x$ of the $y$ cent coins.

\begin{align*} x && y \\ 1 && 100 \\ 2 && 50 \\ 5 && 20 \\ 10 && 10 \\ 20 && 5 \\ 50 && 2 \\ 100 && 1 \end{align*} Now suppose that $N >1$ coins have a total value of $M$ cents. We want to find a combination of $M$ coins with a total value of $N$ dollars. Let's write \[ M = x_1 + x_2 + \cdots + x_N, \] where $x_j$ is the value (in cents) of the $j$-th coin. Then, for each $j \in \{1,2, \dots, N\}$, we can use the table above to find a (uniform) combination of $x_j$ coins with a total value of $1$ dollar by taking $x_j$ coins of the appropriate type. At the end of this process, we will have a collection of \[ x_1 + x_2 + \cdots + x_N = M \] coins with a total value of \[ \underbrace{1+1+ \cdots 1}_{N \text{ times}}=N \] dollars. This establishes the case when $N>1$ and completes the proof.

This is a problem from the book Leningrad Mathematical Olympiad: 1987-1991 by D. Fomin and A. Kirichenko, (MathPro Press, 1994, #20-1987). This was a problem for grade 8.

Solution 2 is by egghead scholar; Solution 3 is by InfoSymmetries.