組み合わせの問題です。

質問

当方はすでに社会人ですが（というか、もういい歳なのですが）、
最近、気になった問題があるので、お教えください。

１６人の集団があるとします。
まず、４人ｘ４グループに分かれてゲーム（麻雀でも何でもいいです）をやります。
次に２回戦も、グループ分けを変えて、再度４人ｘ４グループに分かれて行います。
３回戦、４回戦、、、も、そのたびにグループ分けを変えることにします。

この場合、すくなくとも何回戦までやれば、
１６人それぞれが、他の１５人全員と少なくとも１度は同じグループになる事を経験できるでしょうか？

ある特定の参加者にとって、１回ごとに３人と同グループになるので、
１５割る３で少なくとも５回以上はかかるということはわかります。
ただ、紙に書き出してみると、どうやっても５回ではうまくいきそうもありません。
また、逆に５回では絶対にできないという証明もできませんでした。

５回なのか６回なのか７回なのか？
それが最小回数であるという理由（証明）をお教えいただければと思います。

回答No.4

graphaffine

Phoibosさん、今晩は。
アフィン平面の話ですね。詳細は別にして結論を述べると以下の通りです。

定理：Nを自然数としてN^2人がN人ゲームを行う。このとき、各人が(N+1)回ずつゲームを行って、ちょうど１回ずつ同じグループになるようにすることができる。

従って、ご質問はN=4の場合ですので、５回でできるということになります。

その証明ですが、下記サイトが（そのものずばりではないが）参考になります。但し、大学レベルの代数学や組合せ論の知識が必要なのでご注意のこと。
http://www32.ocn.ne.jp/~graph_puzzle/1no44.html　--(A)
http://www32.ocn.ne.jp/~graph_puzzle/1no52.html　--(B)
なお、(A)はアフィン平面の簡単な性質、(B)は、定理の証明が記述されています。

回答No.3

chamiken

１回目
1,2,3,4 / 5,6,7,8 / 9,10,11,12 / 13,14,15,16
２回目
1,5,9,13 / 2,6,10,14 / 3,7,11,15 / 4,8,12,16
３回目
1,6,11,16 / 2,5,12,15 / 3,8,9,14 / 4,7,10,13
４回目
1,7,12,14 / 2,8,11,13 / 3,5,10,16 / 4,6,9,15
５回目
1,8,10,15 / 2,7,9,16 / 3,6,12,13 / 4,5,11,14

でファイナルアンサーです。今度はちゃんと確認もしました！

証明は、かなりマニアックなので、概要だけ。
上の１回目を４×４の正方行列と見る。
そうすると２回目は縦横を逆転したもの。
余因子展開して、４×３＝１２。４組に分けるから１２÷４＝３
で、２＋３＝５回。
まぁ意味不明だと思うので、上の書き出したもので納得頂ければ幸いです。
ご興味がありましたら、余因子展開などを勉強なさればご理解頂けます。

回答No.2

chamiken

あ、すいません、違ってました！！(＞＿＜)
回答者No.1です。
後でもう一度挑戦してみます！

回答No.1

chamiken

５回でできますよ～。

便宜的に、16人を1～16の番号で表すと、
１回目
1,2,3,4 / 5,6,7,8 / 9,10,11,12 / 13,14,15,16
２回目
1,5,9,13 / 2,6,10,14 / 3,7,11,15 / 4,8,12,16
３回目
1,6,11,16 / 2,7,12,13 / 3,8,9,14 / 4,5,10,15
４回目
1,7,12,14 / 2,8,9,15 / 3,5,10,16 / 4,6,11,13
５回目
1,8,10,15 / 2,5,11,16 / 3,6,12,13 / 4,7,9,14
以上より、５回で可能である。
15÷3＝5より４回は不可能なので、求める解は５回。