[今天我们思考03]归纳题

[pongba]

讨论的目的见这里。

这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。

先提几道经典的：
1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul Erdos用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）
2. 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
    3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？

（友情感谢silwile提供题目^_^）

P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。

P.S. 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意忘形:-) 所以，我觉得，所有有可能带领你发现灵感的一般性思路，都有卓越的价值。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[windstorm]

pongba, 提个建议，这种活动两天一次可能更好一些

我不知道是不是有很多人每天都有时间上来看，我今天打开邮箱，就一下子看到两个我们思考的帖子，我不一定能一天之内全部消化完，然后可能明天又会出来新的......

其实2，3天一次，留给所有人的理解，思考，发散思维的时间可能更多一些

个人建议

[pongba]

2008/4/11 windstorm <likunar...@gmail.com>:

好，我也有这个想法:-)
P.S. 大家都想想有什么印象深刻的题目，即反映了某些重要的一般性思维规则的题目，提出来大家多多讨论:)

[hayate]

第一题互相整除啥意思？
互相整除不是相等么

2008/4/11 pongba <pon...@gmail.com>:

[pongba]

2008/4/11 hayate <haya...@gmail.com>:

第一题互相整除啥意思？
互相整除不是相等么

说错了，是"存在整除关系":) 一个整除另一个。

[鋆邓]

第一题：做过的……而且觉得很简单，不过我只知道一种证明，大概只有3、4行，不知道所谓"规矩"的证明是何……
第二题：决定午饭时间思考思考。
第三题：经典算法……O(N)。
    3.1： 曾思考过，但没有过完美的结论。顺便，用hash是很显然的O(N)。但需要额外内存。

2008/4/11 pongba <pon...@gmail.com>:

[pongba]

2008/4/11 鋆邓 <tdzl...@gmail.com>:

第一题：做过的……而且觉得很简单，不过我只知道一种证明，大概只有3、4行，不知道所谓"规矩"的证明是何……

"规矩"的证明就是拿数学归纳法做；但证明的过程也并不简单。

[pongba]

2008/4/11 鋆邓 <tdzl...@gmail.com>:

第一题：做过的……而且觉得很简单，

一些人的简单在另一些人看并不简单，反之也成立。所以必然是头脑中的知识结构和推理习惯差异造成的。总结造成这个差异的根源是很有意义的。比如你为什么很快就想到那个关键的一步，之前你都想了些什么，它们是怎样对你最终想到关键的一步产生作用的？

[鋆邓]

n+1 直接想到鸽笼定理

午饭时间和同事讨论wow讨论得热血朝天，把题目给忘了，呜呜……

2008/4/11 pongba <pon...@gmail.com>:

[鋆邓]

第二题难以想到O(N)的算法
只想到N+M的算法，M为给定的关系数目

2008/4/11 鋆邓 <tdzl...@gmail.com>:

[pongba]

2008/4/11 鋆邓 <tdzl...@gmail.com>:

n+1 直接想到鸽笼定理

鸽笼原理这个容易想到。但问题是如何构造笼子就不是那么trivial得了。

[鋆邓]

那么你就把它分成不超过N堆……使得任意一堆里选两个数都必然存在倍数关系
然后就可以整出来了，2N以内每一个奇数及其所有2的整次方倍为一堆。

2008/4/11 pongba <pon...@gmail.com>:

[pongba]

2008/4/11 鋆邓 <tdzl...@gmail.com>:

那么你就把它分成不超过N堆……使得任意一堆里选两个数都必然存在倍数关系

这一步当时我也想到了。但是要找出这样的一个划分，并不是trivial的啊。这样的划分大概是没办法通过划分的需求反演出来的；只能通过联想和试错，我当时试了几种处理方法都不得要领。

那么，问题是你是怎么想到这样处理这2N个数的呢？

[鋆邓]

因为先想到N，又有题目中范围为2N，就想到按奇偶划分，首先想到的是将每个数和它的2倍一起，但这样是不正确的，因为有些数的2倍不在范围内，但这样的思路已经得到一个结论，就是奇数必然是不同堆的，剩下的事情就是把偶数重新放到正确的堆里就好了。

2008/4/11 pongba <pon...@gmail.com>:

[pongba]

2008/4/11 鋆邓 <tdzl...@gmail.com>:

因为先想到N，又有题目中范围为2N，就想到按奇偶划分，首先想到的是将每个数和它的2倍一起，但这样是不正确的，因为有些数的2倍不在范围内，但这样的思路已经得到一个结论，就是奇数必然是不同堆的，剩下的事情就是把偶数重新放到正确的堆里就好了。

Good Point!:)
我知道答案之后反过来揣测别人是怎么联想到的，也是想到的是这一解释。Thanks:)

[hayate]

:( 我没有sense
这个划分我想不出来

2008/4/11 pongba <pon...@gmail.com>:

[ZhangShen Peng(Uestc graduating...)]

第2条.

好像是算法导论的,就是求所有人认识的人的交集.求交集用一个n数组来&&运算,最后得到大家都认识的人.

第3条.
好像还是算法导论的

在n中为众数在,去除两个不一样的数仍然为众数,如此递归

然后两遍扫描,第一遍,找到不一样的数字并去掉,最后如果可以得到一个数字,再扫描一遍统计是否是众数

def count(array):
pos=0
max_count=0
max_number=None
for i in range(len(array)-1,0,-1):
if pos>=i:
break
a_i=array[i]
if array[pos]==a_i:
if a_i==max_number:
max_count+=2
elif max_count>=2:
max_count-=2
else:
max_count=2-max_count
max_number=array[i]
pos+=1
if max_number is not None:
count=0
for i in array:
if i==max_number:
count+=1
if count*2>len(array):
return max_number
else:
return None

while True:
from random import randint
array=[]
for i in range(6):
array.append(randint(1,3))
print array,count(array)

第3.1条.
泛化：如果找出现次数>n/3呢？>n/4呢？
同时去除3个不一样的数字仍然>n/3,最后可能得到2个数字........

2008/4/11 pongba <pon...@gmail.com>:

--
Blog(Chinese Edition):
http://zsp.javaeye.com/
Resume(Also Chinese):
http://zsp007.com.cn/
Where graduate soon , where to go ......
Double major:
Biomedical Engineering
Computer Science
-- Hierarch Zhang

[heave...@gmail.com]

第1题，

我想到的是根据素数的划分，

2和2的倍数一堆，

3和3的倍数一堆，但不包括2的倍数，

5和5的倍数一堆，但不包括2，3的倍数，

一次类推，

假设这2n个数字，一共划分成m堆，也就是说2n内有m个素数。

而肯定 m<=n

所以不论n是多少，肯定m<n+1，

也就是说，如果任意取的话，肯定会从某一个堆中至少拿2个数字，

而这2个同一个堆里拿出来的是肯定整除的。



On 4月11日, 上午5时52分, pongba <pon...@gmail.com> wrote:
> 讨论的目的见这里 <http://blog.csdn.net/pongba/archive/2008/04/09/2270171.aspx>。

>
> 这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。
>
> 先提几道经典的：
> 1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul

> Erdos<http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fwww.cise....>

> 用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）
> 2.

> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的-）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。

> 3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
> 3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？
>

> （友情感谢silwile <http://www.douban.com/people/silwile/>提供题目^_^）

>
> P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
> 点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。
>
> P.S.

> 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接-把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意-忘形:-)

[heave...@gmail.com]

第2题

想到的是类似投票的感觉。

如果a认识b，那么就是a投了b 1票。

这样到最后，如果有名人，那么根据条件，必有一人的得票为n，

同时这个人还不认识其他人。

实现上就是2个数组，

一个int的，一个bool的，

第一个用来记录每人的得票数，第二个用来记录此人是否投票过给其他人。

这样遍历一次n个人的关系就可以。

On 4月11日, 上午5时52分, pongba <pon...@gmail.com> wrote:
> 讨论的目的见这里 <http://blog.csdn.net/pongba/archive/2008/04/09/2270171.aspx>。
>

> 这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。
>
> 先提几道经典的：
> 1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul

> Erdos<http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fwww.cise....>

> 用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）
> 2.

> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的-）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。

> 3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
> 3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？
>

> （友情感谢silwile <http://www.douban.com/people/silwile/>提供题目^_^）

>
> P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
> 点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。
>
> P.S.

> 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接-把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意-忘形:-)

[hayate]

9和15 都是3的倍数 但是9不整除15

2008/4/11 heave...@gmail.com <heave...@gmail.com>:

[pongba]

有人想出来这道题吗？

The set of numbers {9, 99, 999, 9999, ...} has some interesting properties. One of these has to do with factorization. Take any number n that isn't divisible by 2 or by 5. You will be able to find at least one number in the set that is divisible by n. Furthermore, you won't need to look beyond the first n numbers in the set.

Prove it.

2008/4/11 pongba <pon...@gmail.com>:

[hayate]

看起来好"数论"啊

2008/4/11 pongba <pon...@gmail.com>:

[ZhangShen Peng(Uestc graduating...)]

第一条:

1 每1个连续的数中有一个倍数
2 每2个连续的数中有一个倍数
...
n 每n个连续的数中有一个倍数

一开始想了很久,只想到上面这些步骤,然后晚上写了一会其他代码,上厕所时有了灵感,也 不知道对不对
______________________
取法1.
1 n+1 .... n+n
2 n+1 .... n+n
....
n n+1 .... n+n
这种取法从1-n,都保证有倍数

取法2.
n-1 n | n+1 .... 2n (去掉一个数字)
这边必然存在n的倍数或n-1倍数两种中的一个(因为连续,为n个连续的数字,只缺一个)
n-2 n | n+1 .... 2n (去掉一个数字)
这边必然存在n的倍数或n-2倍数两种中的一个
.....
......
.......

类推,得证

2008/4/11 hayate <haya...@gmail.com>:

--

[hayate]

呃 知道答案了
刚才复习了一下数论的基本定理就知道了....
sigh.... 猜得，没有成就感

2008/4/11 hayate <haya...@gmail.com>:

[pongba]

昨晚想了一个多小时，试了N种路径，演算了4张纸，还是没导出来。

我主要用了两种处理办法：

1. 表示为5q+r，其中q,r不同奇同偶。然后证明这个数能乘以某个数到达某个999... 进一步表达为10u+1，10u+3，10u+7，10u+9。看起来里面出现了10，特别是10u+1和999...的另一种表达(10^k-1）似乎很接近，只要找到一个f(u)使得(10u+1)f(u) = 10^k-1即可，想到x^k-1的因式分解，但最终还是没有试出来。

2. 在尝试第一种手法的过程中意识到还有一种表达方式（实际上本应首先想到这一种的，但是数论不熟悉，所以..）：p1^r1*p2^r2...pn^rn...其中pi是素数因子，且pi不等于2和5。这个表达式也等价于所有符合条件的n。然后要证明某个999...可以整除这个数，我试图分两步来证：1)证只要9足够多，某个..999...分解因式之后总能覆盖到任何一个素数，这样就不会出现永远无法除以某个n的情况。2)证...999...只要足够长，其每个素数上的方数总能足够大，这就保证了能够整除每种可能的p1^r1*p2^r2...pn^rn...。虽然1)证出来了。但2)怎么都证不出来。到这里基本就放弃了，回家洗洗睡了...

后来睡觉了还在想，不过还是试图从以上两种手法来推导，尤其是第二种。结果是dead end，遂在绝望中睡去...梦见捡了一大堆钱包交给警察叔叔...-_-||| :P 早晨醒来，回顾解题过程，回想起来实际上昨天还用了一个比较平凡的手法，只不过当时不记得什么原因把它给枪毙掉了，但回想起来的时候忽然发现似乎是可以解出来的，这个方法就是老掉牙的待定系数法：既然每个n都无非是10u+1，10u+3，10u+7，10u+9，我们不妨就说10u+1的情况，要让它乘以某个数到达..999...，我们就是要让那个乘数的（倒数）第一位是9，然后，为了让结果的（倒数）第二位也是9，我们可以确定出乘数的（倒数）第二位，为了让结果的（倒数）第三位是9，可以确定出乘数的（倒数）第三位，以此类推。用这个方法也显而易见为什么乘数最多只需n位即可，以及为什么一定存在这个乘数（用互素性证明）。

想起来当时为什么把它枪毙掉了，因为我将10u+1表达为akak-1ak-2...a11（最末尾是1的任何数），然后想到乘以某个数其实就是把这个数加上自身多少次，于是我列了一个纵向的式子，注意到这个加式的最后一位的和mod10必须是9否则加起来最后一位不可能是9，然后往（倒数）第二位看的时候就傻眼了，因为这个式子实在列得不直观。实际上只要模拟一遍平常做乘法的步骤就可以了... 归根到底还是忽视了最常用的手法，因为本以为这个放在"relatively hard"区的题目要用到non-trivial的手法的...

对了，想起来了中途还试图用归纳法来证：对每个素数因子的乘方数作归纳，结果发现这个乘方数序列编码为一个无穷维，每维上的分量都是1~无穷大的向量，是不可数的，自然就没法从k的情况到k+1的情况了...

2008/4/11 hayate <haya...@gmail.com>:

[ZhangShen Peng(Uestc graduating...)]

早上起来,第无数次向google投简历(估计还是石沉大海).

忽然对"点猜"有了灵感

假设每条直线至少过3个点,则任取3点必然共线
a b c e ........
a与b,c共线
e与b,c共线
=>a,b,c,e共线
=>类推,所有点共线,不合题设

得证

不过既然是一道这么难的题目,证明肯定不可能这么简单.一定是我什么地方做错了.........
但是那里错了呢？。。。。。。。。。。。。。。。。。。。

[pongba]

2008/4/12 ZhangShen Peng(Uestc graduating...) <zsp...@gmail.com>:

早上起来,第无数次向google投简历(估计还是石沉大海).

忽然对"点猜"有了灵感

假设每条直线至少过3个点,则任取3点必然共线

不成立:-)

[ZhangShen Peng(Uestc graduating...)]

能给一个反例吗？ 假设每条直线至少过3个点,但是存在有3点不共线的例子，我没想出来

On 4/12/08, pongba <pon...@gmail.com> wrote:

[ZhangShen Peng(Uestc graduating...)]

去吃饭时想到我错了
假设应该成立,但是是一个等价命题...........

[ZhangShen Peng(Uestc graduating...)]

再来一个更绕头的证明,应该存在更隐蔽的Bug

假设每条直线至少过3个点
任取2点必然有另外一点与之共线
考虑点
1 2 3 4 ........ n

1 2 x 共线
有点y与1 2 x 不共线
存在一个新的点z与1 y共线=>z与2 x不共线
存在一个新的点m与2 z共线=>m与前面的(1 2 x)(1 y z)不共线(可以先假设m与(1 2 x)共线=>z与(1 2 x
m)共线,且y在(1,z)即(1 2 x)上=>矛盾)
......
可以无限的推下去
推出有无穷个点,不符合题设

[hayate]

:) 很好很强大

我没花这么多功夫，但其实没有收获。因为看到整除和并且和互素有关，我就先去把相关定理熟悉了一下----偏偏正好我想看的第一个定理就可以直接推出结果。

定理就是欧拉定理和费马小定理。

当把999...9 写成 10^n -1 的时候立刻就发现了，因为按照欧拉定理，如果10和n互素，那么 10^f(n) mod n = 1 mod n，f(n)是比n小的某个数......明显吧...

搞不好你可以看看，你是不是把欧拉定理给证了一遍，我没有教材，所以没看其过程。

另外，我的感觉，如果把数论中的结果包装一下做成这种智力题，可以弄出很多难题啊.... 因为数论本身就是很超越直觉的，sigh

2008/4/12 pongba <pon...@gmail.com>:

[王小康]

弱弱的问一句,关于第一题:

n=1.那么之存在1,和2这两个数.取1+1=2两个数:1,2.那么1可以整除2,2可以整除1??????


见笑了,看了半天没看明白

在08-4-12，hayate <haya...@gmail.com> 写道：

[pongba]

2008/4/12 王小康 <egm...@gmail.com>:

弱弱的问一句,关于第一题:

n=1.那么之存在1,和2这两个数.取1+1=2两个数:1,2.那么1可以整除2,2可以整除1??????


见笑了,看了半天没看明白

sorry，条件写错了，只要其中一个能整除一个即可。

[pongba]

2008/4/12 ZhangShen Peng(Uestc graduating...) <zsp...@gmail.com>:

再来一个更绕头的证明,应该存在更隐蔽的Bug

假设每条直线至少过3个点
任取2点必然有另外一点与之共线
考虑点
1 2 3 4 ........ n

1 2 x 共线
有点y与1 2 x 不共线
存在一个新的点z与1 y共线=>z与2 x不共线
存在一个新的点m与2 z共线=>m与前面的(1 2 x)(1 y z)不共线(可以先假设m与(1 2 x)共线=>z与(1 2 x
m)共线,且y在(1,z)即(1 2 x)上=>矛盾)
......
可以无限的推下去

需要严格说明这种手法可以无限地找出新点；需要形式化地说明这个寻找新点的手法的过程。

[ZhangShen Peng(Uestc graduating...)]

详细的写了一下构造方法,请刘老大指教
________________
假设每条直线至少过3个点
任取2点必然有另外一点与之共线

考虑点
1 2 3 4 ........ n

令1 2 3共线,有题设得到有
4与1 2 3不共线
此时存在线段(1 4)(2 4)(3 4)(1 2 3)

又因为 任取2点必然有另外一点与之共线

存在点5与(1 4)共线且与(2 4)(3 4)(1 2 3)不共线或与 2或3重合 (否则根据两点定一直线都可以推出4与(1 2 3)共线)
=>5是一个新的点
此时存在线段(2 4)(3 4)(2 5)(3 5) (1 2 3) (1 4 5)

存在点6与(2 4)共线且与其他线都不共线且不与以往的点重合(因为(2,4)与其他原有点不共线)
=>6是新点
此时存在线段(3 4)(2 5)(3 5)(1 6)(3 6)(5 6) (1 2 3) (1 4 5) (2 4 6)

label next:
每为一个只有两点线段找第三点,都可以保证第三点与原有点不重合,与原有线段线段不共线.=>是一个新点
而每增加一个这样的点,将增加>1条的只有两个点的线段,goto next:

2008/4/12 pongba <pon...@gmail.com>:

--

[ZhangShen Peng(Uestc graduating...)]

刚刚到网上找到了
<<费马大定理>>
上传到这里:)
权当YY小说看
http://pongba.googlegroups.com/web/%E8%B4%B9%E9%A9%AC%E5%A4%A7%E5%AE%9A%E7%90%86.rar?gda=Q3WI7GIAAAAZjO1Cx6SHkJNJdewHUrhumWYFUThGOFBAwcd2rmBxpmG1qiJ7UbTIup-M2XPURDRPJTfBM_OCBBMUEzEbkBlVwI9pbmPfeHJf2NpBqzLsDosU9YXpfwvSp909ONtTtip0xCTqDOw4Cs1bwhQEschW&gsc=Ga0gDgsAAAAir4lvQR1JhRETcGaRF9bG

--
~~~~~~~~~~~~~~~~~~~~~~~~~

Blog(Chinese Edition):
http://zsp.javaeye.com/
Resume(Also Chinese):
http://zsp007.com.cn/

Graduating , where to go ......

Double major:
Biomedical Engineering
Computer Science

-- Hierarch Zhang(张教主)

[lbaby]

第一个和素数的求法有关，

有这样一个算法，将 1 -n 中的 数=，从 2 至n的平方根，两两相乘，把相乘的结果从这个列中划去，
重复这个算法，直到 没有数被划去，余下的数，就是素数了
这个算法是筛法的变形，是我在大二时为了快速求某范围内的素数时"发明"的

对于这个题可以对非素数的个数和我们选n +1 的数作鸽巢，

On Apr 11, 11:52 am, pongba <pon...@gmail.com> wrote:
> 讨论的目的见这里 <http://blog.csdn.net/pongba/archive/2008/04/09/2270171.aspx>。
>

> 这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。
>
> 先提几道经典的：
> 1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul

> Erdos<http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fwww.cise....>

> 用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）
> 2.

> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的-）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。

> 3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
> 3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？
>

> （友情感谢silwile <http://www.douban.com/people/silwile/>提供题目^_^）

>
> P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
> 点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。
>
> P.S.

> 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接-把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意-忘形:-)

[hyifeng]

点猜想问题：
设有M个点，那么任意两点连结成的直线有 (M, 2) = M(M-1)/2 条。
现在假设有 X1，X2，X3，...Xn 点集，各个点集共线，并且Xj(j = 1 to n) >= 3
所以 M >= X1+X2+X3+...Xn = Z
因为Xj(j = 1 to n)中的点集共线，所以，(Xj, 2)条两点直线重合，
即剩下的只过两点的直线数
R = (M, 2) - (X1, 2) - (X2, 2) - ...(Xn, 2)
求证当Z<M 时 R>0
因为
M(M-1) - X1(X1-1) - ... Xn(Xn-1)
= M^2 - M - (X1^2 - X1) - ...(Xn^2 - Xn)
= M^2 - M - (X1^2+X2^2+...Xn^2) + (X1+X2+..Xn)
因为M = Z+(M-Z) = X1+X2+...Xn + (M-Z)
所以
M^2
= [X1+X2+...Xn + (M-Z)]^2
= (X1^2+X2^2+..Xn^2) + (M-Z)^2 + 2[X1*X2 + X1*X3+...X2*X3 +
X2*X4+...Xn*(M-Z)]

M^2 = (X1^2+X2^2+..Xn^2) + (M-Z)^2 当且仅当 X1=Z=M

代入原式得
当Z<M时，M(M-1) - X1(X1-1) - ... Xn(Xn-1) > (M-Z)^2 - M + Z = (M-Z-1)(M-
Z) >= 0
所以，必然存在只过两点的直线。

---------------------------------------------------------------------
把1~2n数字分成1~n(A1组)和n+1~2n(B1组)，可见B1组中的偶数由A1组中的n/2~n乘以2得到，同理A1组可递归划分成A2组和
B2组，具有相同性质。
现只需证明在(A1组+B1组偶数)构成的数集中，无法得到n/2+1个数字符合不存在相整除。
事实上递归地取Bj(j=1 to 无穷)中的奇数，构成的数列和为
lim(m->无穷) n/2+n/4+n/8+...n/m = n
n < n+1，所以不可能取n+1个数，又不存在相整除的情况。


证完这个以后发现，其实跟邓鋆的方法道理是一样的，他的理解比我的要舒服多了。
我感觉那个啥费马的问题比这个还要简单一些。

On 4月11日, 上午11时52分, pongba <pon...@gmail.com> wrote:
> 讨论的目的见这里 <http://blog.csdn.net/pongba/archive/2008/04/09/2270171.aspx>。
>
> 这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。
>
> 先提几道经典的：
> 1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul
> Erdos<http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fwww.cise....>
> 用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）
> 2.

> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。

> 3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
> 3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？
>
> （友情感谢silwile <http://www.douban.com/people/silwile/>提供题目^_^）
>
> P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
> 点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。
>
> P.S.

> 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意忘形:-)

[ZhangShen Peng(Uestc graduating...)]

2008/4/14 hyifeng <hyi...@gmail.com>:

>
> 点猜想问题：
> 设有M个点，那么任意两点连结成的直线有 (M, 2) = M(M-1)/2 条

错,任意两点连结成的直线有 (M, 2) = M(M-1)/2 条的前提是全不共线而非不全共线

--

[ZhangShen Peng(Uestc graduating...)]

2008/4/14 hyifeng <hyi...@gmail.com>:

错,A1组的元素个数可能是奇书个

> 现只需证明在(A1组+B1组偶数)构成的数集中，无法得到n/2+1个数字符合不存在相整除。
错,应该是(A1组+B1组奇数)

--

[hyifeng]

错,任意两点连结成的直线有 (M, 2) = M(M-1)/2 条的前提是全不共线而非不全共线

----------------------
不考虑重叠。




第二条题的证明难以表述，可能用图形说明会比较好，
我尝试说明一下，如果不能理解就作罢了。

1 2 3 4 5 6 7 8 9 10
观察上面的数列
把它平分，原则是前面数列的最大的数的2倍不大于后面的数列的最大数，如：
A1: 1 2 3 4 5
B1: 6 7 8 9 10
现在把B1分解成奇数和偶数两个集合(6 8 10) (7 9)

偶数和A1构成一个新集合命名为C：(1 2) (3 4 5) (6 8 10)
奇数部分命名为D：(7 9)

那么你要从数列中选取n+1个数，可以在C或D中选，
D的集合的数量为大略是n/2，视其奇偶性，会有波动，不过不会影响结果。

好了，下面是关键，
留意A1集合中(3 4 5)和(6 8 10)的关系，他们是等价的，
即是集合C 可简化成 (1 2) (3 4 5)，
而刚好，这可以递归地应用上面的分组策略，
A2: 1 2
B2: 3 4 5
并且B2元素的数量是n-D（这是很重要的），
重复
偶：(1) (2) (4)
奇：(3 5)

然后，回来考虑
C：(1 2) (3 4 5) (6 8 10)
D：(7 9)
假设，D可以全部加入到我们的结果集中，并且从C中选取剩余的部分构成n+1个数，接下来证明这是不可能的。
（这里隐含，如果D不能够全部加入到结果集中，则需要在C中选取更多的数，也是不可能的）
在C 中，要么你选择把(6 8 10)全部加入到结果集中，从而失败掉。
要么选择递归地进行上面的过程，直到达到(1 2)，最终失败。
你选取的数目只有趋向于n（或达到n），而达不到n+1


On 4月14日, 下午6时00分, "ZhangShen Peng(Uestc graduating...)"
<zsp...@gmail.com> wrote:
> 2008/4/14 hyifeng <hyif...@gmail.com>:

[hyifeng]

解析一下，上面的方法跟邓鋆的方法原理是一致的。

原因在于
------------------

留意A1集合中(3 4 5)和(6 8 10)的关系，他们是等价的，
即是集合C 可简化成 (1 2) (3 4 5)，

------------------------

导致例如取数不能同时取5和10，
而且这种递归的关系导致，不可能同时取 (2 4 8) 任意两个数。

这就变成了奇数分组了。

简单的事情就是这么变复杂的～唉

[ZhangShen Peng(Uestc graduating...)]

2008/4/14 hyifeng <hyi...@gmail.com>:

> 错,任意两点连结成的直线有 (M, 2) = M(M-1)/2 条的前提是全不共线而非不全共线
> ----------------------
> 不考虑重叠。
>
>
>
>
> 第二条题的证明难以表述，可能用图形说明会比较好，
> 我尝试说明一下，如果不能理解就作罢了。
>
> 1 2 3 4 5 6 7 8 9 10
> 观察上面的数列
> 把它平分，原则是前面数列的最大的数的2倍不大于后面的数列的最大数，如：
> A1: 1 2 3 4 5
> B1: 6 7 8 9 10
> 现在把B1分解成奇数和偶数两个集合(6 8 10) (7 9)
>
> 偶数和A1构成一个新集合命名为C：(1 2) (3 4 5) (6 8 10)
> 奇数部分命名为D：(7 9)
>
> 那么你要从数列中选取n+1个数，可以在C或D中选，
> D的集合的数量为大略是n/2，视其奇偶性，会有波动，不过不会影响结果。

不过不会影响结果
这一点不是很理解

lim(m->无穷) n/2+n/4+n/8+...n/m = n

可能变为

lim(m->无穷)
n/2
n/4+1
....
后面可能还有+1
也是极限不是你下面说的n了

[hyifeng]

-_-!
是我误导了你，你可以先别管那个级数和，那只是一个近似过程。

---------------------------------------------------

那么你要从数列中选取n+1个数，可以在C或D中选，
D的集合的数量为大略是n/2，视其奇偶性，会有波动，不过不会影响结果。

好了，下面是关键，
留意A1集合中(3 4 5)和(6 8 10)的关系，他们是等价的，
即是集合C 可简化成 (1 2) (3 4 5)，
而刚好，这可以递归地应用上面的分组策略，
A2: 1 2
B2: 3 4 5

并且B2元素的数量是n-D（这是很重要的）， <-------------------------关键在这里，每次收入到结果集中的数，总
量总是不会超过 n 的。
-------------------------------------------------------------

假设第一次收集了D个，那么下次收集的数字是在n-D中进行的，
第一次D=n/2+1，那么下次迭代就是从剩下的 n-(n/2+1) 中进行。

思想是很简单的，
不可能从集合(A + B的偶数) 中，找到 (n+1 - B的奇数个数) 个符合要求的数。


On 4月14日, 下午8时59分, "ZhangShen Peng(Uestc graduating...)"

[Poople]

我只想明白了第一题不知道是否正确：
例如1 2 3 4 5 6 7 8 9 10 我可以分解成5堆，分别是(1 2 4 8), (3 6), (5 10), (7), (9) 只
要个数大于2的任意堆取出超过两个数，那么这两个数肯定就有整除关系了。

现在我们要确定的就是对于1--2N的数据中，是不是都可以构造出少于等于N堆，构造方法就是每个堆的里面都是一个数列，
数列的算法就是((2*P+1) * 2^Q)的集合，其中P代表堆号是从0开始的，Q代表幂数也是从0开始的。

[hayate]

对 有sense

2008/4/15 Poople <poopl...@gmail.com>:

[Mr Shore]

高中竞赛树上一道填空题
不过暂时想不出来了

在08-4-16，hayate <haya...@gmail.com> 写道：

[Justin L]

将1000瓶酒按照顺序标上号：1～1000

囚犯A，每天喝200瓶酒，分成5天喝完。
喝法：（相当于把酒分成5大组（200瓶一组）每天喝一大组），此人第几天死就可以确认毒酒是在哪个大组。（精确到200瓶酒内）
第一天：1~200；第二天：201~400；第三天:401~600；第四天601~800，第五天:801~1000

囚犯B，每天喝200瓶酒，分成5天喝完。
喝法：(相当于把5大组，每个组分成5个小组，每天喝按顺序5个大组中的第n个小组)，此人第几天死就可以确认毒酒是在哪个小组。（精确到40瓶酒
内）
第一天：1~40, 201~241, 401~441, 601~641, 801~841
……………………………………
第n-1天:1+n*40~40+n*40, 201+n*40~241+n*40, 401+n*40~441+n*40,
601+n*40~641+n*40, 801+n*40~841+n*40

囚犯C，每天同样和200瓶酒，5天喝完。
喝法：在5个小组中又分出5个最小组（每组8瓶酒）每天喝所有小组中的第n个最小组。此人第几天死就可以确认毒酒是在哪个最小组中。（精确到8瓶酒
内）
剩下的7个囚犯，每天跟囚犯C同样的喝法。（最小组中有8瓶酒，7个人喝掉其中的7瓶，按顺序，例如7个人喝1-7号酒，而第8瓶酒留下来不喝）（这样
剩下七

个人的死法，可以确定8瓶酒内具体的有毒的情况）


例如：
囚犯A在第二天就死掉了（从总的5个星期中的第31天算起，算作第一天），则说明毒酒在第二个大组中——201～400号酒中
囚犯B在第三天死掉了，则说明毒酒在（第二个大组的）第三个小组中——283～323号酒中
囚犯C在第四天死掉了，则说明毒酒在（第二个大组，第三个小组的）第四个最小组中——346～357号酒中（如果我没数错的话）
再通过剩下7个囚犯的情况，可以知道上面8瓶酒中，几号酒有毒。

[Eric]

其实点猜想的初等方法很简单，我给大家一个提示吧：

考虑线外的点到线的距离。选一根线，使得线外的某个点到这条线的距离是所有点到直线距离最短的。想想假如这个线上至少有三个点能导出什么矛盾。

思路其实很简单，从极端情形入手。

On Apr 10, 10:52 pm, pongba <pon...@gmail.com> wrote:
> 讨论的目的见这里 <http://blog.csdn.net/pongba/archive/2008/04/09/2270171.aspx>。
>
> 这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。
>
> 先提几道经典的：
> 1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul
> Erdos<http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fwww.cise....>
> 用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）
> 2.
> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的 ）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
> 3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
> 3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？
>
> （友情感谢silwile <http://www.douban.com/people/silwile/>提供题目^_^）
>
> P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
> 点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。
>
> P.S.

> 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接 把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意 忘形:-)

[pongba]

2008/4/24 Eric <xu.ma...@gmail.com>:

其实点猜想的初等方法很简单，我给大家一个提示吧：

考虑线外的点到线的距离。选一根线，使得线外的某个点到这条线的距离是所有点到直线距离最短的。想想假如这个线上至少有三个点能导出什么矛盾。

思路其实很简单，从极端情形入手。

可这个"简单"的思路耗去了十五年时间啊..
我一直认为像这类题目，要想到这个方法除了试错之外并没有所谓的灵感。这就是为什么需要这么久才有人发现这个方法。

[Justin L]

1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。

如果一定要从鸽洞原理考虑：
1到2n这么一堆数，从鸽洞原理来考虑，那么必定是可以把这2n个数分成两组（一组代表鸽子，一组代表洞）。
鸽子和洞之间是整除关系。
那么欲采用鸽洞原理证明，则变成了证明，1-2n这些数，每个都可以和另外一个数有整除关系。

[Justin L]

“从(n+1)/2 到n”这一系列数分别和“从(n+1)到2n”有对应的整除关系。这些数加起来，应该有n个了吧。

如果剩下的n个数中，如果我能找到n/2个数和另外n/2个数是没有整除关系的，那么我就可以推翻题目的结论了。
剩下的数有哪些呢？
“1~(n+1)/2之间的所有数”和“(n+1)~2n之间的奇数”。
但是很显然，1可以和任何数有整除关系，2可以和任何偶数有整除关系。
所以剩下的n个数中我们不能找到n个数，他们之间没有整除关系。

因此，对于n+1个数，肯定可以找到有整除关系的。

[Justin L]

对于这个点猜想的题，看过只有有如下想法：
将点分为两类。一类是是共线（直线L1）的点，另一类是不共线的点（L1之外的A点和B点）。
考虑到L1上两点和A点三个点形成的三角形，如果B能在这个三角形的一个边上的话，他一定不能同时在另外两条边上（否则怎么形成三角形）。即：4个点的
情况得证。

那么现在考虑只能多画一个点：如果多出一个点C，那么这个点C如果不出现在现有三角形的边（所在的直线）上，那就会导致存在只过两个点的直线。因此考虑
把这个点画在现有三角形的边(所在的直线上)。
因此，新添加的这个点C画在三角形的某个边的延长线上（因为新增的点当然不能画在L1上），那可以以L1上两个点为和这个新的点为三个顶点，画一个三角
形，而两个三角形肯定不是同一个（因为C点不在原来定点位置上），因为其他的点在原先的三角形所在的边上，则这个三角形的一个边必定只过L1上那个点还
有B点（只过两个点）。
因此只能再添加一个点，要让他破坏现有的只过两个点的线，这样问题又回到了从4个点开始加点的情况，证明方法类似。

因此你只能不断的添加新的点，而我又能从你的新添加的点中找到合乎要求的点，因此点猜想得证。

我只是看题目，一时想到的。可能谈不上论证的地步。大家看看有没有问题。
我觉得这也是一个推理方法吧，就是不断的满足条件，但是又能找到新的突破口，最后得出，除非不断的更新假设，否则我总能找到满足条件的方法。

On 4月11日, 上午11时52分, pongba <pon...@gmail.com> wrote:
> 讨论的目的见这里 <http://blog.csdn.net/pongba/archive/2008/04/09/2270171.aspx>。

> P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
> 点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。
>

[部洪波]

关于第1题，我有一个想法，不知道正确否：
因为两个数存在整除关系，那么这两个数就存在一个倍数关系，最小的是1倍，接着是2倍，3倍等等。给出的数列是1到2n，所以1倍关系不存在，那么最小的是2倍关系。
现在构造一个n+1个数的数列，要求数列中不存两个数有倍数关系，很自然应该从2n开始向前拿。依次拿到2n-1, 2n-2, ...。当拿到n+1这个数的时候，已经取得了n-1个数，这n-1个数之间不可能有存在整除关系的数对。
剩下的2个数，从余下的1到n中拿，无论怎么拿，这两个数的2倍的数必然在已经拿到的n-1个数中。
由于不能构造出一个不存在倍数关系数对的n+1个数的数列，所以原题得证。

2008/4/11 pongba <pon...@gmail.com>:

讨论的目的见这里。

这个帖子就总结经典的归纳题吧，归纳题的特质还是蛮清晰的，一般里面有某种变量n的，就是一个提示，可以尝试用用归纳法。

先提几道经典的：

1. 1~2n这2n个自然数中任取n+1个数，证明必有两个数能够互相整除。（据silwile说，这道题被Paul Erdos用来测试学生是不是有数学"sense"，它有一个漂亮的证明和一个"规矩"的证明，能够想到前者的被认为有"sense"）

2. 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
3. 众数问题：n个数，求有没有这样一个数，它的出现次数>n/2。O(n)复杂性。
    3.1. 泛化：如果找出现次数>n/3呢？>n/4呢？

（友情感谢silwile提供题目^_^）

P.S. 前两天的讨论发现这里真是藏龙卧虎啊:-) 点猜想有人自己做出来过吗，如果有的话，请教完整思路，不要证明，要思路:-)
点猜想虽然是一道初等题，但十几年没有人证出来，后来被人用初等手法证出来了，《费马大定理》上有介绍：平面上n个点，不全共线，证明存在一条直线仅过两点。

P.S. 讨论的目的不是为了答案，而是为了思路，已经知道答案的，我想知道是怎样想到那关键的一步的，只有思路才是对所有问题都相通的，如果你有一个灵感，千万不要直接把灵感就扔出来，在灵感背后，肯定有着艰苦的思考过程，正如没有前7个饼，第八个饼本身是吃不饱的。阿基米德如果不是思考得很艰苦，也不至于想出来之后那么得意忘形:-) 所以，我觉得，所有有可能带领你发现灵感的一般性思路，都有卓越的价值。

[pongba]

2008/4/29 部洪波 <buho...@gmail.com>:

关于第1题，我有一个想法，不知道正确否：
因为两个数存在整除关系，那么这两个数就存在一个倍数关系，最小的是1倍，接着是2倍，3倍等等。给出的数列是1到2n，所以1倍关系不存在，那么最小的是2倍关系。
现在构造一个n+1个数的数列，要求数列中不存两个数有倍数关系，很自然应该从2n开始向前拿。依次拿到2n-1, 2n-2, ...。当拿到n+1这个数的时候，已经取得了n-1个数，这n-1个数之间不可能有存在整除关系的数对。
剩下的2个数，从余下的1到n中拿，无论怎么拿，这两个数的2倍的数必然在已经拿到的n-1个数中。
由于不能构造出一个不存在倍数关系数对的n+1个数的数列，所以原题得证。

你这个严格来说是一个特例，不是一个证明。你先前说"显然"应该从2n拿到n+1，这种非随意拿法为什么是"唯一"的可能性，没有证明。

[Eli]

第一题， 你们的想法似乎都太复杂了。 我的方法是， 将2n之内任取n+1个数， 找出有限个方法，这些方法构造的结果可以覆盖所有情况， 然后证明
这些方法构造出来的集合， 全都不能满足"在n+1这个集合内没有任何两个数存在整除关系"。 如果题设成立， 这显然是不可能的。

不过如何严谨的表达我还没有试， 谁想法跟我差不多， 可以试试， 我觉得似乎比较简单。



On May 1, 4:08 pm, pongba <pon...@gmail.com> wrote:
> 2008/4/29 部洪波 <buhon...@gmail.com>:

[pongba]

2008/5/3 Eli <Eli...@gmail.com>:

第一题， 你们的想法似乎都太复杂了。 我的方法是， 将2n之内任取n+1个数， 找出有限个方法，这些方法构造的结果可以覆盖所有情况， 然后证明
这些方法构造出来的集合， 全都不能满足"在n+1这个集合内没有任何两个数存在整除关系"。 如果题设成立， 这显然是不可能的。

关键是你怎么"找出"这"有限个方法"呢

[jerry]

第一题的证明如下：
从2n个数中取n+1个数
把2n个数分成两个集合，（1-n）（n-2n）
n+1个数必定在两个集合都有数，假设在（1-n）的元素个数为x，如果证明这x个元素中每一个元素都能在（n-2n）中找到一个倍数就能证明问题。因
为如果（2-2n）中都有x的倍数的话，那至少这些元素就不能被选择，那么总数都不够n+1个了。

下面证明这x个元素中每一个元素都能在（n-2n）中找到一个倍数。
首先考虑这些元素的2倍，如果2倍在（n-2n）中，则证明成功，排除之。如果不在，那这些元素一定在（1-n/2），在考虑元素的4倍，如此推理，则
每个元素必定能在（n-2n）中找到一个倍数。

证明完毕！

对于{9，99，999....}这题证明如下（利用同余的思想即可得到）：
选择n，那么对于10^0 -1, 10^1 -1,....,10^n -1,一定有n+1个数，那么一定存在同余的两个数。
假设为10^x -1和10^y -1（y>x），那么（10^y-1）- (10^x -1)一定能被n整除。
（10^y-1）- (10^x -1) = 10^y - 10^x = 10^x(10^(y -x) -1)
由于n不能被2和5整除，那么n一定能被10^(y-x) -1整除，命题得证！

[pongba]

2008/6/11 jerry <hbje...@gmail.com>:

第一题的证明如下：
从2n个数中取n+1个数
把2n个数分成两个集合，（1-n）（n-2n）
n+1个数必定在两个集合都有数，假设在（1-n）的元素个数为x，如果证明这x个元素中每一个元素都能在（n-2n）中找到一个倍数就能证明问题。因
为如果（2-2n）中都有x的倍数的话，那至少这些元素就不能被选择，那么总数都不够n+1个了。

下面证明这x个元素中每一个元素都能在（n-2n）中找到一个倍数。
首先考虑这些元素的2倍，如果2倍在（n-2n）中，则证明成功，排除之。如果不在，那这些元素一定在（1-n/2），在考虑元素的4倍，如此推理，则
每个元素必定能在（n-2n）中找到一个倍数。

证明完毕！

对于{9，99，999....}这题证明如下（利用同余的思想即可得到）：
选择n，那么对于10^0 -1, 10^1 -1,....,10^n -1,一定有n+1个数，那么一定存在同余的两个数。
假设为10^x -1和10^y -1（y>x），那么（10^y-1）- (10^x -1)一定能被n整除。
（10^y-1）- (10^x -1) = 10^y - 10^x = 10^x(10^(y -x) -1)
由于n不能被2和5整除，那么n一定能被10^(y-x) -1整除，命题得证！

这个证明很漂亮！:D

[hayate]

嗯 这回我可以确定了

欧拉定理的证明就是这个思路

2008/6/11 pongba <pon...@gmail.com>:

[liuxinyu]

我想个思路，不一定正确，请指正：
根据筛法分成如下组
{1,2,3,...,2n}
{2,4,6,...,2n}
{3,6,9,...}
...
{p, 2p, 3p,...}

其中p是<2n的最大素数。
由于p<=sqrt(2n) (这个证明就不细说了，google即可)
当n>2的时候，sqrt(2n)<=n (2n<=n^2 where n<=2)
所以上述组数一定不大于n，根据抽屉原则，必有2个整数落入同一组。故而能互相整除。

当n<=2时的特例可以分成以下两组{1,3}, {2,4}。任取3个数必然有2数落入其中一组，也可互相整除。

[alai]

p<=sqrt(2n)是不成立的。

2008/6/12 liuxinyu <liuxi...@gmail.com>:

[obtuseSword]

liuxinyu的证明中的问题主要不在于分成多少组，而在于落在同一组的两个数不一定存在整除-被整除关系。但这个思路可以启发我们构造这样的分组：
同一组中的数皆存在整除-被整除的关系。

看看这样的分组能尽可能少到多少呢？要是能少到n，就可以利用鸽巢原理了。 为了构造尽可能少的分组，直觉上，我们应该在各组中容纳尽可能多的数，不妨
先对具体例子作些尝试。

比如 n = 10，分组如下：
[组1] 1, 2, 4, 8, 16
[组2] 3, 6, 12
[组3] 5, 10, 20
[组4] 7, 14
[组5] 9, 18
[组6] 11
[组7] 13
[组8] 15
[组9] 17
[组10] 19

发现10组就够了，而且所有组中的元素是存在整除-被整除关系的。

那么这个分组是怎样形成的呢？首先把1分到某组，然后把它能整除的最小元素，即2，分到同一组，再把2的最小倍数4分到同一组…… 这样的目的是使该组
元素尽可能多。当该分组无法容纳更多的元素时，开始新的分组。最终将所有元素分到某组中。

接下来，我们自然要去看看对于一般的n，按这种原则得到的分组数是多少。 稍作思考，容易发现，所有奇数作为各组中的最小元，而所有偶数按照不断除去素
因数2后得到的奇数分到对应的组。比如12，不断除去素因数2后得到3，故与3同组；比如20，不断除去素因数2后得到5，故与5同组。 也就是说，第
k组的元素必有形式 (2k-1) * 2^p，这样的组数显然就是1到2n中的奇数的个数，即n。 根据这个分组，接下来就容易用鸽巢原理证明原命题
了。


现在我们回顾一下我们到达问题的解答的路径：
[1] 出于应用鸽巢原理的直觉和动机，尝试构造分组 —〉
[2] 考虑鸽巢原理的使用方式（如果落在同一组，他们存在整除-被整除关系），尝试构造尽可能少的分组 —〉
[3] 考虑到分组尽可能少，根据直觉，各组应尽可能大 —〉
[4] 有原则地尝试而得到一种具体分组方案，推广到一般情形。如果可行，停止尝试；否则继续尝试 —〉
[5] 整理思路，给出形式化的证明。 —〉END

从这条路径看出，直觉（数学的——比如应用鸽巢原理；非数学的——比如各组尽可能大）起到了很大的作用，它是思维链上此结点到下一结点的路标。这或许就
是Erdos说的"sense"吧。

数学感还有一种形式是将数学各分支的结论融会起来，对于这一题，按说是“数论”的内容，但是如果知道组合数学“极端集合论”中的Dilworth定理，
知道“偏序”、“链”、“反链”的意义，或许可能马上引导你给出如上的论证。因为，我们可以定义a|b为一个序关系，那么1到2n这些数构成的集合为一
偏序集，这一题就是要你证明，该偏序集的所有反链，其长度不超过n。 根据Dilworth定理，“最长反链长度<=偏序集划分成的链的条数”， 所以
只要证明链的条数可以少到n或更少，就解决该问题了。 而链就是我们上面说的“分组”，所以立刻引导我们把注意力集中在研究分组方式上了，可以少走很多
弯路。

最后，我们还要反思一下我们所证明的命题，比如，为什么一定是取n+1个数呢？取少一点就可能不满足了吗？答案很明白，如果取 n+1,n
+2,...,2n 这n个数，就不存在某个整除某个了，这说明原命题中的n+1已经足够精确了，同时也说明我们定义的偏序集，不可能分成少于n条链，
也就是说，我们在上面的证明中给出的简简单单的分组方式，得到的分组数竟然是最少的，尽管还有很多种不同的分组方式。 显然，这样的反思是很有益的，
既能加深对命题的理解，又可能得到其它的结果。



On 6月12日, 下午5时41分, alai <ala...@gmail.com> wrote:
> p<=sqrt(2n)是不成立的。
>
> 2008/6/12 liuxinyu <liuxiny...@gmail.com>:

>
>
>
> > 我想个思路，不一定正确，请指正：
> > 根据筛法分成如下组
> > {1,2,3,...,2n}
> > {2,4,6,...,2n}
> > {3,6,9,...}
> > ...
> > {p, 2p, 3p,...}
>
> > 其中p是<2n的最大素数。
> > 由于p<=sqrt(2n) (这个证明就不细说了，google即可)
> > 当n>2的时候，sqrt(2n)<=n (2n<=n^2 where n<=2)
> > 所以上述组数一定不大于n，根据抽屉原则，必有2个整数落入同一组。故而能互相整除。
>

> > 当n<=2时的特例可以分成以下两组{1,3}, {2,4}。任取3个数必然有2数落入其中一组，也可互相整除。- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[pongba]

2008/6/13 obtuseSword <obtus...@gmail.com>:

liuxinyu的证明中的问题主要不在于分成多少组，而在于落在同一组的两个数不一定存在整除-被整除关系。但这个思路可以启发我们构造这样的分组：
同一组中的数皆存在整除-被整除的关系。

看看这样的分组能尽可能少到多少呢？要是能少到n，就可以利用鸽巢原理了。 为了构造尽可能少的分组，直觉上，我们应该在各组中容纳尽可能多的数，不妨
先对具体例子作些尝试。

比如 n = 10，分组如下：
[组1]   1, 2, 4, 8, 16
[组2]   3, 6, 12
[组3]   5, 10, 20
[组4]   7, 14
[组5]   9, 18
[组6]   11
[组7]   13
[组8]   15
[组9]   17
[组10] 19

发现10组就够了，而且所有组中的元素是存在整除-被整除关系的。

那么这个分组是怎样形成的呢？首先把1分到某组，然后把它能整除的最小元素，即2，分到同一组，再把2的最小倍数4分到同一组...... 这样的目的是使该组

元素尽可能多。当该分组无法容纳更多的元素时，开始新的分组。最终将所有元素分到某组中。

接下来，我们自然要去看看对于一般的n，按这种原则得到的分组数是多少。 稍作思考，容易发现，所有奇数作为各组中的最小元，而所有偶数按照不断除去素
因数2后得到的奇数分到对应的组。比如12，不断除去素因数2后得到3，故与3同组；比如20，不断除去素因数2后得到5，故与5同组。 也就是说，第
k组的元素必有形式 (2k-1) * 2^p，这样的组数显然就是1到2n中的奇数的个数，即n。 根据这个分组，接下来就容易用鸽巢原理证明原命题
了。


现在我们回顾一下我们到达问题的解答的路径：

[1] 出于应用鸽巢原理的直觉和动机，尝试构造分组 --〉
[2] 考虑鸽巢原理的使用方式（如果落在同一组，他们存在整除-被整除关系），尝试构造尽可能少的分组 --〉
[3] 考虑到分组尽可能少，根据直觉，各组应尽可能大 --〉
[4] 有原则地尝试而得到一种具体分组方案，推广到一般情形。如果可行，停止尝试；否则继续尝试 --〉
[5] 整理思路，给出形式化的证明。 --〉END

从这条路径看出，直觉（数学的----比如应用鸽巢原理；非数学的----比如各组尽可能大）起到了很大的作用，它是思维链上此结点到下一结点的路标。这或许就
是Erdos说的"sense"吧。

非常到位！其实这也正是我后来总结的最接近可行的方法——先尝试构造分组，然后观察分组的性质。人的思维有一个特点，善于对具体的事物进行抽象，然而如果直接从抽象性质入手则更困难。比如这道题目，如果仅仅知道约束：分为N组，使得每组里面的元素都两两相除，求分组的方案。这时候思维根本无法下手。一方面这其实也是因为这个约束并非是分组方案的充分条件——在约束之下并不必然只存在唯一的分组方案。而思考充分条件是困难的。但归纳却是相对容易的——如果我们知道这个方案的一个特例，从特例中去归纳其性质就相对容易多了。

对于"直觉"一说，我的看法是这里不存在"人们所认为的"直觉，所有的直觉都只不过是神经网络的模糊计算，虽然这个计算的复杂度也许是NP难的（能够解释为什么对于复杂的问题直觉就走不远了），但这并不改变直觉的本质——计算。譬如这里的两个可能是直觉的地方：应用鸽笼原理——简单的联想（从"n+1个里面必然有2个__"的模糊匹配），分组尽可能少=>各组尽可能大则更只是简单的逻辑推导。