選幾個數才能保證出現相鄰整數
用五組覆蓋和失敗構造證明,從1到9選不同整數時保證出現差1的一對所需的最少個數。
影片暫時無法載入。請檢查網絡後重試,或直接下載影片。
下載影片
展開影片文字稿
- 从一到九里选不同整数,要保证出现相差一的一对。先把“保证”理解为不管怎样选都一定发生。
- 把数字分成一二、三四、五六、七八四个相邻数对,再把九单独放一组,一共五组。
- 如果选六个数,六个选择放进五组,至少有一组会同时选中两个数;双数格里的两个数正好相差一。
- 为什么五个不够?可以选一、三、五、七、九,这五个数任意两个都不相差一。
- 所以选五个仍可能失败,选六个一定成功;能保证的最少个数是六。
- 证明最少值要做两件事:说明六个一定成功,还要给出五个失败的具体选法。
邏輯思維
分組上界與失敗構造,並用反向檢查確認。
看一個例子
從1到9中選不同整數,至少選幾個,才能保證其中有兩個數相差1?
6個。失敗構造含5個不同數;五組覆蓋1到9且互不重疊。
立即試一題
可分{1,2}{3,4}{5,6}{7}四組,選5個保證同組;選1、3、5、7仍可失敗。