|
|
問題
1対1で、勝ち負けが決まる試合をします。
8人でトーナメントをすると、だれか1人が必ず1位になり、その人は3連勝しています。
つまり、8人いれば3連勝している人を100%の確率で、有限時間の間に作り出すことができます。
では、100連勝している人を100%の確率で、有限時間の間に生み出すためには、
最低でも何人必要でしょうか。ただし、トーナメント形式をとる必要はありません。
答え
(n+1)人の試合
アルゴリズム
(1) 誰か1人を仲間外れにしておく。
(2) 残りn人は全員看板（数字は「勝ち数」を意味する）を持ち、0と記入しておく。
(3) 以下のルールでひたすら試合を繰り返す。
(a) 同じ数字を掲げた人と出会ったら試合をする。
(b) 勝った人は看板の数字に1を足す。
(c) 負けた人は看板の数字を0に戻す。
(4) やがて、看板の数字が0から(n-1)までのものが1つずつになる。
(5) 仲間外れにしていた1人が看板を持ち、0と記入する。
(6) 以下のルールでひたすら試合を繰り返す。
(a) 同じ数字を掲げた人と出会ったら試合をする。
(b) 勝った人は看板の数字に1を足す。
(c) 負けた人は看板を捨てる。
(7) 最後の試合に勝った人がn連勝となる。
（終り）
●(3),(4)について
k人が 2^(k-1)-1 試合を行って、ひとりが (k-1)連勝となる。 残りは、0連勝となる。
証明
k=2のとき、
ABc
0:00
1:01
のような、1試合を行う。
k=3のとき、
ABCd
0:000
1:010
2:011
3:002
のような、3試合を行う。
k=4のとき、
ABCDe
0:0000
1:0100
2:0110
3:0020
4:0120
5:0121
6:0022
7:0003
のような、7試合を行う。
k=m≧2のとき、
m人が 2^(m-1)-1 試合を行って、ひとりが (m-1)連勝となる。 残りは、0連勝となる。
┌─── m 人 ───┐
0,0,0, …, 0,0,(m-1)
と仮定する。
k=m+1のとき、
┌─── (m+1) 人 ───┐
0,0,0, …, 0,0,0, 0
まず、最初のm人に対して、2^(m-1)-1 試合を行って、
┌─── (m+1) 人 ───┐
0,0,0, …, 0,0,(m-1), 0
次に、0連勝のm人（ (m-1)連勝の1人を除いたもの）に対して、2^(m-1)-1 試合を行って、
┌─── (m+1) 人 ───┐
0,0,0, …, 0,0,(m-1), (m-1)
とできる。
(m-1)連勝どうしで、もう1試合して、
┌─── (m+1) 人 ───┐
0,0,0, …, 0,0,0, m
よって、
(2^(m-1)-1)+(2^(m-1)-1)+1=2^m-1 試合を行って、ひとりが m連勝となる。 残りは、0連勝となる。
（終り）
これより、
┌──── n 人 ────┐
A B C D E F
k=n のとき、0,0,0, …, 0, 0, (n-1)
┌── (n-1) 人 ──┐
k=n-1のとき、0,0,0, …, 0, (n-2),(n-1)
┌─ (n-2) 人 ─┐
k=n-2のとき、0,0,0, …, (n-3),(n-2),(n-1)
:
:
┌3人┐
k=3 のとき、0,0,2, …, (n-3),(n-2),(n-1)
┌2┐
k=2 のとき、0,1,2, …, (n-3),(n-2),(n-1)
よって、Σ[k=1,n]{ 2^(k-1)-1 } = 2^n-1-n 試合
●(6)について
┌┴┐
┌┴┐F Fは(n-1)勝
┌┴┐E Eは(n-2)勝
┌┴┐D Dは(n-3)勝
：
┌┴┐
┌┴┐C Cは2勝
┌┴┐B Bは1勝
g A Aは0勝
の n 試合
●(7)について
全体で、(2^n-1-n) + n = 2^n-1 試合
具体的に見てみると、
・n=1の場合
(3),(4)について、
Ab
0:0
のような、0試合
(6)について、
┌┴┐
b A
の1試合
よって、0+1=1試合
・n=2の場合
(3),(4)について、
ABc
0:00
1:01 A-Bより（右側が「勝つ」とした）
のような、1試合
(6)について、
┌┴┐
┌┴┐B Bは1勝
c A Aは0勝
の2試合
よって、1+2=3試合
・n=3の場合
(3),(4)について、
ABCd
0:000
1:010 A-Bより（右側が「勝つ」とした）
2:011 A-Cより
3:002 B-Cより
4:012 A-Bより
のような、4試合
(6)について、
┌┴┐
┌┴┐C Cは2勝
┌┴┐B Bは1勝
d A Aは0勝
の3試合
よって、4+3=7試合
・n=4の場合
(3),(4)について、
ABCDe
0:0000
1:0100
2:0110
3:0111
4:0021
5:0121
6:0022
7:0003
8:0103
9:0113
10:0023
11:0123
のような、11試合
(6)について、
┌┴┐
┌┴┐D Dは3勝
┌┴┐C Cは2勝
┌┴┐B Bは1勝
e A Aは0勝
の4試合
よって、11+4=15試合
!(3),(4)について
LET N=7 !n連勝
DIM P(N) !n人の看板
MAT P=ZER
LET C=0 !試合の回数
LET K=N !※右側yが「勝つ」として、Pの並びは0,1,2,3,…,(n-1)
DO
FOR X=1 TO K-1 !xとyとの試合
FOR Y=X+1 TO K
IF P(Y)=P(X) THEN
LET P(Y)=P(Y)+1 !試合の結果を反映させる
LET P(X)=0
LET C=C+1
PRINT C !結果を表示する
MAT PRINT P;
END IF
NEXT Y
NEXT X
IF P(K)=K-1 THEN
PRINT K-1;"連勝をつくりました。"
PRINT
LET K=K-1
IF K=1 THEN
LET S=0 !Σ
FOR i=1 TO N
LET S=S +2^(i-1)-1
NEXT i
PRINT S
PRINT 2^N-1 -N !必要な試合の回数
STOP
END IF
END IF
LOOP
END
実行結果
1
0 1 0 0 0 0
2
0 1 1 0 0 0
3
0 1 1 1 0 0
4
0 1 1 1 1 0
5
0 1 1 1 1 1
6
0 0 2 1 1 1
7
0 0 2 0 2 1
8
0 1 2 0 2 1
9
0 1 2 1 2 1
10
0 0 2 2 2 1
11
0 0 0 3 2 1
12
0 1 0 3 2 1
13
0 1 1 3 2 1
14
0 0 2 3 2 1
15
0 0 0 3 3 1
16
0 0 0 0 4 1
17
0 1 0 0 4 1
18
0 1 1 0 4 1
19
0 1 1 1 4 1
20
0 0 2 1 4 1
21
0 0 2 0 4 2
22
0 1 2 0 4 2
23
0 1 2 1 4 2
24
0 0 2 2 4 2
25
0 0 0 3 4 2
26
0 1 0 3 4 2
27
0 1 1 3 4 2
28
0 0 2 3 4 2
29
0 0 0 3 4 3
30
0 0 0 0 4 4
31
0 0 0 0 0 5
5 連勝をつくりました。
32
0 1 0 0 0 5
33
0 1 1 0 0 5
34
0 1 1 1 0 5
35
0 1 1 1 1 5
36
0 0 2 1 1 5
37
0 0 2 0 2 5
38
0 1 2 0 2 5
39
0 1 2 1 2 5
40
0 0 2 2 2 5
41
0 0 0 3 2 5
42
0 1 0 3 2 5
43
0 1 1 3 2 5
44
0 0 2 3 2 5
45
0 0 0 3 3 5
46
0 0 0 0 4 5
4 連勝をつくりました。
47
0 1 0 0 4 5
48
0 1 1 0 4 5
49
0 1 1 1 4 5
50
0 0 2 1 4 5
51
0 1 2 1 4 5
52
0 0 2 2 4 5
53
0 0 0 3 4 5
3 連勝をつくりました。
54
0 1 0 3 4 5
55
0 1 1 3 4 5
56
0 0 2 3 4 5
2 連勝をつくりました。
57
0 1 2 3 4 5
1 連勝をつくりました。
57
57
|
|