10th Mexico 1996 Problem A2 64 tokens are numbered 1, 2, ... , 64. The tokens are arranged in a circle around 1996 lamps which are all turned off. Each minute the tokens are all moved. Token number n is moved n places clockwise. More than one token is allowed to occupy the same place. After each move we count the number of tokens which occupy the same place as token 1 and turn on that number of lamps. Where is token 1 when the last lamp is turned on?
32 Solution Label the positions 1 to 64, so that initially token k is in position k. Token k gets to position m+1 after m moves iff (m+1)k = m+1 mod 64 or (k-1)(m+1) = 0 mod 64. So if k ≠ 1, then m+1 must be a power of 2. If 2 n is the highest power of 2 dividing m+1, then k-1 must be divisible by 2 6-n . So if m+1 = 2, 6, 10, 14, 18, ... , then only 33 shares a place with token 1. If m+1 = 4, 12, 20, 28, 36, ..., then 17, 33, 49 share a place with token 1. If m+1 = 8, 24, 40, 56, ..., then 9, 17, 25, 33, 41, 49, 57 share a place with token 1. If m+1 = 16, 48, 80, ..., then 15 numbers share a place with token 1. If m+1 = 32, 96, 160, ..., then 31 numbers share a place with token 1, and if m+1 = 64, 128, 192, ..., then 63 numbers (all of them) share a place with token 1. So in the first 64 moves, 32·1 + 16·2 + 8·4 + 4·8 + 2·16 + 1·32 = 192 numbers share a place with 1. After 64 moves every token is back at its starting point. So after 10 such rounds 1920 bulbs are turned on and all the numbers are back at their starting points. Now when 1 reaches 31 on the next round we another 1+3+1+7+1+3+1+15+1+3+1+7+3+1 = 48 lights are turned on, for a total of 1968. When it moves to 32 the remaining 28 lights are turned on. 10th Mexican 1996 © John Scholes jscholes@kalva.demon.co.uk 9 March 2004 Last corrected/updated 9 Mar 04