【数学A】例題4.2.16：部屋割り論法（One More）★★

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.16：部屋割り論法（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) クラスで行うあるプロジェクトのチームのメンバーは，13名で構成されている．このとき，少なくとも2人のメンバーの誕生月が同じであることを示せ．

(2) $n$を自然数とする．異なる$n+1$個の整数から，適当な2個を選ぶと，その差が$n$の倍数になることを示せ．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.16の解答（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) 誕生月は1月から12月までの12通りである．したがって，12名以下の場合であれば，全員の誕生月が異なる場合もあるが，13名の場合は，少なくとも2人の誕生月が同じでなければならない．

よって，少なくとも2人のメンバーの誕生月が同じである．$\blacksquare$

(2) $n+1$個の数を$a_1,a_2,\ldots,a_n,a_{n+1}$とする．

これらの数を$n$で割った余りを，それぞれ$r_1,r_2,\ldots,r_{n+1}$とする．

このとき，それぞれの余り$r_i$は，すべて$0$以上$n-1$以下の$n$個の整数のいずれかである．

したがって，$n+1$個の余り$r_1,r_2,\ldots,r_{n+1}$の中には，少なくとも同じ値が2つ存在する．

ここで，その2つの余りを$r_i,r_j$とすると，$a_i$と$a_j$は次のように表される．

\[
a_i=nk_i+r_i,a_j=nk_j+r_j(k_i,k_j\text{は整数)}
\]

ゆえに，

\[
a_i-a_j=(nk_i+r_i)-(nk_j+r_j)=n(k_i-k_j)
\]

よって，$k_i-k_j$は整数であるから，$a_i-a_j$は$n$の倍数である．$\blacksquare$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.16：部屋割り論法（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

赤玉が6個，白玉が4個，青玉が3個入っている箱がある．この箱から玉を取り出すとき，いずれかの色の玉が必ず3個以上になるためには，最低何個取り出せばよいか．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.16の解答（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

いずれの色の玉も2個以下となるように取り出せる最大の個数は，$2+2+2=6$（個）である．

したがって，箱から7個取り出すと，少なくとも1つの色の玉が3個以上となる．

よって，最低7個取り出せばよい．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.16の側注：部屋割り論法（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
部屋割り論法の考え方を用いる．

% 側注2
$n$で割ったときの余り$r$は，$0\leqq r<n$

% 側注3
$n+1$個の余りと$n$個の整数に，部屋割り論法の考え方を用いる．

% 側注4
$r_i=r_j$

% 側注5
$k_i,k_j$は整数であるから，$k_i-k_j$も整数である．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.16の側注：部屋割り論法（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
部屋割り論法の考え方を用いる．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.16の考え方・補足など：部屋割り論法（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

部屋割り論法「$n+1$個のものを$n$組に分けるとき，2個以上入っている組が少なくとも1つ存在する」を利用する．

(1) チームのメンバーは13名であり，誕生月は1月から12月までの12通りであることに注目する．

(2) 2つの数が$n$の倍数どうしであるとき，その差も$n$の倍数になる．$n$の倍数ではない2つの数の差が$n$の倍数になるためには，その2つの数をそれぞれ$n$で割った余りが等しければよい．そこで，$n$で割ったときの余りを分類して考える．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 部屋割り論法
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n+1$個のものを$n$組に分けるとき，2個以上入っている組が少なくとも1つ存在する．