PUMaC 2014 · 个人决赛（A 组） · 第 3 题
PUMaC 2014 — Individual Finals (Division A) — Problem 3
题目详情
- There are n coins lying in a circle. Each coin has two sides, + and − . A flop means to flip every coin that has two different neighbors simultaneously, while leaving the others alone. For instance, + + − +, after one flop , becomes + − −− . For n coins, let us define M to be a perfect number if for any initial arrangement of the coins, the arrangement of the coins after M flops is exactly the same as the initial one. (a) When n = 1024, find a perfect number M . (b) Find all n for which a perfect number M exist. 1
解析
- There are n coins lying in a circle. Each coin has two sides, + and . A flop means to flip every coin that has two di ↵ erent neighbors simultaneously, while leaving the others alone. For instance, + + +, after one flop , becomes + . For n coins, let us define M to be a perfect number if for any initial arrangement of the coins, the arrangement of the coins after M flops is exactly the same as the initial one. (a) When n = 1024, find a perfect number M . (b) Find all n for which a perfect number M exist. Solution: (a) By part (b), since M exist, then any initial arrangement will cycle after x flops for some n n x 2 Hence if we let M = 2 ! , x | M will necessarily be true and hence at M flops , it M 1024 will return to the initial position for the time. Thus (2 )! is a perfect number. x (b) We see that for 3 | n , there can be no perfect number as + + + + ... + + after one flop will become ... and it is clear that this will remain this way for any future flops and therefore can never return to its initial arrangement. For 3 - n , let us consider the following: We can replace the + with 1 and with 1. th Let a denote the value of the k coin after x flops . We see that with each flop , k,x 2 a = a a a . Note that a = 1 k,x k 1 ,x 1 k,x 1 k +1 ,x 1 k,x We see that for n = 3 m + 2, we can write a = a a a a a ...a a k,x k,x +1 k +2 ,x +1 k +3 ,x +1 k +5 ,x +1 k +6 ,x +1 k 3 ,x +1 k 2 ,x +1 and expanding, we can verify this to be true as a = ( a a a )( a a a )( a a a ) ... ( a a a )( a a a ) k,x k 1 ,x k,x k +1 ,x k +1 ,x k +2 ,x k +3 ,x k +2 ,x k +3 ,x k +4 ,x k 4 ,x k 3 ,x k 2 ,x k 3 ,x k 2 ,x k 1 ,x which we can group into 2 2 2 2 2 a = a a a a + ...a a k,x k,x k 1 ,x k +1 ,x k +2 ,x k 3 ,x k 2 ,x which is clearly true. Similarly, we see that for n = 3 m + 1, we can write a = a a a a a ...a a k,x k,x +1 k +1 ,x +1 k +3 ,x +1 k +4 ,x +1 k +6 ,x +1 k 3 ,x +1 k 1 ,x +1 2 and expanding, we can verify this to be true as a = ( a a a )( a a a )( a a a ) ... ( a a a )( a a a ) k,x k 1 ,x k,x k +1 ,x k,x k +1 ,x k +2 ,x k +2 ,x k +3 ,x k +4 ,x k 4 ,x k 3 ,x k 2 ,x k 2 ,x k 1 ,x k,x which we can group into 2 3 2 2 2 2 a = a a a a + ...a a k,x k 1 ,x k,x k +1 ,x k +2 ,x k 3 ,x k 2 ,x which is clearly true. Therefore, we see that for 3 - n , position after x flops will determine uniquely the position after x 1 and after x + 1 flops . Since there is a finite number of positions possible, it must eventually cycle after some time and since any position uniquely determine the one before and after, the cycle must include the intitial position. Hence M exist only for all n where 3 - n . 3