6

ある同僚が興味深い問題を抱えて私のところに来ました。それは、彼女が所属している「町の新しい人々」グループに関係する実用的な問題です。

次の 4 日間、18 人の友人がグループで夕食をとりたいと考えています。ルールは次のとおりです。

  1. 毎日、グループは 4 人の 4 つのグループと 2 つのグループに分けられます。
  2. どのペアの人も、4 日間で最大 1 回しかお互いに会うことができません。
  3. 任意の人物がサイズ 2 のグループに参加できるのは、多くても 1 回だけです。

グループ割り当ての有効なセットを再帰的に力ずくで検索することは、明らかに実用的ではありません。できるだけ早くツリーの一部を剪定するための単純なロジックをいくつか投入しましたが、実用化するには不十分です。

実際、すべてのルールに従うことは不可能かもしれないと疑い始めていますが、なぜそうなるかについての組み合わせ論的な議論を思いつくことはできません.

何かご意見は？

4

1 に答える 1

4

互いに直交する次数 4 の 2 つのラテン方陣を使用して、16 人の友人を 4 泊 4x4 でスケジュールできます。各友人を 4x4 グリッド内の異なる位置に割り当てます。最初の夜に、行ごとにグループ化します。2 つ目は、列ごとにグループ化します。3 番目に、ラテン語の正方形 #1 の同様のエントリ (4x4 の例ではカードのランク) でグループ化します。4 番目に、ラテン スクエア #2 (4x4 の例ではカード スーツ) の同様のエントリでグループ化します。実際には、アフィン平面の構成により、相互に直交する 3 つのラテン方陣が生成されるため、5 番目の夜をスケジュールして、各ペアの友人が 1 度だけ会うようにすることができます。

おそらく、未使用の 5 泊目の自由を利用して、16 日のスケジュールを延長することができます。

編集: 5 泊 16 人のスケジュールは次のとおりです。各行は夜です。各列は人です。エントリは、割り当てられているグループです。

[0, 0, 0, 0,  1, 1, 1, 1,  2, 2, 2, 2,  3, 3, 3, 3]
[0, 1, 2, 3,  0, 1, 2, 3,  0, 1, 2, 3,  0, 1, 2, 3]
[0, 1, 2, 3,  1, 0, 3, 2,  2, 3, 0, 1,  3, 2, 1, 0]
[0, 2, 3, 1,  1, 3, 2, 0,  2, 0, 1, 3,  3, 1, 0, 2]
[0, 3, 1, 2,  1, 2, 0, 3,  2, 1, 3, 0,  3, 0, 2, 1]
于 2012-09-25T17:24:26.087 に答える