Re: [鴿籠] 年齡
※ 引述《wsx02 ()》之銘言：
: In a room where there are more than 50 people with ages between 1 and 100
: (B) either two people have the same age or one person's age is a multiple of
: another's
: 請問這句是對的嗎?
: 有辦法證明嗎?
: 謝謝
不妨設房內有51人及任兩人年齡不同
所以要證明的就是其中必有一人年齡為另一人的倍數
設年齡分別為a_1, a_2, ... ,a_51
考慮這樣的集合A_n = { n_1, n_2, ... ,n_m }
其中n_1 = n 且 n_(k+1) = n_k / {n_k的最小質因數}
n_m = 1
所以我們有 n_x | n_y 對所有的 1 <= x <= y <= m
注意到A_1~A_50這50個集合分別包含於某個A_n (51 <= n <= 100)
這是因為我們知道 A_i 包含於 A_2i 包含於 A_4i ....
所以對每一個1 <= k <= 50 存在一個t
使得 51 <= 2^t * k <= 100
所以我們很容易知道 A51~A100 包含所有的1~100
故若所有a_i都在A_51~A_100這50個集合中
必有兩個在同一集合中, 其中一個為另一個的倍數
--
^^
('') ~我是可愛的兔子
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.28.199
推
05/05 23:57, , 1F
05/05 23:57, 1F
→
05/06 08:23, , 2F
05/06 08:23, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
鴿籠
1
2