選數字問題

[armopen]

從自然數列 a_1, a_2, a_3, a_4, ... , a_100 中選取 k 個，則

(1) 若 k 個中任兩個均不相鄰，則 k 最多是多少？

(2) 若 k 個中恰兩個相鄰，其他任兩個均不相鄰的機率為何？

麻煩 thepiano 老師解惑, 謝謝您的幫忙.

[thepiano]

http://forum.nta.org.tw/examservice/sho ... hp?t=39717

第 2 小題
小弟覺得不太可能用紙筆算出來

[armopen]

我打一下書上的解法，

(1) C(100-k+1,k), 其中 101 - k ≧ k, 所以 k 最大只能是 50.

(2) C(101-k,k-1) * (k-1) / C(100,k) <=== 分子又是怎麼想的呢？


另外，我覺得奇怪為何第 (1) 小題的答案是從 100 - k + 1 去選 k 個，

而不是從 100 - k 去選 k 個呢？ 那個多加的 1 是怎麼來的呢？ 謝謝 thepiano 老師的幫忙.

[eggsu]

第(1)小題：
若選出 k 個元素，則至少要用 k-1 個元素去隔開
故 k + (k-1) ≦ 100，推得 k≦50.5
即得 max k = 50

第(2)小題：
有 k 個元素，其中有兩個要相鄰，
將之視為 x_1 、x_2、……、x_(k-1) ，共 k-1 組，其中有一組是 2 個元素

則 x_1 的左方有 y_0 個元素
　x_1和x_2之間有 y_1 個元素
　x_2和x_3之間有y_2個元素
　…
　x_(k-2)和x_(k-1)之間有y_(k-2)個元素
　x_(k-1) 的右方有 y_k-1 個元素
故 y_0 + y_1 + y_2 + ... + y_(k-2) + y_(k-1) = 100 - k　
且 y_1～y_(k-2)為正整數，y_0 及 y_(k-1) 為非負整數

得 z_0 + (z_1 + 1) + (z_2 + 1) + ... + (z_(k-2) + 1) + y_(k-1) = 100 - k
其中 y_i = z_i + 1，1≦i≦k-2 且 y_0 = z_0、y_(k-1) = z_(k-1)
轉化成 z_0 + z_1 + z_2 + ... + z_(k-1) = 102 - 2k
共有 H(k,102-2k) = C(101-k,102-2k)=C(101-k,k-1) 種可能

故答 (k-1)*C(101-k,k-1) / C(100,k)