选几个数才能保证出现相邻整数
用五组覆盖和失败构造证明,从1到9选不同整数时保证出现差1的一对所需的最少个数。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 从一到九里选不同整数,要保证出现相差一的一对。先把“保证”理解为不管怎样选都一定发生。
- 把数字分成一二、三四、五六、七八四个相邻数对,再把九单独放一组,一共五组。
- 如果选六个数,六个选择放进五组,至少有一组会同时选中两个数;双数格里的两个数正好相差一。
- 为什么五个不够?可以选一、三、五、七、九,这五个数任意两个都不相差一。
- 所以选五个仍可能失败,选六个一定成功;能保证的最少个数是六。
- 证明最少值要做两件事:说明六个一定成功,还要给出五个失败的具体选法。
逻辑思维
分组上界与失败构造,并用反向检查确认。
看一个例子
从1到9中选不同整数,至少选几个,才能保证其中有两个数相差1?
6个。失败构造含5个不同数;五组覆盖1到9且互不重叠。
马上试一题
可分{1,2}{3,4}{5,6}{7}四组,选5个保证同组;选1、3、5、7仍可失败。