16th Mexico 2002 Problem A1 The numbers 1 to 1024 are written one per square on a 32 x 32 board, so that the first row is 1, 2, ... , 32, the second row is 33, 34, ... , 64 and so on. Then the board is divided into four 16 x 16 boards and the position of these boards is moved round clockwise, so that AB goes to DA DC CB then each of the 16 x 16 boards is divided into four equal 8 x 8 parts and each of these is moved around in the same way (within the 16 x 16 board). Then each of the 8 x 8 boards is divided into four 4 x 4 parts and these are moved around, then each 4 x 4 board is divided into 2 x 2 parts which are moved around, and finally the squares of each 2 x 2 part are moved around. What numbers end up on the main diagonal (from the top left to bottom right)?
993, 962, ... , 63, 32 (originally the other main diagonal, from bottom to top) Solution We show by induction on n that for a 2 n x 2 n board we get the other main diagonal (OMD) from bottom to top. For n = 1 this is obvious. Suppose it is true for n. Now consider a 2 n+1 x 2 n+1 board. After the first move, the top left quadrant is the original bottom left quadrant which contains the bottom half of the OMD as its other main diagonal. Similarly, the bottom right quadrant is the original top right quadrant which contains the top half of the OMD as its other main diagonal. Hence, by induction, the subsequent moves give the OMD from bottom to top. 16th Mexican 2002 © John Scholes jscholes@kalva.demon.co.uk 5 March 2004 Last corrected/updated 5 Mar 04