Combinatorics (Fall 2010)/Problem set 2

Problem 1

1. 对任意的整数序列 [math]\displaystyle{ a_1,a_2,\ldots, a_n }[/math]， 证明存在 [math]\displaystyle{ 1\le j\le k\le n }[/math] 使得 [math]\displaystyle{ \sum_{i=j}^k a_i }[/math] 被 [math]\displaystyle{ n }[/math] 整除。
2. ( Erdős' favorite ) 令 [math]\displaystyle{ A\subset\{1,2,\ldots,2n\} }[/math] 且 [math]\displaystyle{ |A|=n+1\, }[/math]。则总存在不相等的 [math]\displaystyle{ j,k\in A }[/math] 有 [math]\displaystyle{ k\, }[/math] 被 [math]\displaystyle{ j\, }[/math] 整除。

提示：用鸽笼原理。