PUMaC 2020 · 组合（A 组） · 第 6 题
PUMaC 2020 — Combinatorics (Division A) — Problem 6
题目详情
- In the country of Princetonia, there are an infinite number of cities, connected by roads. For every two distinct cities, there is a unique sequence of roads that leads from one city to the other. Moreover, there are exactly three roads from every city. On a sunny morning in early July, n tourists have arrived at the capital of Princetonia. They repeat the following process every day: in every city that contains three or more tourists, three tourists are picked and one moves to each of the three cities connected to the original one by roads. If there are 2 or fewer tourists in the city, they do nothing. After some time, all tourists will settle and there will be no more changing cities. For how many values of n from 1 to 2020 will the tourists end in a configuration in which no two of them are in the same city? ∑
解析
- In the country of Princetonia, there are an infinite number of cities, connected by roads. For every two distinct cities, there is a unique sequence of roads that leads from one city to the other. Moreover, there are exactly three roads from every city. On a sunny morning in early July, n tourists have arrived at the capital of Princetonia. They repeat the following process every day: in every city that contains three or more tourists, three tourists are picked and one moves to each of the three cities connected to the original one by roads. If there are 2 or fewer tourists in the city, they do nothing. After some time, all tourists will settle and there will be no more changing cities. For how many values of n from 1 to 2020 will the tourists end in a configuration in which no two of them are in the same city? Proposed by Aleksa Milojevic Answer: 19 . Solution: ( By Daniel Carter ) From the theory of abelian sandpiles, it doesn’t matter in what order the cities are considered for relocating tourists (or “collapsed”). Because of this, each suc- cessive final configuration may be found by adding one tourist to the capital and settling every- thing. Denote by c = ( a , a , a , ... ) the configuration associated with n tourists, where a ∈ n 0 1 2 i { 0 , 1 , 2 } is the number of tourists in any city i away from the capital. By symmetry, all of these cities will have the same number of tourists. Inductively, c k = (2 , 2 , ..., 2 , 0 , ... ) , c k = 3 · 2 − 4 3 · 2 − 3 (0 , 1 , 1 , ..., 1 , 0 , ... ), and c k = (1 , 1 , 1 , ..., 1 , 0 , ... ), with k twos, k ones, and k + 1 ones in a 3 · 2 − 2 row, respectively. This is easily verified for the base case k = 1, then by the independence of order c k = c k +1 = (2 , 2 , ..., 2 , 0 , ... ) with k + 2 twos. Adding one more and col- 2(3 · 2 − 2) 3 · 2 − 4 lapsing the first k + 1 cities gives (0 , 1 , 1 , ..., 1 , 3 , 0 , 1 , 0 , ... ) , (3 , 0 , 1 , ..., 1 , 0 , ... ) , (0 , 1 , ..., 1 , 0 , ... ) with k + 1 ones. Adding one more completes the inductive step. Finally, note that for any k k +1 number strictly between 3 · 2 − 2 and 3 · 2 − 3, there is nobody in any city more than k away from the capital, so some city must have two people by Pigeonhole Principle (there’s k only 3 · 2 − 2 cities up to that distance, yet more people). Hence, the condition is met only k k when n = 3 · 2 − 2 or n = 3 · 2 − 3 for k ∈ N , giving 19 solutions (1,3,4,9,10,21,22,...,1534). 4 ∑