PUMaC 2014 · 组合（A 组） · 第 7 题
PUMaC 2014 — Combinatorics (Division A) — Problem 7
题目详情
- [ 7 ] Ding and Jianing are playing a game. In this game, they use pieces of paper with 2014 positions, in which some permutation of the numbers 1 , 2 , ... 2014 are to be written. (Each number will be written exactly once). Ding fills in a piece of paper first. How many pieces of paper must Jianing fill in to ensure that at least one of her pieces of paper will have a permutation that has the same number as Ding’s in at least one position?
解析
- [ 7 ] Tom and Jerry are playing a game. In this game, they use pieces of paper with 2014 positions, in which some permutation of the numbers 1 , 2 , ... 2014 are to be written. (Each number will be written exactly once). Tom fills in a piece of paper first. How many pieces of paper must Jerry fill in to ensure that at least one of his pieces of paper will have a permutation that has the same number as Tom’s in at least one positon? Solutions: Jerry writes 1 to 1008 for the first 1008 spots and for the 1008 different pieces of paper, he th cycle through the numbers such that the i paper will have i, i + 1 , ..., 1008 , 1 , 2 , ..., i − 1for the first 1008 position. Hence if any of the numbers { 1 , 2 , ..., 1008 } appears in the first 1008 position on Tom’s paper, Jerry would have gotten it right. Otherwise, Tom would have written th th the first 1008 numbers in the 1009 to 2014 position, which is clearly impossible as there are more numbers than positions. Thus Jerry can get it right in 1008 tries. With any 1007 pieces written, we shall show there exist a piece that doesn’t coincide with any th of the 1007 at any position. Let s be the set of 1007 numbers that occurs at the n position. n th We see that for the i position 1 ≤ i ≤ 1007, we can put in some number x such that x / ∈ s i and x is distinct from the i − 1 entries before which. th We continue assigning numbers until it is impossible at the j position. Let the set of numbers in the first j − 1 positions be s . Let S be the set of all 2008 numbers. We shall show it is th th possible to find l < j such that we can switch the number at the l position to the j position th and find another number for the l positon that avoids s . Assuming the contrary that no l such l exist, let us consider s/s . Since s ∪ s = S , we see that | s/s | ≥ 1007. Also S/s ∈ s . j j j j For any positon l which has number in s/s , we need that s ∪ s = S which is equivalent to j l S/s ∈ s . Thus S/s ∈ s for at least 1008 distinct i . this is clearly impossible. Hence we can al- l i ways find a position l to swap. Continuing this algorithm, we see that we can always construct a piece of paper that is distinct at every position from any 1007pieces of paper that Jerry picks.