Magic Teller Machine Solution

We had three correct entries to the Magic Teller Machine puzzle. Congratulations to: Tim Hillman, Ting Chen, and Paul Swinhoe. This month’s winner was Paul Swinhoe who will receive a $50 book voucher. Unfortunately, we didn’t receive any correct proofs of the Riemann Hypothesis.

The Magic Teller Machine:

You have several coins. Each of these coins has a front and a back, and on each side of the coin is a non-negative integer. We can represent a coin as the ordered paid $$\langle x, y \rangle$$ and the value of each coin is the sum of the integers on the front and back, $$x+y$$. In front of you is a magic teller machine, it knows the contents of your coin purse. If you have a coin $$\langle x, y \rangle$$, but you do not have either the coin $$\langle x+1, y \rangle$$  or  $$\langle x, y +1\rangle$$, then the MTM will allow you to exchange your coin $$\langle x, y \rangle$$  for two new coins $$\langle x+1, y \rangle$$  and $$\langle x, y+1 \rangle$$.  You are allowed to make any (finite) number of transactions with the MTM. The aim of the game is to make a sequence of transactions with the MTM so that all of your coins have a value greater than $2$. Is this possible in either of the following scenarios:

1. You start with the $$6$$ unique coins with a value at most $$2$$:
   $$\langle 0, 0 \rangle, \langle 1, 0 \rangle, \langle 0, 1 \rangle, \langle 2, 0 \rangle, \langle 1,1 \rangle, \langle 0, 2 \rangle$$
2. You start with a single coin of value zero: $$\langle 0, 0 \rangle$$

Demonstrate that you can exchange your coins until they all have a value greater than $$2$$, or prove that it’s impossible.

Solution 1:

We will show that it is impossible to convert the coin $$\langle 0, 0 \rangle$$ into coins with value greater than $$2$$ in a finite number of moves. This will also show that scenario (a) is impossible.

Suppose, for the sake of contradiction, that we have a finite sequence moves that will exchange $$\langle 0, 0 \rangle$$ into coins of values greater than $$2$$. For each coin $$\langle x, y \rangle$$ we will consider the minimum number of times that this coin will appear in our collection of coins throughout the strategy (i.e. not at the same time). Clearly $$\langle 0, 0 \rangle$$ appears once and it must be exchanged with the MTM. This will produce two coins $$\langle 1, 0 \rangle$$ and $$\langle 0, 1 \rangle$$. These must also be exchanged with the MTM (as they have value less than $$2$$) and so on. This is illustrated in the diagram below:

The bottom row of the diagram shows coins with value $$3$$. The coin $$\langle 2, 1 \rangle$$ will appear in the collection of coins $$3$$ times. We must exchange that coin with the MTM at least twice (because we can only have one coin $$\langle 2, 1 \rangle$$ at the end).

For a positive integer $$k$$, consider the wallet of coins $$W(k) = \{\langle k+2, k-1\rangle, \langle k+1, k\rangle, \langle k, k+1\rangle, \langle k-1, k+2\rangle \}$$.

Let $$P(k)$$ be the proposition that the minimum number of times that each of these coins appear in our possession is at least $$1 \times \langle k+2, k-1\rangle, 3 \times \langle k+1, k\rangle, 3 \times \langle k, k+1\rangle, 1 \times \langle k-1, k+2\rangle$$. The bottom row of the above diagram demonstrates that $$P(1)$$ is true. We will show that $$P(k)$$ implies $$P(k+1)$$.

Notice that if $$P(k)$$ is true then at a minimum we must exchange both $$\langle k+1, k\rangle$$, and $$\langle k, k+1\rangle$$ with the MTM twice. This produces $$2\times\langle k+2, k\rangle, 4\times \langle k+1, k+1\rangle,2\times \langle k, k+2\rangle$$.

In turn this implies we must exchange $$\langle k+2, k\rangle, \langle k+1, k+1\rangle$$, and $$\langle k, k+2\rangle)$$ leaving at least $$1\times \langle k+3, k\rangle, 3\times \langle k+2, k+1\rangle,3\times \langle k+1, k+2\rangle,1\times \langle k, k+3\rangle$$, which is $$P(k+1)$$.

By induction this implies that every coin in $$W(k)$$ for every $$k$$ must appear in our collection of coins at some point in our strategy, but this requires an infinite number of moves – a contradiction! So we have demonstrated that both cases are impossible.

Solution 2:

With a little bit more work and ingenuity we can also show that both cases are impossible, even with an infinite number of moves.

First, let us apply a weight to each coin $$\omega( \langle x, y\rangle ) = 2^{-(x+y)}$$. We have chosen this weight because $$\omega( \langle x, y\rangle ) = \omega( \langle x+1, y\rangle ) + \omega( \langle x, y+1\rangle )$$. That is, one transaction with the MTM preserves the total weight of the coins.

Summing a geometric series we can calculate the weight of all the coins as $$\sum_{x \in \mathbb{N}_0} \sum_{y \in \mathbb{N}_0} \omega( \langle x, y\rangle ) = 4$$.

• The weight of the $$6$$ coins with value at most $$2$$ is $$(1 + \frac{1}2 +\frac{1}2 +\frac{1}4+\frac{1}4+\frac{1}4) = 2\frac{3}4$$. The weight of all coins with a value greater than $$2$$ is $$4 – 2\frac{3}4 = 1\frac{1}4$$. Because each transaction preserves total weight of the coins we cannot convert all of our original coins into coins with value greater than $$2$$, so case-a is impossible.
• We will extend the logic for case-b. Starting with a single coin, after any number of transactions, we can have at most $$1$$ coin of the form $$\langle x, 0\rangle$$ and $$1$$ coin with of the form $$\langle 0, y\rangle$$ for $$x,y \in \mathbb{N}$$. The weight of all coins $$\langle x, 0\rangle$$ with value greater than $$2$$ is $$\frac{1}4$$, and the largest weight a single coin of this form can take is $$\omega(\langle 3, 0\rangle) = \frac{1}8$$. This means that the potential weight of coins with value greater than $$2$$ reduces to $$1\frac{1}4 – (\frac{1}8 + \frac{1}8) = 1$$.  Further note that the number of coins we can have of the form $$\langle x, 1 \rangle$$ is equal to the number of transactions we make of a coin with the form $$\langle x, 0\rangle$$. This means we could never have both the coin $$\langle 3, 0\rangle$$ and more than $$3$$ coins of the form $$\langle x, 1 \rangle$$. This reduces our bound to strictly less than $$1$$. So again we cannot convert the coin $$\langle 0, 0 \rangle$$ into coins with value greater than $$2$$, even with infinitely many moves.

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.