Schools Mathematics Grand Challenge
Week seven's Puzzles
The puzzles this week were quite tricky and required a lot of
work. Even if you didn't get the answer, if you made any progress,
you should consider it a good achievement!
Problem 19:
The solution was:
There are two tricks to solving this problem. The first is to notice
that you don't need to figure out the whole of each number in the
Fibonacci sequence, you only need to figure out the units number,
because the units number of the next one only depends on the units
digits of the previous ones.
This makes working things out a bit easier. Now, the units digit only
depends on the previous two units digits. There are 10 possibilities
for the units digit of each of the two previous ones, so there are
only 100 possibilities. This means than in less than 100 terms, the
sequence of units digits must begin to repeat.
Now we need to do a little work  let's keep calculating units digits
until they begin to repeat.
1 + 1 = 2 < last digit of 3
1 + 2 = 3 < last digit of 4
2 + 3 = 5 < last digit of 5
3 + 5 = 8 < last digit of 6
5 + 8 = 3 < last digit of 7
8 + 3 = 1 < last digit of 8
3 + 1 = 4 < last digit of 9
1 + 4 = 5 < last digit of 10
4 + 5 = 9 < last digit of 11
5 + 9 = 4 < last digit of 12
9 + 4 = 3 < last digit of 13
4 + 3 = 7 < last digit of 14
3 + 7 = 0 < last digit of 15
7 + 0 = 7 < last digit of 16
0 + 7 = 7 < last digit of 17
7 + 7 = 4 < last digit of 18
7 + 4 = 1 < last digit of 19
4 + 1 = 5 < last digit of 20
1 + 5 = 6 < last digit of 21
5 + 6 = 1 < last digit of 22
6 + 1 = 7 < last digit of 23
1 + 7 = 8 < last digit of 24
7 + 8 = 5 < last digit of 25
8 + 5 = 3 < last digit of 26
5 + 3 = 8 < last digit of 27
3 + 8 = 1 < last digit of 28
8 + 1 = 9 < last digit of 29
1 + 9 = 0 < last digit of 30
9 + 0 = 9 < last digit of 31
0 + 9 = 9 < last digit of 32
9 + 9 = 8 < last digit of 33
9 + 8 = 7 < last digit of 34
8 + 7 = 5 < last digit of 35
7 + 5 = 2 < last digit of 36
5 + 2 = 7 < last digit of 37
2 + 7 = 9 < last digit of 38
7 + 9 = 6 < last digit of 39
9 + 6 = 5 < last digit of 40
6 + 5 = 1 < last digit of 41
5 + 1 = 6 < last digit of 42
1 + 6 = 7 < last digit of 43
6 + 7 = 3 < last digit of 44
7 + 3 = 0 < last digit of 45
3 + 0 = 3 < last digit of 46
0 + 3 = 3 < last digit of 47
3 + 3 = 6 < last digit of 48
3 + 6 = 9 < last digit of 49
6 + 9 = 5 < last digit of 50
9 + 5 = 4 < last digit of 51
5 + 4 = 9 < last digit of 52
4 + 9 = 3 < last digit of 53
9 + 3 = 2 < last digit of 54
3 + 2 = 5 < last digit of 55
2 + 5 = 7 < last digit of 56
5 + 7 = 2 < last digit of 57
7 + 2 = 9 < last digit of 58
2 + 9 = 1 < last digit of 59
9 + 1 = 0 < last digit of 60
1 + 0 = 1 < last digit of 61
0 + 1 = 1 < last digit of 62
1 + 1 = 2 < last digit of 63
So, now we are back where we started  we have the two previous
units digits being 1 and 1, which is what we began with. We see
that the units digits of terms 1, 2 and 3 are the same as those for
terms 61, 62 and 63, which means the pattern repeats every 60.
So the 1200th number has the same last digit as the 1140th term,
which is the same as the 1080th term, ... which is the same as
the 60th term. We have already figured out that the 60th term has
last digit 0, so we are done!
Problem 20:
The solution was:
The answer is 5. One of many possible dominations is shown below in
picture A.
To prove that it cannot be done with 4 (or less) we proceed as follows.
Consider picture B and suppose that the board in picture
A could be dominated by 4 queens. Then it follows that
at least one of the queens must be in area (1) because otherwise the
8x8 board composed of areas (2) and (3) would be dominated by 4 queens
and we know this is not possible. By symmetry, there must also be at
least one queen in area (2). This leaves us with at most two queens
for area (3). It follows by inspection that no matter how we place the
queens in area (3), we will need at least two queens in both area (1)
and area (2) to ensure that all squares in their respective territories
(i.e. (1) and (2)) are attacked. In fact, inspection shows that both
queens would have to be on the long diagonal, as illustrated in picture
C. But obviously this is not a solution to the QDP. We
conclude that minimum number of queens needed to dominate the board is 5.
Problem 21:
The solution was:
The first step in this problem is to find any number n so that M is a
square. Note that if we square 2^{k} we get 4^{k}, this
gives an idea about what number we need to square. Then we rewrite things
a little:
4^{40} + 4^{1024} + 4^{n} = 4^{40} (1 + 4^{984} + 4^{n40})
4^{40} is easy to write as a square, so now we want to write 1 +
4^{984} + 4^{n40} as a square. This looks a bit like:
(1 + 2^{j})^{2} = 1 + 2*2^{j} + 4^{j} = 1 + 2^{j+1} + 4^{j}.
So we want to solve 4^{984} = 2^{j+1} and 4^{j}
= 4^{n40}. Since 4^{984} = 2^{1968} we get j =
1967, and so n = 1967 + 40 = 2007. This tells us that 4^{40} +
4^{1024} + 4^{2007} is 2^{40} (1+2^{1967})
squared.
To get this answer, we guessed that the number we were looking for might
be of the form
2^{40}(1 + 2^{j})
Could there be other numbers that give bigger values for n? The answer
is no, but we need to do a good bit of work to check.
The next step is to show that n can't be much bigger than 2007. Why is
this? Well, 4^{n} is the square of 2^{n}. The next
square after this is (2^{n}+1) squared, and the one after is
(2^{n}+2) squared. We know that M is even, so it must be at
least as big as the next even square, so
M ≥ (2^{n}+2)^{2}
4^{40} + 4^{1024} + 4^{n} ≥ 4^{n} + 2^{n+2} + 4
4^{40} + 4^{1024} ≥ 2^{n+2} + 4
2^{80} + 2^{2048} ≥ 2^{n+2} + 4
If n+2 > 2048, then this wouldn't be true, so we know we couldn't
get any squares if n ≤ 2046. We now need to eliminate the values
the numbers between 2007 (which we know makes a square) and 2047
(which we know is too big).
To do this last step, I used the fact that when you divide a square
by some number, then only certain remainders are possible. For example,
if you divide a square by 4, then the only possible remainders are 0
or 1  you will never get 2 or 3. If d is the number you are going
to divide by, then you can find all the possible remainders by
checking the numbers from 1 to d. For example, if d is 5, you figure
out the following table.
number square remainder when divided by 5
1 1 1
2 4 4
3 9 4
4 16 1
5 25 0
So the squares divided by 5 will always give you remainder
0, 1 or 4. These sorts of numbers are sometimes called Quadratic
Residues and are sometimes used in number theory and cryptography.
We can compare these numbers to the remainder when we divide
4^{40} + 4^{1024} + 4^{n} by 5. How do we
figure this other remainder out? Well, if we look at the remainder for
4, 4^{2}, 4^{3}, ... we find a repeating pattern: it
goes 4, 1, 4, 1, ... This means that 4^{40} gives remainder 1,
4^{1024} gives remainder 1 and 4^{n} gives remainder
1 if n is even and 4 if n is odd. When we add these up, the total is
1+1+1 = 3 if n is even (which isn't a possible square) and 1+1+4, or
remainder 1 if n is odd (which is a possible square). This eliminates
all the even numbers.
To eliminate all the remaining numbers, I checked if the remainders were
OK for all the numbers from 5 to 17. The patterns for each number are
slightly different. This gradually eliminated more numbers between 2007
and 2047 until only 2007 remained. The table below shows the result
of this  the number I was dividing by is on the left, and there is a
zero or a one in each row depending on if the remainder worked out OK
or not. There is at least one zero in each column except fro 2007.
If you're still with us at this stage, well done!
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
                                        
05: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
06: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
07: 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
08: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
09: 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
10: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
11: 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1
12: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
13: 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1
14: 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
15: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
16: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
17: 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
