53锁男福利 (转载)

【 以下文字转载自 Military 讨论区 】
发信人: BroPingtou (ǢŦĦȆȐ), 信区: Military
标 题: 53锁男福利
发信站: BBS 未名空间站 (Tue Sep 21 22:43:20 2021, 美东)

从1到2n，2n个正整数

从中任选n+1个

证明或证伪:一定有一对能出现整除.
====================================
举例:

n = 3
{1,2,3,4,5,6}

去出{2,3,4,5}，则2 | 4

给第一个提示:

可以证明此命题

分成n组每组两个， 取n+1个数的话，根据鸽笼原理，至少有一组两个数都要取。

【 在 BroPingtou (ǢŦĦȆȐ) 的大作中提到: 】
: 给第一个提示:
: 可以证明此命题

举个例子上面的{1,2,3,4,5,6}怎么分三组？
【 在 fhnan (腹黑男) 的大作中提到: 】
: 分成n组每组两个， 取n+1个数的话，根据鸽笼原理，至少有一组两个数都要取。

两两分组不行啊
可以按照k*2^m.
k相同的分到一组
1 2 4 8 16
3 6 12
5 10
7 14
9
11
13
15

需要证明分组个数小于等于n 或者里面只有一个数字的分组个数小于n

【 在 BroPingtou (0803030303) 的大作中提到: 】
: 举个例子上面的{1,2,3,4,5,6}怎么分三组？

可以给每个奇数一个分组 然后偶数总可以找到一个分组 放到这个分组后 分组里面任
意两个数 都可以整除

【 在 BroPingtou (0803030303) 的大作中提到: 】
: 举个例子上面的{1,2,3,4,5,6}怎么分三组？

对 每个奇数一个分组 k=这个奇数。偶数总可以找到一个分组让它等于k*2^m

【 在 fhnan (腹黑男) 的大作中提到: 】
: 两两分组不行啊
: 可以按照k*2^m.
: k相同的分到一组
: 1 2 4 8 16
: 3 6 12
: 5 10
: 7 14
: 9
: 11
: 13
: ...................

嗯，我再想想细节。

倾向于这是正确的

【 在 fhnan(腹黑男) 的大作中提到: 】

: 对 每个奇数一个分组 k=这个奇数。偶数总可以找到一个分组让它等于k*2^m

不错，奖励20伪币
【 在 fhnan (腹黑男) 的大作中提到: 】
: 对 每个奇数一个分组 k=这个奇数。偶数总可以找到一个分组让它等于k*2^m