A coworker came to me with an interesting problem, a practical one having to do with a "new people in town" group she's a part of.
18 friends want to have dinner in groups for each of the next 4 days. The rules are as follows:
A brute force recursive search for a valid set of group assignment is obviously impractical. I've thrown in some simple logic for pruning parts of the tree as soon as possible, but not enough to make it practical.
Actually, I'm starting to suspect that it might be impossible to follow all the rules, but I can't come up with a combinatorial argument for why that would be.
Any thoughts?
16 friends can be scheduled 4x4 for 4 nights using two mutually orthogonal latin squares of order 4. Assign each friend to a distinct position in the 4x4 grid. On the first night, group by row. On the second, group by column. On the third, group by similar entry in latin square #1 (card rank in the 4x4 example). On the fourth, group by similar entry in latin square #2 (card suit in the 4x4 example). Actually, the affine plane construction gives rise to three mutually orthogonal latin squares, so a fifth night could be scheduled, ensuring that each pair of friends meets exactly once.
Perhaps the schedule for 16 could be extended, using the freedom of the unused fifth night.
EDIT: here's the schedule for 16 people over 5 nights. Each row is a night. Each column is a person. The entry is the group to which they're assigned.
[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]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With