Search code examples
mathproofgame-theory

Grouping 1-12 in groups of 4 with the least number of duplicates


Consider 12 people who want to meet up to play a game every week. They meet in groups of 4. They want to play each other an even number of times.

After 4 weeks there doesn't seem to be any combination that allows each player to have played with all 11 opponents. I haven't been able to prove it, but I've yet to find a solution.

So what is the smallest value of N such that after (N*4) weeks every player can be guaranteed to have played with all other players at least N times? Can it be done for N=2?


Solution

  • This is very similar to the Social Golfer Problem -- an unsolved problem in mathematics. Here's a relevant post from math.stackexchange which discusses what you're looking at. If your concern is focused on the math behind it, you may want to repost it there, since that's not really suited for stackoverflow.

    If you're just concerned about an algorithm to attempt to solve it (and don't want to just brute force it), this paper presents a bunch approaches to solving problems of this type. It's a pretty dense read, but it's a place to start. There's also a list of explicit solutions to some cases, but I don't know how useful it will be to you (since the problem is slightly different).

    If you really just want to prove a lower bound for N, since its discrete and the cases you're examining are relatively small, your best bet would probably be to throw together a brute force search algorithm, and increment N until it works.

    Finally, here's a few other links that may or may not be useful: http://www.bridgeguys.com/Conventions/movements_for_bridge.html http://www.jdawiseman.com/papers/tournaments/individual-pairs/individual-pairs.html http://www.csplib.org/Problems/prob010/
    https://www.metalevel.at/sgp/