Kombinatoryczny algorytm przydzielania osób do grup

Question

Przyszedł mi do mnie współpracownik z interesującym problemem, praktycznym związkiem z grupą "nowych ludzi w mieście", z którą jest częścią.

18 znajomych chce zjeść kolację w grupach dla każdego z kolejnych 4 dni. Zasady są następujące:

1. Każdego dnia grupa będzie podzielone na 4 grupy po 4, a grupa 2.
2. Wszelkie podane parę osób będzie widzieć tylko siebie co najwyżej raz w ciągu 4 dni.
3. Dowolna dana osoba będzie tylko częścią grupy wielkości 2 najwyżej jeden raz.

Wyszukiwanie rekursywne z użyciem siły brutalnej dla prawidłowego zestawu przydziału grupy jest oczywiście niepraktyczne. Wrzuciłem prostą logikę do przycinania części drzewa tak szybko, jak to możliwe, ale nie na tyle, aby było to praktyczne.

Właściwie to zaczynam podejrzewać, że niemożliwe jest przestrzeganie wszystkich reguł, ale nie mogę wymyślić kombinatorycznego argumentu za tym, dlaczego tak się stało.

Jakieś myśli?

Answer 1

16 znajomych może być zaplanowanych 4x4 na 4 noce przy użyciu dwóch mutually orthogonal latin squares z porządku 4. Przypisać każdemu przyjacielowi do odrębnej pozycji w siatce 4x4. Pierwszej nocy, grupując po kolei. Na drugim, grupa po kolumnie. Na trzecim, grupa przez podobny wpis na łacińskim kwadracie # 1 (ranking karty w przykładzie 4x4). Na czwartym, grupa przez podobny wpis w łacińskim kwadracie # 2 (kolor karty w przykładzie 4x4). W rzeczywistości konstrukcja samolotu afinicznego powoduje powstanie trzech wzajemnie ortogonalnych kwadratów łacińskich, więc można zaplanować piątą noc, upewniając się, że każda para przyjaciół spotyka się dokładnie raz.

Być może harmonogram 16 lat może zostać przedłużony, wykorzystując wolność niewykorzystanej piątej nocy.

EDYCJA: oto harmonogram dla 16 osób na 5 nocy. Każdy rząd to noc. Każda kolumna to osoba. Wpis to grupa, do której zostali przypisani.

[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]