Challenge Level

Many people sent in examples of amounts Alison could change her account by. However, this was quite a sneaky question, because the answer is that she can change her account by

Here is Nathan's explanation:

If she wants to increase by $x$ pounds, she can deposit 2$x$ lots of £2 and withdraw $x$ lots of £3. This creates a input of £4$x-$ £3$x$= £$x$.

To decrease by £$x$ deposit £2 $x$ times and withdraw £3 $x$ times.

Dare noted that Alison can increase her bank account by £1 by depositing £2 twice and withdrawing £3. She can do this repeatedly to add any positive whole number. If she withdraws £3 and deposits £2 she can decrease her account by £1, then she can repeat this to decrease her account by any whole number.

Nathan noted:

Alison can still increase and decrease her balance by any amount of integer pounds.

To increase by £$x$, deposit 5$x$ lots of £3 and withdraw 2$x$ lots of £7.

To decrease by £$x$, deposit 2$x$ lots of £3 and withdraw $x$ lots of £7.

The solution to this might look complicated at first, but read it slowly and carefully. If you can understand it then you're developing excellent mathematical understanding!

Therefore, the amounts Alison can change her balance by are of the form $ax-by$ for any non-negative integers $a$ and $b$.

Integers are the numbers ...,-2,-1,0,1,2,3,...

Positive integers are the numbers 1,2,3,...

Non-negative integers are the numbers 0,1,2,3,...

Positive integers are the numbers 1,2,3,...

Non-negative integers are the numbers 0,1,2,3,...

If $x$ and $y$ have a common factor $d$ then $d$ is also a factor of $ax-by$. This means that the only amounts Alison can change her balance by are multiples of $d$. So if $d$ is greater than 1 then Alison will never be able to change her balance by anything that is not a multiple of $d$.

Therefore, for Alison to be able to change her bank account by anything, $x$ and $y$ should have highest common factor 1.

But is it true that for any pair £$x$, £$y$ with HCF 1 Alison will be able to change her account by any amount?

Look back at Dare's solution to the first part. By depositing and withdrawing he managed to make £1 and - £1 and then he could make any amount by repeating this.

So if we can find positive integers $a$, $b$, $c$ and $d$ so that $$ax-by=1$$ and $$cx-dy=-1$$ then she can make any amount.

If we have found $a$ and $b$ then we can automatically find $c$ and $d$, because if we let $c=-a+ky$, $d=-b+kx$ where $k$ is any positive integer then $$\begin{align*} cx-dy &=(-a+ky)x-(-b+kx)y \\&=-ax+kyx+by-kyx \\&=-ax+by \\&=-(ax-by) \\&=-1 \end{align*}$$

and $k$ can be chosen large enough so that $c$ and $d$ are positive integers.

So all we need is to find positive integers $a$ and $b$ so that $$ax-by=1.$$

If we find any integers $u$ and $v$ so that $$ux+vy=1$$ then it must be the case that one is positive and the other is negative. (Because if they are both negative then $ux+vy$ will be negative, and if they are both positive then $ux+vy$ will be bigger than 1.)

If $u$ is positive and $v$ is negative then we can let $a=u$ and $b=-v$ and we have finished, if $u$ is negative and $v$ is positive then let $a=u+ny$ and $b=-v+nx$ where $n$ is some positive integer chosen large enough so that $a$ and $b$ are positive.

So all we need to be able to do is find integers $u$ and $v$ such that $ux+vy=1$.

Dare worked really hard on this problem, and at this stage had this insight:

It should not be too surprising, after working the first question, that in order to increase by any integer amount we need to be able to write the number 1 as a combination of $x$s and $y$s. More precisely, we can increase Alison's account balance by any positive integer if and only if there are integers $u$ and $v$ such that $$ 1 = ux + vy. $$

Two integers satisfying the above condition are called coprime, which is equivalent to the condition that $x$ and $y$ have highest common factor 1.

As Dare says, for every pairs of integers $x$ and $y$ that have highest common factor 1 you can find $u$ and $v$ which are both integers so that $$ 1 = ux + vy. $$ If you would like to know why this is the case you can read more about it here: An Introduction to Modular Arithmetic

Therefore, if $x$ and $y$ have HCF 1, Alison can make any amount, and if they have HCF greater than 1 Alison cannot make any amount.