| home      | people     | research     | publications    | seminars    | events     | contact

### 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 2k we get 4k, this gives an idea about what number we need to square. Then we rewrite things a little:

440 + 41024 + 4n = 440 (1 + 4984 + 4n-40)

440 is easy to write as a square, so now we want to write 1 + 4984 + 4n-40 as a square. This looks a bit like:

(1 + 2j)2 = 1 + 2*2j + 4j = 1 + 2j+1 + 4j.

So we want to solve 4984 = 2j+1 and 4j = 4n-40. Since 4984 = 21968 we get j = 1967, and so n = 1967 + 40 = 2007. This tells us that 440 + 41024 + 42007 is 240 (1+21967) squared.

To get this answer, we guessed that the number we were looking for might be of the form
240(1 + 2j)

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, 4n is the square of 2n. The next square after this is (2n+1) squared, and the one after is (2n+2) squared. We know that M is even, so it must be at least as big as the next even square, so

M ≥ (2n+2)2
440 + 41024 + 4n ≥ 4n + 2n+2 + 4
440 + 41024 ≥ 2n+2 + 4
280 + 22048 ≥ 2n+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 440 + 41024 + 4n by 5. How do we figure this other remainder out? Well, if we look at the remainder for 4, 42, 43, ... we find a repeating pattern: it goes 4, 1, 4, 1, ... This means that 440 gives remainder 1, 41024 gives remainder 1 and 4n 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
```