第337問の解答
問題[場合の数、剰余]
1〜13までのカードが1枚ずつあります。 これらの中から4枚を同時に取り出すとき、4枚のカードに書かれた数の合計が13の倍数になるような取り出し方は何通りあるでしょうか。
解答例1
トトロ@Nさん、sugitakukunさん、ミミズクはくず耳さん、ねこやんさん、あほあほまんさん、ステップ ばい ステップさん、M.Hossieさん、航介さん、フランク長いさん、富山清風さん、他多数
4枚のカードの数を小さい順にa、b、c、dとして数え上げていきます。
まず、1〜11から異なる2個の数を選び小さい方からa、bとします。
- (a、b)=(1、2)のとき ・・・ a+b=3だから、和が13の倍数となるのは、c+d=10または23
よって、(c、d)=(3、7)、(4、6)、(10、13)、(11、12)- (a、b)=(1、3)のとき ・・・ a+b=4だから、和が13の倍数となるのは、c+d=9または22
よって、(c、d)=(4、5)、(9、13)、(10、12)以下、同様にして下表の結果を得ます。
よって、和が13の倍数となるのは、合計55通りとなります。
答: 55通り
以上
解答例2
数楽者さん、Miki Sugimotoさん、kotaeさん、 他
一般化して考えます。
(補題)
2つの自然数n>mが互いに素の場合、1〜nの数から異なるm個の数を同時に選んだとき、
これらの和をnで割った余りの個数は全て同じ。(本問では、n=13、m=4の場合)
- 1〜nの数から異なるm個の数を同時に選ぶ選び方は、全部でnCm通りあります。
まず、これがnの倍数であることを示します。
n-1Cm-1=(n-1)!/(n-m)!(m-1)!
={n!/(n-m)!m!}×m/n
=nCm×m/n
nとmは互いに素だから、nCmはnで割り切れる。・・・(1)
- 1〜nの数から異なるm個の数を同時に選ぶ選び方全体を{G}として、
これを次のようにn個のグループ分けします。
{G}から任意にG0=(a1、a2、・・、am)を取り出します。
k=0〜n-1に対し、Gk=(a1+k、a2+k、・・、am+k)とし、
ap+kがnを超えた場合はap+k−nに置き換えることとします。
すると、Gkの各数は1〜nとなります。 ・・・(2)
これらの和をsk、およびskをnで割った余りをrkとすると、rkは全て異なります。・・・(3)
なぜなら、もしrp=rq(ただし、p<q)と仮定すると、sq−spはnの倍数となりますが、
sq−sp={(a1+q)+(a2+q)+・・+(am+q)}-{(a1+p)+(a2+p)+・・+(am+p)}
=(a1+a2+・・+am+m×q)-(a1+a2+・・+am+m×p)
=m×q-m×p
=m×(q−p)
となり、mはnと互いに素で、しかも、0<q−p<nより、sq−spがnの倍数と矛盾します。
また、Gkについても全て異なります。 ・・・(4)
もし、Gp=Gq(ただし、p<q)と仮定すると、rp=rqとなって矛盾するからです。
従って、{G0、G1、・・・、Gn-1}はn個の相異なる{G}の要素となります。
また、Gn=(a1+n-n、a2+n-n、・・、am+n-n)=G0となることから、
このグループのどの要素を最初のG0としても同じグループになることが分かります。 ・・・(5)
従って、別のグループG'nの各要素は全てGn要素と異なることになります。以上から補題が成り立つことが示されました。
よって、和をnで割った余りの個数は全て同じだから、nCm/n通りとなります。
とくに本問では、13C4/13=715/13=55通りとなります。
(参考)n=8、m=3の場合のグループ化の例
(注)赤字:和がn=8の倍数
(その他の解法)
- プログラムを使って全ての場合をチェック ・・・ ぶなしめじTZさん、ハラギャーテイさん、まるケンさん、ふじさきたつみさん、小西孝一さん、萬田銀次郎さん、他