玄関＞雑学の部屋＞クイズコーナー＞算数クイズ−解答編1

【算数クイズ−解答編2】

(第1問)　カードの数字の合計

トランプのように1から13までの数字が書かれた13枚のカードがあり、この13枚のカードから0枚以上のカードを取った時、その数字の合計が10になるカードの組み合わせはいくつあるでしょうか？ また合計が10になる確率はいくつでしょうか？

さらにこれを一般化して、1からnまでの数字が書かれたn枚のカードがあり、このn枚のカードから0枚以上のカードを取った時、その合計がTになるカードの組み合わせはいくつあるでしょうか？ また合計がTになる確率はいくつでしょうか？ (→第2問へ)

○解答

カードの枚数が1、2、3、…、(n-1)、nの時を考えると、カードの組み合わせとその合計Tは次のようになります。

1枚の時…(カード無)：T=0　カード[1]：T=1
2枚の時…(カード無)：T=0　[1]：T=1　[2]：T=2　[1]+[2]：T=3
3枚の時…(カード無)：T=0　[1]：T=1　[2]：T=2　[1]+[2]：T=3　[3]：T=3　[1]+[3]：T=4　[2]+[3]：T=5　[1]+[2]+[3]：T=6
：
(n-1)枚の時…(カード無)：T=0　[1]：T=1　…　[n-1]：T=n-1　[1]+[2]：T=3　…　[n-2]+[n-1]：T=2n-3　…　[1]+…+[n-1]：T=(n-1)n/2
n枚の時…(カード無)：T=0　[1]：T=1　…　[n-1]：T=n-1　[1]+[2]：T=3　…　[n-2]+[n-1]：T=2n-3　…　[1]+…+[n-1]：T=(n-1)n/2
　[n]：T=n　[1]+[n]：T=n+1　[n-1]+[n]：T=2n-1　[1]+[2]+[n]：T=n+3　…　[n-2]+[n-1]+[n]：T=3n-3　…　[1]+…+[n-1]+[n]：T=n(n+1)/2

以上のように、カードがn枚の時の合計Tは最小値が0で最大値がn(n+1)/2になります。 そしてnが2以上の時は、カードの組み合わせが違っても同じ合計になるものがあります。 またカードの組み合わせはn枚のカードのそれぞれを「取る／取らない」で決まるため、組み合わせ数は全部で2n通りあります。 そのため合計がTになるカードの組み合わせ数をmとすると、合計がTになる確率はm/2nになります。

mを求めるために、nが増えるとカードの組み合わせがどのように増えるか考えてみましょう。 まず1枚の時と2枚の時を比べると、2枚の時は、1枚の時のカードの組み合わせ(カードなし)とカード[1]を全て含んだ上で、それらにカード[2]が追加された[2]と[1]+[2]——上の例で太字で表記したもの——が増え、カードの組み合わせ数が2倍になることがわかります。

これを一般化すると、n枚の時は(n-1)枚の時のカードの組み合わせを全て含んだ上で、さらにカード[n]が追加されたカードの組み合わせが増え、カードの組み合わせ数が2倍になります。 このことから、n枚の時に合計がTになるカードの組み合わせ数mを組み合わせ数関数f(n,T)で表すと、これは(n-1)枚の時に合計がTになる組み合わせ数f(n-1,T)に、合計が(T-n)になる組み合わせ数f(n-1,T-n)を足した数になることがわかります。

またn＞0の時はT=0になるカードの組み合わせは(カード無)だけであり、T=1になるカードの組み合わせは[1]だけであり、T=n(n+1)/2になるカードの組み合わせは[1]+…+[n]だけです。 そしてn＞1の時はT=2になるカードの組み合わせは[2]だけであり、T={n(n+1)/2-1}になるカードの組み合わせは[2]+…+[n]だけです。 さらにT＜0またはT＞n(n+1)/2になるカードの組み合わせは存在しません。 これらのことから、f(n,T)を次のような漸化式で表すことができます。

f(n≦0,T)=f(n,T＜0)=f(n,T＞n(n+1)/2)=0
f(n＞0,0)=f(n＞0,1)=f(n＞0,n(n+1)/2)=f(n＞1,2)=f(n＞1,n(n+1)/2-1)=1
カードの合計がTになる組み合わせ数：m=f(n,T)=f(n-1,T)+f(n-1,T-n)
カードの合計がTになる確率：p=m/2n

この漸化式を利用して、n=3の時にT=3になるカードの組み合わせ数と、n=13の時にT=10になるカードの組み合わせ数を計算すると次のようになります。

＜計算例＞
・n=3、T=3の時
　m=f(3,3)=f(3-1,3)+f(3-1,3-3)=f(2,3)+f(2,0)=1+1=2
　p=2/8=0.25
・n=13、T=10の時
　m=f(13,10)=f(13-1,10)+f(13-1,10-13)=f(12,10)+f(12,-3)=f(12,10)+0 =f(11,10)+f(11,-2)=f(11,10)+0=f(10,10)+f(10,-1)
　　=f(9,10)+f(9,0)=f(9,10)+1=f(8,10)+f(8,1)+1=f(7,10)+f(7,2)+2 =f(6,10)+f(6,3)+3=f(5,10)+f(5,4)+f(5,3)+f(5,-3)+3
　　=f(4,10)+f(4,5)+f(4,4)+f(4,-1)+f(4,3)+f(4,-2)+3 =1+f(4,5)+f(4,4)+f(4,3)+3=f(3,5)+f(3,1)+f(3,4)+f(3,0)+f(3,3)+f(3,-1)+4
　　=1+1+f(3,4)+1+2+4=f(2,4)+f(2,1)+9=0+1+9=10
　p=10/213=10/8192=0.001
n=13の時のバイナリ—ツリー
○上のバイナリ—ツリー(二分木)の構造
・左側の葉(リーフ、終点)は漸化式のf(n-1,T)を表し、f(n,T＞n(n+1)/2)=0の時はカードの組み合わせが存在せず、f(n＞0,T=n(n+1)/2)=1の時はカード[1]+…+[n]、f(n＞1,T=n(n+1)/2-1)=1の時はカード[2]+…+[n]
・右側の葉は漸化式のf(n-1,T-n)を表し、f(n,T＜0)=0の時はカードの組み合わせが存在せず、f(n＞0,T=0)=1の時は(カード無し)のみ、f(n＞0,T=1)=1の時はカード[1]のみ、f(n＞1,T=2)=1の時はカード[2]のみ
○カードの組み合わせ
・関数値が1の葉について、合計がTになるカードの組み合わせが1種類存在する。
・左側の葉については、T=n(n+1)/2の時は[1]+[2]+…+[n]、T={n(n+1)/2-1}の時は[2]+…+[n]
・右側の葉については、T=0の時は(カード無)、T=1の時は[1]のみ、T=2の時は[2]のみ
・葉から上に向かって枝をたどり、左側の枝(左向きの矢印)の時は、枝が出ている節(ノード、2本の枝が出ている四角形)のカードは追加しない。
・葉から上に向かって枝をたどり、右側の枝(右向きの矢印)の時は、枝が出ている節の最大のカード[n]を追加する。
・枝をたどって根(ルート、最初の節)までたどり着いたら、そこで終了。
※＜例＞　赤い葉[f(3,5)=1]のカードの組み合わせ
(1) この葉は左側の葉だから、T=5=3×4／2-1=[2]+[3]の組み合わせになる。
(2) この葉の上の枝は左側の枝だから、節[f(4,10-5)=f(4,5)]のカードは追加しない。
(3) 節[f(4,10-5)=f(4,5)]の上の枝は右側の枝だから、枝が出ている節[f(5,10)]の最大のカード[5]を追加する。
(4) 節[f(5,10)]の上の枝は根[f(13,10]まで全て左側の枝だから、カードは追加せずに終了。
(5) その結果、カードの組み合わせとその合計は[2]+[3]+[5]=10なる。

ちなみにこの漸化式を計算するプログラムを例えばC言語で組む時は、再帰法というプログラム技法を利用して、次のようなエレガントなプログラムを組むことができます。 またカードの組み合わせは、この漸化式を利用してバイナリ—ツリーを構築し、それを再帰的にたどることによって知ることができます。

int f(int n, int t)
// カードの組み合わせ数を返す関数
{
　int tmax = n * (n + 1) / 2;
　if (n <= 0 || t < 0 || t > tmax) return 0;
　if (t <= 1 || t >= tmax - 1) return 1;
　return f(n - 1, t) + f(n - 1, t - n);
}
最終更新日：2016年1月18日　解答に疑問がある方はメールしてください！
【我楽多頓陳館】 　〒webmaster@snap-tck.com 　Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)