lineva2002的部落格

鴿籠原理Pigeon hole principle

    設有N個鴿籠，但有N+1隻鴿子，要住進去，則一定有個籠內有2隻鴿子。

題目：從1、2、3………. 、2N個數中，任取N+1個數，則一定2個數互質。 

把問題特殊化

令N=5

1、2、3、4、5、6、7、8、9、10

若選5個偶數，1個奇數，相鄰的兩數一定互質

(1、2、3、4、5、6)，(1、2、3、4、5、7) ，(1、2、3、4、5、7)，(1、2、3、4、5、8)，(1、2、3、4、5、9)，……….

10!/6!4!=210    共有210種要列出來太累了。

N= 4     8!/5!3!=56   共有56種，也太多。

N=3      6!/4!2!=15   共有15種。如下：

舉例從1、2、3、4、5、6中，任取4個數，則一定2個數互質。

(1、2、3、4)，(1、2、3、5)，(1、2、3、6)，(1、2、4、5)，(1、2、4、6)，(1、2、5、6)，(1、3、4、5)，(1、3、4、6)，(1、3、5、6)，(1、4、5、6)，(2、3、4、5)，(2、3、4、6)，(2、3、5、6)，(2、4、5、6)，(3、4、5、6)。

Lexico-graphic排列順序由小而大。

N+1隻鴿子要放進N個籠子，有一個籠子一定會有二隻個鴿子。

相鄰兩自然數一定互質

設N和N+1兩數有公因數P(P≠1)

則   N=P‧Q1………..1

  N+1= P‧Q2………2

2-1得1=P(Q2-Q1)

上面的列式乘(Q2-Q1)得P=1‧(Q2-Q1)

但P≠1，故N,N+1沒有公因數。