Magic Teller Machine Solution

Oliver Chambers outlines the solutions to his Magic Teller puzzle and announces the winner of the first instalment of The Critical Line series.

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:

Magic Teller Machine Picture

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.