# Magic gopher

### From Seo Wiki - Search Engine Optimization and Programming Languages

The **magic gopher**[1] is an interactive Adobe Flash game published online by British Council.

## Contents |

## The trick

The trick to the game is that the gopher uses the same symbol for every multiple of 9, from 0 through 81 (it is impossible to get a higher number using only two digits). The gopher assigns the same symbol to the multiples of 9 as to other non-multiples of 9 in order to cover up the trick; the symbol picked for each game is randomized. No matter which two-digit integer the player chooses, when the subtraction is done, the resulting number will always be a multiple of 9. In fact, no matter which (nonnegative) integer the player chooses, the result will always be a multiple of 9. The former can be proven using elementary algebra. Be aware that the proofs for *n* digits rely on that the digits of the number <math>n\,</math> are indexed with the rightmost digit being assigned position 0, with the adjacent digits (to the left) having an index increasing by one each time. For example, for the number '261', the digit '1' is in position 0, '6' is in position 1, and '2' is in position 2.

### Proof for 2 digits

Let *n* be a 2-digit integer. Additionally, let *a* be the first digit of *n* and *b* be the second digit of *n*. Finally, let *c* equal the sum of the digits of *n*, so *c* = *a* + *b*..

An equivalent form for *n*, by virtue of using a decimal numeral system, is *n* = 10*a* + *b*.

The resulting number, *z*, is given by *z* = *n* − *c* = (10*a* + b) − (*a* + *b*) = 9*a*. Hence, *z* is always a multiple of 9. Q.E.D.

### Proof for *n* digits

Proving that no matter how large <math>n\,</math> is (and how many digits <math>n\,</math> has), it is always a multiple of 9 is slightly trickier. The following proof makes use of modular arithmetic:

Let <math>n\,</math> be an integer with <math>m\,</math> digits and let <math>n_m\,</math> represent the <math>m^{th}\,</math> digit of <math>n\,</math>.

Thus, <math>n\ = 10^m \cdot n_m + 10^{m-1} \cdot n_{m-1} + \cdots + 10^0 \cdot n_0</math>.

Let <math>c\,</math> be the sum of the digits of <math>n\,</math>. So, <math>c\ = n_m + n_{m-1} + \cdots + n_0</math>.

Since <math>10^m \equiv 1 \mod 9, n = n_m + n_{m-1} + \cdots + n_0 = c \mod 9</math>.

Hence <math>n - c \equiv 0 \mod 9</math> so the resulting number <math>z = n - c\,</math> is a multiple of 9.

Q.E.D.

#### Alternative proof for *n* digits

This alternative proof is less mathematically rigorous, relying on some common sense and intuition, but it is still sufficient to demonstrate the same as the above.

Again, let *n* be an integer with *m* digits and let *n*_{m} represent the *m*^{th} digit of *n*.

Thus,

- <math>n = 10^m \cdot n_m + 10^{m-1} \cdot n_{m-1} + \cdots + 10^0 \cdot n_0.\,</math>

Let *c* be the sum of the digits of *n*. So

- <math>c\ = n_m + n_{m-1} + \cdots + n_0.</math>

Now, let

- <math>z = n - c = (10^m \cdot n_m + 10^{m-1} \cdot n_{m-1} + .. + 10^0 \cdot n_0) - (n_m + n_{m-1} + \cdots + n_0).</math>

This can be written as

- <math>z = (10^m \cdot n_m - n_m) + (10^{m-1} \cdot n_{m-1} - n_{m-1}) + \cdots + (10^0 \cdot n_0 - n_0).</math>

By factoring, we obtain

- <math>z = n_m(10^m - 1) + n_{m-1}(10^{m-1} - 1) + \cdots + n_0(10^0 - 1).\,</math>

Now, <math>10^m - 1\,</math> will give a number with <math>m - 1\,</math> nines, hence, each individual digit of *n* is being multiplied by a multiple of 9 as the numbers given by <math>10^m - 1\,</math> are implicitly multiples of 9. Since the sum of any number of multiples of 9 is always divisible by 9, we conclude that whichever number is picked for *n*, it will always be a multiple of 9.

If we use the resulting formula for *z* assuming that *n* will only be 2 digits in length, we obtain the same formula as with the proof for a 2 digit *n*:

- <math>z = n_1(10^1 - 1) + n_0(10^0 - 1) = n_1 \cdot 9 + n_0 \cdot 0 = 9n_1</math> where <math>n_1 = a.\,</math>