PUMaC 2020 · 个人决赛（B 组） · 第 1 题
PUMaC 2020 — Individual Finals (Division B) — Problem 1
题目详情
- Find all pairs of natural numbers ( n, k ) with the following property: Given a k × k array of cells, such that every cell contains one integer, there always exists a path from the left to the right edges such that the sum of the numbers on the path is a multiple of n . Note: A path from the left to the right edge is a sequence of cells of the array a , a , . . . , a 1 2 m so that a is a cell of the leftmost column, a is the cell of the rightmost column, and a , a 1 m i i +1 share an edge for all i = 1 , 2 , . . . , m − 1.
解析
- Find all pairs of natural numbers ( n, k ) with the following property: Given a k × k array of cells, such that every cell contains one integer, there always exists a path from the left to the right edges such that the sum of the numbers on the path is a multiple of n . Note: A path from the left to the right edge is a sequence of cells of the array a , a , . . . , a 1 2 m so that a is a cell of the leftmost column, a is the cell of the rightmost column, and a , a 1 m i i +1 share an edge for all i = 1 , 2 , . . . , m − 1. Answer: The pair ( n, k ) satisfies the above property if and only if n ≤ k . Solution : The proof consists of two parts. In case n > k , we will construct an array of cells which does not has the above property, while in case n ≤ k we will prove that the property always holds. If n > k , consider the following array: let all the columns but the rightmost one be filled with all zeroes and the rightmost with all ones. Then every path from the left edge to the right edge has the sum at least one, and at most k . As n > k , this means none of the possible sums is divisible by n , which completes the construction. In case n ≤ k , let the sum of numbers in the row i be R . We will first prove that there is i a there is a contiguous segment R , ..., R such that the sum R + · · · + R is divisible by n . i j i j Consider the sums S = R , S = R + R , . . . , S = R + · · · + S . Then, either one of the S 1 1 2 1 2 k 1 k i is divisible by n or all of them have non-zero residues modulo n . In the first case, the segment R , . . . , R is a contiguous segment satisfying the above property. In case all residues of S are 1 i i non-zero, by Pigeonhole principle, there must be two sums which have the same residue, say S ≡ S ( mod n ). This means that n | S − S = R + · · · + R , which provides the wanted i j j i i +1 j contiguous segment. Now, it is easy to construct a path passing only the cells from the rows i, . . . , j . It suffices to go column by column, passing the whole column before going onto the next one. Proposed by Pavle Martinovi´ c.