Maths--Pigeonhole Principle

這種口氣.... 嗯，雖然我不是甚麼高手，但也和你「玩玩」吧！
順帶一提，第五題的意思是，有 4x4的大正方形，每個小正方形vertex 上放上一個color，即color的矩陣應是5x5, 而題目的proposition 是: 這 5x5裡面，有至少一個「四個頂點同色的rectangle」。
至於第四題，的確如你所言，畫graph的話，會是K8。

2009-02-08 16:16:58 補充：
我淨係答左 1, 3, 同埋 1 無用到 pigeonhole....

1.
Q: Prove that if 51 numbers are chosen from 1, 2, 3, 4, ... , 99 and 100, then there are 8 of them such that their greatest common divisor is great than 1.
A: Note that within 1,2,3,...,100, 50 of them are even numbers.
If more than or equal to 8 out of 51 numbers we chose are even, then they must have common divisor of 2.
If less than 8 numbers are even, that is, more than or equal to 51-8=42 numbers are odd.
Note that within the 50 odd numbers 1,3,5,...,99 , 33 of them are multiples of 3, in others words, 50-33=17 of these odd numbers are not multiple of 3.
Now, we are going to choose 42 remaining numbers from these 50 odd numbers, therefore, at most 17 of them are not multiple of 3, in other words, at least 42-17=25 of them have common multiple of 3.

3.
Q: Find the min. number of positive integers to be written to ensure that there are 2 numbers such that their sum or their difference is a multiple of 2008.
A: Let each number written be x(i), where i = 1,2,3,....
write x(i) = 2008*k(i) + a(i), where k(i) and a(i) are constant integers, with k(i)>=0, 0<=a(i)<=2007
For x = 2008*k + a, if x + y is multiple of 2008, then y = 2008h + (2008-a); if x - y is multiple of 2008, then y = 2008h + a.
> : Our proposition is the required minimum number is 1006.
Note that in our above analysis, each a has its "conjuate", e.g. 1~2007, 2~2006, ... , up to 1003~1005, we count each of these pair as one pigeon hole, and there are two special cases : 0~0 and 1004~1004, Thus, there are totally 1005 pigeon holes for 2008, by Pigeonhold Principle, at least 2 pigeons will be in same hole if there are 1006 pigeons.

2009-02-14 21:02:33 補充：
sorry that i got it wrong in Q. 1,
within 1,3,5,...,99, there should be 17 multiples of 3,
and thus 33 of them are not.
As we have to choose 42 numbers out of the 50 odd numbers, at least 42-33=9 numbers are multiples of 3.

2009-02-14 21:06:31 補充：
唔..原來第二題是這樣解的~
至於第五題，想問一下，為什麼「by pigeonhole principle，有三點是同色的」
是否應在第一行 分 case 為 全紅, 1黑4紅, 2黑3紅, 3黑2紅, 4黑1紅 及 全黑 呢?

我代石神哲哉和maximal_ideal_space答q2啦

2009-02-11 00:03:02 補充：
Solution: Let a1 = 7, a2 = 77, a3 = 777, a4 = 7777 and so on. Consider the n+1 numbers
a1, a2, · · · an,an+1 all reduced modulo n.

2009-02-11 00:03:07 補充：
Some 2 of these must be equal in Zn, say ak = al ∈ Zn with k < l. Then al − ak = 0 ∈ Zn so al − ak is a multiple of n, and notice that al − ak is
of the form 77 · · · 700 · · · 0.

4,5 兩題的題目似乎有點問題。第4題如果每兩隊之間要打剛好1場，則每隊打的場數都是7，根本不用Pigeonhole Principle。第5題可以找到反例。

RRBB
BBRR
RBRB
BRBR

2009-02-07 11:58:26 補充：
1至3題不是太難，先讓各位高手玩玩吧！

2009-02-10 16:30:25 補充：
一時戲言，不要太介意啦。
第二題嘛，嘗試考慮 7, 77, 777, 7777, ....，take mod n.
至於第五題，先看第一行，by pigeonhole principle，有三點是同色的，假設是黑色。考慮其餘四行的這三個位置，如果其中一行的三個位置中有兩點是黑色，則有一個黑色長方形。否則每行至少有兩點紅色，由於只有三個位置，3C2=3<4，所以必有兩行的兩點紅色在相同位置上，所以有一個紅色長方形。
另外你第一題的答案其實已用了pigeonhole principle，只不過不是很明顯吧。