鴿籠

2023-02-14 23:12 作者:sxlxcsxlxc 0人讀過 | 我要投稿

不想復(fù)習(xí)。。。記錄一下?https://proofsfromthebook.github.io/25 前半部分的有趣問題

pigeonhole principle?https://en.wikipedia.org/wiki/Pigeonhole_principle

(1) 1，2，3，4，...，2n 中選 n+1 個(gè)，一定有兩個(gè)互質(zhì)

(2)?1，2，3，4，...，2n 中選 n+1 個(gè)，一定存在兩個(gè)元素,a,b, a|b

看起來就不那么顯然了。把1，2，3，4，...，2n 中的所有數(shù)字寫成a=b*2^k. b是奇數(shù)。b有n種可能，而我們選擇了n+1個(gè)元素。

(3) 一個(gè)有nm+1個(gè)數(shù)的sequence，沒有任何兩個(gè)數(shù)字相等。下面兩種情況至少滿足其一：

- 存在長度為m+1的上升子序列

- 存在長度為n+1的下降子序列

看起來也不是那么明顯了。假設(shè)序列中不存在長度為m+1的上升子序列。定義一個(gè)映射，from 序列中的每個(gè)元素 {a_1,a_2,.... , a_{mn+1} } to {1,2,...,m}，表示以一個(gè)元素開始的最長上升子序列的長度. 存在某個(gè) s \in??{1,2,...,m} ?序列中有至少n+1個(gè)元素開頭的最長上升子序列(LIS)長度都是s. 把這些LIS長度都是s的元素取出來形成新的子序列，可以發(fā)現(xiàn)相鄰兩個(gè)元素一定是前者小于后者（否則LIS的長度會變成s+1）因此這是一個(gè)長度至少是n+1的下降子序列。