✔ 最佳答案
這是獎門人的"開口中" 吧?
我們要找 P(n,k) 的 recurrence relation.
假設 k=1, 則明顯地 P(n,1) = 1/n, 這是 initial condition.
現在假設 k > 1
我們猜數字可以想成這樣:
1) 先猜一個數字 i ( Prob = 1/n)
2) 答案一定是小於 i (Prob = (i-1)/n ) 或大於 i (Prob = (n-i)/n) (因為 k>1)
3) 如果答案小於 i, 即現在想在這i-1 個數字猜 k-1 次猜中 (P(i-1, k-1))
同樣, 如果答案大於 i, 即現在想在這n-i 個數字猜 k-1 次猜中 (P(n-i, k-1))
於是, recurrence relation 就是:
P(n,k)
= Σ(i=1 to n) (1/n) * [(i-1)/n * P(i-1,k-1) + (n-i)/n * P(n-i, k-1)]
= (1/n^2) * Σ(i=1 to n) [(i-1)P(i-1,k-1) + (n-i)P(n-i, k-1)]
留意, 當 i = 1 時, (i-1)P(i-1,k-1) = 0
接著, by change of variable:
Σ(i=1 to n) [(n-i) * P(n-i, k-1)]
= Σ(i=1 to n-1 ) (i * P(i, k-1) )
同樣,
Σ(i=1 to n) [(i-1)P(i-1,k-1)]
= Σ(i=1 to n-1 ) (i * P(i, k-1) )
所以其實兩個 term 係double 左, 可以化簡成:
P(n,k) = 2/n^2 Σ(i=1 to n-1 ) (i * P(i, k-1) )
(由於(*)當 i<k-1, P(i,k-1) = 0, 所以可以再寫成:
P(n,k) = 2/n^2 Σ(i=k-1 to n-1 ) (i * P(i, k-1) ) )
例:
P(3,k) = 3/9, 4/9, 2/9
P(4,k) = 6/24, 9/24, 7/24, 2/24
亦可計算 P(n,2):
P(n,2) = 2/n^2 Σ(i=1 to n-1) (i*P(i, 1))
= 2/n^2 Σ(i=1 to n-1) i/i
=2/n^2 * (n-1)
但當計算 P(n,3) 時:
P(n,3) = 2/n^2 Σ(i=1 to n-1) i*P(i,2)
= 2/n^2 Σ(i=1 to n-1) i* 2/i^2 (i-1)
=2/n^2 Σ(i=1 to n-1) 2(i-1)/i
=4/n^2 [n-1 - H]
H = 1 + 1/2 + 1/3 + 1/4 +... 1/n-1
是 Harmonic Sum
所以 P(n,3) 已經要寫成 Harmonic Sum, 就不是奢望 k > 3 的時候有closed form solution 了.
(*)至於當k>n 時 P(n,k) =0 也很容易看出來:
P(1,2) =0, 因為右手面冇野
之後 by induction, P(n,k) = 0, 因為右手面每個 term 都是0
用Dynamics Programming, 先由 k=1 開始算起, 再逐層往上推, 很容易得出:
k: P(100,k)
1:1/100
2:198/10000
3:0.03753
4:0.06499
5:0.0991
6:0.1306
7:0.1481
8:0.145
9:0.1234
10:0.09201
11:0.06056
12:0.03545
13:0.01858
14:0.008773
15:0.003753
16:0.001461
17:0.0005202
18:0.00017
19:5.117e-005
20:1.424e-005
21:3.671e-006
22:8.796e-007
23:1.964e-007
24:4.093e-008
25:7.98e-009
26:1.458e-009
27:2.502e-010
28:4.036e-011
29:6.132e-012
30:8.783e-013
31:1.188e-013
32:1.518e-014
33:1.836e-015
34:2.103e-016
35:2.283e-017
36:2.352e-018
37:2.3e-019
38:2.137e-020
39:1.888e-021
40:1.586e-022
41:1.269e-023
42:9.662e-025
43:7.011e-026
44:4.848e-027
45:3.197e-028
46:2.011e-029
47:1.206e-030
48:6.907e-032
49:3.774e-033
50:1.969e-034
爆字數了...
亦可計出 Expected Guess = 7.47485
2009-04-30 05:39:31 補充：
60:2.323e-048
61:7.285e-050
62:2.179e-051
63:6.218e-053
64:1.691e-054
65:4.385e-056
66:1.083e-057
67:2.545e-059
68:5.692e-061
69:1.211e-062
70:2.447e-064
2009-04-30 05:39:53 補充：
51:9.809e-036
52:4.666e-037
53:2.119e-038
54:9.193e-040
55:3.809e-041
56:1.507e-042
57:5.692e-044
58:2.053e-045
59:7.068e-047
60:2.323e-048
2009-04-30 05:40:05 補充：
71:4.695e-066
72:8.548e-068
73:1.475e-069
74:2.41e-071
75:3.723e-073
76:5.435e-075
77:7.483e-077
78:9.704e-079
79:1.183e-080
80:1.354e-082
81:1.452e-084
82:1.454e-086
83:1.358e-088
84:1.178e-090
85:9.473e-093
86:7.028e-095
87:4.792e-097
88:2.987e-099
89:1.693e-101
90:8.667e-104
2009-04-30 05:40:15 補充：
91:3.973e-106
92:1.616e-108
93:5.755e-111
94:1.768e-113
95:4.591e-116
96:9.795e-119
97:1.649e-121
98:2.053e-124
99:1.681e-127
100:6.792e-131
101: 0
