PUMaC 2019 · 组合（A 组） · 第 7 题
PUMaC 2019 — Combinatorics (Division A) — Problem 7
题目详情
- In the country of PUMACsboro, there are n distinct cities labelled 1 through n . There is a rail line going from city i to city j if and only if i < j ; you can only take this rail line from city i to city j . What is the smallest possible value of n , such that if each rail line’s track is painted orange or black, you can always take the train between 2019 cities on tracks that are all the same color? (This means there are some cities c , c , . . . , c , such that there is a rail 1 2 2019 line going from city c to c for all 1 ≤ i ≤ 2018, and their rail lines’ tracks are either all i i +1 orange or all black.) 2
解析
- In the country of PUMACsboro, there are n distinct cities labelled 1 through n . There is a
rail line going from city i to city j if and only if i < j ; you can only take this rail line from
city i to city j . What is the smallest possible value of n , such that if each rail line’s track is
painted orange or black, you can always take the train between 2019 cities on tracks that are
all the same color? (This means there are some cities c , c , . . . , c , such that there is a rail
1 2 2019
line going from city c to c for all 1 ≤ i ≤ 2018, and their rail lines’ tracks are either all
i i +1
orange or all black.)
Proposed by Reed Jacobs.
Answer: 4072325 .
Solution: We translate this into graph theory and solve a more generalized problem: Given
↑
a positive integer n , consider a complete directed graph K whose vertices are n distinct real
n
numbers. If r < s are two vertices, direct edge { r, s } to go out of r and into s . What is
↑
the smallest positive integer n , such that when the edges of K are colored with c colors, a
n
monochromatic directed path of length
is guaranteed? For every vertex x and integer 1 ≤ i ≤ r , let a ( x, i ) be the number of edges in the longest monochromatic directed path of color i which ends at x . The problem is equivalent to showing c that some a ( x, i ) is at least ` − 1; suppose this does not hold. Then there are at most ( ` − 1) possible tuples ( a ( x, 1) , . . . , a ( x, a )). Also, note that any two of these tuples are distinct; ↑ the definition of K ensures the existence of a suitably directed edge, and the tuples differ n c at that edge’s color. If we take n = (− 1) + 1, we obtain a contradiction. Exhibiting a ↑ coloring of K with c colors that has no monochromatic directed paths of lengthis left c (− 1) to the reader; as a hint, arrange the vertices in a c -dimensional hypercube. So the answer is 2 (2019 − 1) + 1 = 4072325. 2