9th Mexico 1995 Problem A1 N students are seated at desks in an m x n array, where m, n ≥ 3. Each student shakes hands with the students who are adjacent horizontally, vertically or diagonally. If there are 1020 handshakes, what is N?
280 Solution Students in the corner shake hands 3 times, those on the sides 5 times and those in the middle 8 times. So the total number of handshakes is (4·3 + (2m-4+2n-4)5 + (m-2)(n-2)8)/2 = (12 + 10m + 10n - 40 + 8mn - 16m - 16n + 32)/2 = (16mn - 12m - 12n + 8)/4 = (4m - 3)(4n - 3)/4 - 1/4 = 1020, so (4m-3)(4n-3) = 4081 = 7·11·53. Now 7 = 3 mod 4, 11 = 3 mod 4 and 53 = 1 mod 4, so we must have 4m-3 = 77, 4n-3 = 53 (or vice versa) and hence N = mn = 20·14 = 280. 9th Mexican 1995 © John Scholes jscholes@kalva.demon.co.uk 28 February 2004 Last corrected/updated 28 Feb 04