A beautiful game of gold and silver coins

A stack of silver coins is on the table.

For each step we can either remove a silver coin and write the number of gold coins on a piece of paper, or we can add a gold coin and write the number of silver coins on another piece of paper.

We stop when only gold coins are left.

Prove that the sums of numbers on these two papers are equal.

Tried playing the game and the problem seems right each time, but I can't proceed from there. Is it done by induction?

Solution 1:

The state of the game can be desribed by $$ (g,s,G,S), $$ where $g$ is the number of golden coins on the table, $s$ is the number of silver coins on the table, $G$ is the sum of the numbers in the first paper, and $S$ is the sum of the numbers in the second paper. The initial state is $(0,n,0,0)$, and we want to show that if the state of the game is $(g,0,G,S)$, then $G=S$.

If we are at $(g_i,s_i,G_i,S_i)$ and add a golden coin, the state changes to $$ (g_{i+1},s_{i+1},G_{i+1},S_{i+1}) = (g_i+1,s_i,G_i,S_i+s_i), $$ and if we remove a silver coin, the state changes to $$ (g_{i+1},s_{i+1},G_{i+1},S_{i+1}) = (g_i,s_i-1,G_i+g_i,S_i). $$

One plan to solve the problem is to find an invariant, for example, a function from $(g,s,G,S)$ to integers, such that these transformations do not change the value of that function. Looking at the equations for a while suggests something with $gs$ because that's how we would get changes of size $g$ and $s$. A bit more looking gives us $$ f(g,s,G,S) = gs+G-S. $$ Once we have found the above formula, it is easy to verify that a step does not affect the value of $gs+G-S$.

Thus if we start from $f(0,n,0,0)=0$ and end with $f(g,0,G,S) = G-S$, we can see that $G=S$.

Solution 2:

When you add a gold coin, you write $n$ for the number of silver coins left.

Every time you remove one of those $n$ silver coins, that gold coin gets counted once as part of the number of gold coins - a total of $n$ times, since all the silver coins are eventually removed.

Solution 3:

Say you start with $n$ silver coins. As long as you remove only silver coins, you keep writing $0$s. These moves don’t affect the sum on either paper, so you might as well ignore them and assume that the first move is to add a gold coin, writing $n$ on the second paper. Each time you remove a silver coin before you add another gold coin, you’ll write another $1$ on the second paper, so if you remove $s_1$ coins, you’ll add $s_1$ to the total on the first paper.

Then you add a second gold coin, which adds $n-s_1$ to the total on the second paper. Say you then remove $s_2$ silver coins (where $s_2$ could be $0$); that adds $2s_2$ to the total on the first paper and leaves you with $n-(s_1+s_2)$ silver coins.

When you then add a third gold coin, you write $n-(s_1+s_2)$ on the second paper, and if you then remove another $s_3$ silver coins, you’ll write $3$ on the first paper $s_3$ times.

In general, when you’ve added the $k$-th gold coin, you’ll write $n-\sum_{i=1}^{k-1}s_i$ on the second paper, and when you then remove another $s_k$ silver coins, you’ll write $k$ on the first paper $s_k$ times. At this point the total on the first paper will be $$\sum_{i=1}^kis_i\;,$$ and the total on the second paper will be

$$\sum_{j=0}^{k-1}\left(n-\sum_{i=1}^js_i\right)=kn-\sum_{j=1}^{k-1}\sum_{i=1}^js_i=kn-\sum_{i=1}^{k-1}\sum_{j=i}^{k-1}s_i=kn-\sum_{i=1}^{k-1}(k-i)s_i\;.$$

(Note that $\sum_{i=1}^0s_i=0$.)

Suppose that at the end there are $m$ gold coins. Write out expressions for the totals on the two papers in terms of $m$ and $n$; the expressions will involve summations. Then show that the expressions are equal; it’s a fairly simple algebraic manipulation at that point. If you get completely stuck, mouse over the spoiler-protected block below.

If there are $m$ gold coins at the end, the total on the first paper will be $$\sum_{i=1}^mis_i\;,$$ and the total on the second will be $$mn-\sum_{i=1}^{m-1}(m-i)s_i=mn-\sum_{i=1}^m(m-i)s_i\;.$$ You’ll need to realize that $\sum_{i=1}^ms_i$ can be simplified enormously.

Solution 4:

Let the number of gold coins and silver coins be x and y. Imagine the xy-grid and let our starting state and ending state be represented by (0, y) and (x, 0) respectively.

With each step, (x, y) becomes either (x+1, y) or (x, y-1), corresponding to when a gold coin is added or a silver coin is removed. Consider the path traced by the point moving from (0, y) to (x, 0), and also consider the area bounded by this curve, the positive x-axis, and the positive y-axis.

The area mentioned above may be evaluated in two ways, either as sum of areas of rectangles with width 1 and largest possible height, or sum of areas of rectangles with height 1 and largest possible width. Each piece of paper lists the areas of the individual rectangles, and since the total area is the same, the sum on each paper is the same and both are equal to the value of area under the path traced.

Solution 5:

Let's start with just a single silver coin. We can now add $k$ gold coins, until we remove our $1$ silver coin and the game ends.
For each of those gold coins, we wrote $1$ on our piece of paper, so that's a total of $k$ 1's. When we finally removed the silver coin, we wrote $k$ on the other piece of paper, once. It's easy to see that both sums are $k$.

Let's move on to $2$ silver coins. We now add $m$ gold coins, then we remove the first silver coin, then we add another $k$ gold coins and remove the second silver coin.
On one piece of paper we have $m$ 2's and $k$ 1's, on the other we have $m$ (from when we removed the first silver coin) and $m + k$ (from when we removed the second silver coin). As both sum to $2m + k$, again, the sums are equal.

If we define $g_s$ as the number of gold coins added between between removal of silver coins $s$ and $s-1$, we can see that $s$ is listed $g_s$ times, while $g_s$ occurs $s$ times as a summand of a number in the other list, for all $g, s \in \mathbb Z_{\ge 0}$