第224問の解答


1.問題 [場合の数

から32までの整数が書いたカードが1枚ずつ、計32枚あります。

この計32枚カードの中から3枚を同時に取り出すとき、互いの数の2以上になるような取り出し方
何通りあるでしょうか。

2.解答例1ヒデー王子さん、高橋道広さん、noetherさん、他)

 ・カード枚数で、差が2以上の場合・・・(A)
 ・カード枚数
n−2で、差が2以上でなくても良い場合・・・(B)
の2通りの取り出し方を考えます。

参考図1

A)で取り出したときの数字を小さい順にa、b、cとします。
このとき、a、b−1、c−2a<b−1<c−2となるので、(B)の場合の1つの取り出し方になります。

逆に、(B)で取り出したときの数字を小さい順にx、y、zとします。
このとき、x、y+1、z+2差が2以上あるので(A)の場合の1つの取り出し方になります。

以上から、(A)(B)取り出し方の数は等しいことになります。
(B)では、
 n−2
=(n−2)(n−3)(n−4)/3・2・1
      =30・29・28/6=4060通り

従って、(A)4060通りになります。

答:4060通り


3.解答例2ふぇるまーさん、H.Takaiさん、すうぱあさん、M.Hossieさん、N.Nishiさん、せんださん、mhayashiさん、他多数)

n個カードから3枚選ぶ組み合わせの数は、n3で得られます。

この中には、選んだカード数字の差が1以下の場合がありますので、これを除くことにします。

参考図2

差が1以下のものがあるときは、数字が連続した2枚カードを1組と、それ以外の1枚カードを選ぶことになります。

これは、n−1個のものから2個選ぶことと同じになりますが、選んだ2個を入れ替えたものは異なる場合になりますので、組み合わせの数は2×n-1C2になります。

この中には、3枚連続したカードを選ぶことが含まれますが、2個のものと1個のものを入れ替えたもので重複して数えることになりますので、今度はこの分、すなわちn−2個のものから1個選ぶn-2C1にだけ加える必要があります。

従って、求める場合の数は、
  n32×n-1C2n-2C1
 =n(n−1)(n−2)/6−2(n−1)(n−2)/2+(n−2)
 =(n−2)(n−3)(n−4)/6
 =30・29・28/6
 =4060通り
となります。


4.解答例3Gouさん、AUさん、圭太さん、あんみつさん、糸瀬善人さん、他多数)

(カードを2枚選ぶ場合)
まず、n枚カードから2枚選んで差が2以上の場合の数を求めます。

参考図3

最初に選ぶカードの数字で分類します。

のとき:隣のは選べませんから、残りは3〜nまでのn−2通り
のとき:隣のは選べませんから、残りは4〜nまでのn−3通り
  ・・・
n−2のとき:隣のn−1は選べませんから、残りは1通り

従ってこれらを合計すると、
 1+2+・・・(n−2)=(n−2)(n−1)/2通り
になります。

(カードを3枚選ぶ場合)
同様に、
最初に選ぶカードの数字で分類します。

参考図4

のとき:残りは3〜nまでのn−4枚から2枚選ぶ(n−4)(n−3)/2通り
のとき:残りは4〜nまでのn−5枚から2枚選ぶ(n−5)(n−4)/2通り
  ・・・
n−4のとき:残りはn−2〜nまでの3枚から2枚選ぶ2・1/2=1通り

=n(n+1)(n+2)/3とすると、
−S
k-1
 =k(k+1)(k+2)/3−(k−1)k(k+1)/3
 =k(k+1)

よって、
  
Σ(k=1..n)
k(k+1)
  =Σ(k=1..n)(S−Sk-1
  =S−S
  =Sn 
  
=n(n+1)(n+2)/3 ・・・(1)

求める場合の数は、
 1/2・Sn−4
 =(n−4)(n−3)(n−2)/6 
 =30・29・28/6

 =4060通り


4.解答例3POIさん、うっしーさん、他)

真ん中のカードを最初に選ぶ方法で分類します。

参考図5

のとき:左側のカードのみの1通り、右側は5〜nまでのn−4通り
のとき:左側のカード1〜22通り、右側は6〜nまでのn−5通り
  ・・・
n−2のとき:左側のカード1〜n−4n−4通り
  右側はのみの1通り

よって合計は、
  Σ(k=1..n-4)k(n−3−k)
 =(n−3)Σ(k=1..n-4)k−Σ(k=1..n-4)2
 =(n−3)(n−4)(n−3)/2−(n−4)(n−3)(2n−7)/6
 ={(n−4)(n−3)/6}{3(n−3)−(2n−7)}
 =(n−4)(n−3)(n−2)/6
 =4060通り


5.解答例4(DrKさん、他)

漸化式で考えます。
カードn枚から3枚選ぶときの場合の数をf(n)2枚選ぶ時をg(n)1枚選ぶ時をh(n)とします。

参考図6

(1)カード1枚を選ぶとき:h(n)=n通りとなります。

(2)カード2枚を選ぶとき:

 よって、g(n)=g(n−1)+n−2が成り立ちます。
 従って、
  g(n)=Σ(k=1..n)(k−2)+g(0)
    =(n−2)(n−1)/2通り
 
となります。

(3)カード3枚を選ぶとき:

 よって、f(n)=f(n−1)+g(n−2)が成り立ちます。
 従って、
  f(n)=Σ(k=1..n)(k−4)(k−3)/2+f(0)
    =(n−4)(n−3)(n−2)/6  ・・・(1)
より
    =4060通り
 
となります。