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

% 例題A4.2.16：部屋割り論法 （One More）★★
(1)クラスで行うあるプロジェクトのチームのメンバーは,13名で構成されている.このとき,メンバーの誕生日は,少なくとも2人が同じ月に誕生日を迎えることを示せ. (2)異なる$n+1$個の整数から,適当な2個を選ぶと,その差が$n$の倍数になることを示せ.

% 解答（例題A4.2.16）
(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=n k_i+r_i, a_j=n k_j+r_j(k_i,k_j \text{ は整数)}$$ゆえに,$$a_i-a_j=(n k_i+r_i)-(n k_j+r_j)=n(k_i-k_j)$$よって,$k_i-k_j$は整数であるから,$a_i-a_j$は$n$の倍数である.$\blacksquare$

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

% 解答A4.2.16
いずれの色の玉も2個以下となるように取り出せる最大の個数は,$2+2+2=6$（個）である. したがって,箱から7個取り出すと,少なくとも1つの色の玉が3個以上となる. よって,最低7個取り出せばよい.