close
Let A be a set containing n+1 integers. Show that it's always possible to choose two numbers, a and b, from A such that a-b is divisible by n.
首先將 Z 分散在 n 個集合, 分別從 A_0 到 A_(n-1),
定義 A_i 裡面的元素是 x=i (mod n)
這樣根據 Pigeonhole Principle, 至少有一個集合理面會有兩個元素來自 A。相減得 a-b=0 (mod n)
QED
全站熱搜
留言列表
