Schools Mathematics Grand Challenge
Week eight's Puzzles
Problem 22:
The solution was:
The answer is 5000000050000000.
To get the answer we use a trick. The trick is to observe that
2 / ((k+1)*(k+2)*(k+3)) = 1/((k+1)*(k+2)) - 1/((k+2)*(k+3))
for all k ≥ 0. This allows us to write:
2A = [1/(1*2) - 1/(2*3)] + [1/(2*3) - 1/(3*4)] + [1/(3*4) - 1/(4*5)] + ... etc.
After rearranging the brackets we get:
2A = 1/(1*2) + [1/(2*3)-1/(2*3)] + [1/(3*4)-1/(3*4)] + ... - = 1/(1000000*1000001)
since the terms between the brackets are all zero it follows that
2A = 1/(1*2) - 1/(1000000*1000001),
which gives us:
1/(1-4A) = 5000000050000000.
We also accepted answers close to 6 because there was a typo in
the original question, which would have given an answer of almost
6.
Problem 23:
The solution was:
It seems obvious to use 1,2,4,8 as one of the geometric sequences, as it
is the only geometric sequence covering 4 of our numbers. What other
sequences will cover lots of balls? Note that we can make a geometric
sequence hit any two numbers a and b by choosing the sequence to be a,
b = a*(b/a), a*(b/a)*(b/a), etc. If we do this with numbers where a does
not divide into b however, only two of the terms will be whole numbers.
So a solution is 1,2,4,8 then 3,5 then 6,7 and then 9; so Jo can do
it with four sequences. If the first sequence is 1,2,4,8 then the
remaining numbers are 3,5,6,7,9. By looking at all the pairs of these
numbers, we can check that a sequence with any pair will not also
contain any of the remaining numbers. That means that if we start
with 1,2,4,8 then the best we can do is pick off pairs, which means
we'll always need 4.
The final thing to do is check that not using 1,2,4,8 doesn't help enough
to get the total down to three. If we have three sequences covering
9 numbers, and none of them hit 4 (or more) numbers, then all three
sequences must hit three numbers. By checking the possibilities, we
can see that is impossible. So, 4 sequences is the best we can do.
Problem 24:
The solution was:
This very hard problem is called the problem of
Derangements. Induction is one of several ways
to solve this problem. Here we will use the method of Inclusion-Exclusion,
where we first double count some things and then go back and correct
ourselves.
Let's begin with ABCD to get the idea. There are 4*3*2*1 = 24 ways to
arrange these letters:
ABCD | BACD | CABD | DABC |
ABDC | BADC | CADB | DACB |
ACBD | BCAD | CBAD | DBAC |
ACDB | BCDA | CBDA | DBCA |
ADBC | BDAC | CDAB | DCAB |
ADCB | BDCA | CDBA | DCBA |
How many have at least one letter in the correct place? There are 15.
The number of left over ones (9) is the number we want, the number that
are all completely misspelled. How can we work out 15 without just
counting them?
We can ESTIMATE the number that has at least one letter in the correct
place as the sum of the number that have A in the correct place (6)
plus the number that have B in the correct place (6) etc. This will
gives us 24, which is WRONG, but is a start. What did we do wrong?
We counted words like ABDC too many times, once for the A in the correct
place, once for the B in the correct place etc. We have to correct 24
by subtracting off the number of words that have at least A and B in
the correct place (2), then the number that have at least A and C in
the correct place (2), then the number that have at least A and D in
the correct place (2), then the number that have at least B and C in
the correct place (2), etc. This all adds up to 12. Our estimate is
now 24-12 = 12, which is still wrong, but a lot closer to 15!!!
Actually we have subtracted off too much, and have to add back in the
number that have at least A and B and C in the correct place (1), and the
number that have at least A and B and D in the correct place (1), and the
number that have at least A and C and D in the correct place (1), etc.
This all adds up to 4, and we are up to 24-12+4 = 16. Now finally we
added back in the number that have A and B and C and D in the correct
place too many times (1) and have to subtract that off to get 15. Phew!!!
You can check that the totals in each case always follows the pattern
4*3*2*1 or 4*3*2 or 4*3 or 4 or 1. So, we get 15 = 4*3*2*1 - 4*3 + 4 -
1 and the answer is 9 = 24 - 4*3*2*1+4*3-4+1.
The same pattern works for ALGORITHM starting with 10; the answer is
1334961 = 10*9*8*7*6*5*4*3*2*1 - 10*9*8*7*6*5*4*3*2*1 +
10*9*8*7*6*5*4*3 - 10*9*8*7*6*5*4 + 10*9*8*7*6*5 - 10*9*8*7*6 +
10*9*8*7 - 10*9*8 + 10*9 - 10 + 1.
|
 |
Links
Home
About
News
This Week's Puzzles
Previous Puzzles
Solutions to old Puzzles
Get a User Code
Get your final score
Submit Your Answers
Tip of the Week
Did You Know ?
Competition Rules
|