8th Mexico 1994 Problem B1 A capricious mathematician writes a book with pages numbered from 2 to 400. The pages are to be read in the following order. Take the last unread page (400), then read (in the usual order) all pages which are not relatively prime to it and which have not been read before. Repeat until all pages are read. So, the order would be 2, 4, 5, ... , 400, 3, 7, 9, ... , 399, ... . What is the last page to be read?
37 Solution First read multiples of 2 and 5 (up to 400). Then since 399 = 3·7·19, read remaining multiples of 3, 7 and 19 up to 399. Then read 397 (a prime). Then read remaining multiples of 17 and 23 up to 391 (=17·23). Now all primes up to 23 have been covered except 11 and 13. Now the largest non-prime number not yet read must be divisible by 11 or 13 (since all multiples of smaller primes have already been read and 29 2 > 400), so the candidates are 377 = 13·29 and 341 = 11·31. So we keep reading primes until we get down to 377 and then read all remaining multiples of 13. We then read primes until we get down to 341, and then read all remaining multiples of 11. At this point the only remaining numbers are primes > 31. So we read them in reverse order, the last being 37. 8th Mexican 1994 © John Scholes jscholes@kalva.demon.co.uk 28 February 2004 Last corrected/updated 28 Feb 04