Saturday, 23 January 2010

Greenwich Maths Challenge 3 - COMING 7 FEBRUARY

GMC3 logo
The third Greenwich Maths Challenge will be posted here on Sunday 7 February at 9:30am (approximately). We have postponed it from the previously announced date so that those preparing presentations for the Tomorrow's Mathematicians Today conference on 6 February will not be distracted! It will be a cryptography challenge so speed will be of the essence. If you don't already have it you might like to download Simon Singh's free "Code Book" CD-rom and practice cracking Vigenere ciphers!

Christmas Quiz results

Congratulations to Ameli Gottstein, who has (for the second year in a row) won our Christmas quiz. Here are the answers:

Q1. Identify the mathematicians whose names are given below as anagrams. Accents and punctuation marks such as hyphens are omitted, and spellings are taken from the MacTutor History of Mathematics website

a) ENRW - Wren

b) EIKLNV - Kelvin

c) EEKLPR - Kepler

d) AAIIJNX - Jia Xian

e) AHILMNOT - Hamilton

f) BEILLNORU - Bernoulli

g) ACDEEHIMRS - Archimedes

h) AEMNNNNOUV - von Neumann

i) GKLMOOOORV - Kolmogorov

j) AAAEKKLOSVVY - Kovalevskaya

Q2. What is the smallest two-digit integer?

-99. Silly, but it caught me out when I was asked.

Q3. Is 10^2010 + 1 prime? Justify your answer.

The trick here is that for any integers x and y, x^3 - y^3 has a factor x-y. So if n is a multiple of 3, then 10^n+1 is the difference between two cubes because it is 10^(n/3)^3 - (-1)^3. So 10^2010+1 is not prime - in fact it has a factor 10^670+1.

Q4. On average, how many times do you need to toss a fair coin before you have seen a run of an odd number of heads followed by a tail?

This was from Peter Winkler, Mathematical Puzzles: A Connoisseur's Collection (A.K. Peters, 2004). Suppose that the answer is x. Consider the first couple of tosses. If the first coin comes up tails (which it will with probability 1/2), then we have made no progress and the expected number of tosses is now x+1. If the first coin comes up heads and the second toss is also heads (which happens one time in four), then we again expect to take a further x tosses so the expected number of tosses is now x+2. And if the first toss is heads and the second is tails (again one time in four), we have finished and it took two tosses. So we have
x = (1/2).(x+1) + (1/4).(x+2) + (1/4).2 so x = 6.

Q5. Consider a chessboard – an 8x8 grid of squares in which each row and column is alternately black and white. You have 31 2x1 rectangles each the size of two adjacent squares of the chessboard. Remove the top left and bottom right corner squares. Is it possible to cover the 62 remaining squares with your 31 rectangles? Provide a solution or show that it can’t be done.

This is a lovely old favourite. Colour the chessboard in the normal way, so that each row and each column contains alternating balck and white squares. Each of your rectangles, wherever it is placed, must cover one black and one white square. But the 62-square board we have to cover has 32 black and 30 white squares, so it can't be covered by our 31 pieces.

Q6. A, B and C are candidates in an election. There is an odd number of voters. The votes are counted and there is a three-way tie. As a tie-breaker the voters’ are asked for their second choices, and again there is a three-way tie. A suggests that, to break the tie, there be a two-way election between B and C, with the winner then facing A in another two-way election. Is this fair? And what is the probability that A would win the election if it were held in this way, assuming no voter changes their mind?

I found this one in the same book by Peter Winkler as Q4: it was originally devised by Ehud Friedgut. The answer is that A's proposal is very far from fair: the probability that A would win under that system is 1. Suppose B beats C in the two-way election: that means that the majority of A's voters prefer B to C. But B has exactly one-third of the second preferences so, to balance, a minority of C's supporters must prefer B to A. Since C's supporters will decide the two-way election between A and B, A will win that election. A symmetrical argument shows that if C beats B in the two-way election then A will beat C in the run-off. So A is guaranteed to win.

Q7. Here are two hidden messages. What do they say?

a) MERRY CHRISTMAS AND HAPPY NEW YEAR (this was originally written in invisible ink, ie in white text on a white background. Moving your mouse over it would reveal it!)


No-one submitted a correct solution to this one. It uses a Vigenere cipher, with the "keyword" chosen so that the first word comes out as AAAAA. My intention was that likely guesses, from the word lengths with part (a) as a clue, would be "MERRY CHRISTMAS" and "HAPPY CHRISTMAS", and testing them with a Vigenere solver would reveal which one it was. In fact the keyword was "TALLC" and the message "Merry Christmas".

Thursday, 14 January 2010

Christmas Quiz deadline extended

Because of the bad weather the deadline for the Christmas Quiz has been extended to 5pm on Monday 18 January.