When I was sick recently, my boss e-mailed me a math problem he said I might try to solve to pass the time. Now, I had thought that this was a problem he had read somewhere, but no: this is an actual thing that happened to him. It happens to lend itself to a cool problem, and here it is:
You have ten players and five two-player games at a party. There will be five rounds of games, and each round will include all five games played simultaneously. You want every player to play each game once, and never play against the same player more than once. Is there a solution?
Once you’ve worked that out, consider:
(a) Is there a solution if you have N rounds of games and 2N people, where N is an arbitrary odd number?
(b) Is there a solution to (a) if N is even?
I know the answer to (a). I suspect I know it for (b) but I can’t prove it. I’d like to see what you all can come up with.
UPDATE 11/14/2011 This problem has been completely solved in the comments! Check them out.
UPDATE 2: 11/15/2011 I’ve also put the C++ code I used to brute-force a solution in the N=6 case online here, in case anyone’s interested.
November 13, 2011 at 7:07 am
These guys, yes? http://en.wikipedia.org/wiki/Graeco-Latin_square
Sorry for the lack of creativity. I don’t know (any) proof of existence of these guys so in some sense I haven’t actually solved it. I guess for n odd you can do e.g. (A)1(B)1 (playing first game) 22 33 in the first one then add 1 to the first one and 2 to the second one each row so 23 31 12 in the second round, then 32 13 21 in the third round.
(This has the extra fun property that matchups used are the complete bipartite graph, allowing for fair result comparisons among each set of n people.)
This is a stronger condition than you need so it doesn’t imply failure where there are no GL squares. For n=1 it’s trivial, n=2 it’s “obviously” impossible. n=6 isn’t immediately clear to me, my instinct is that you could make it work.
November 14, 2011 at 5:57 pm
Aha! Nice. I have tried to read pretty much everything Martin Gardner ever wrote so I should have come up with that. So yes, this takes care of every case except N=6. Time to get to work on that case.
EDIT: I wrote a quick C++ script to try to brute-force that case. I’ll run it overnight and, assuming it’s done by tomorrow morning, we’ll see what it gives.
November 15, 2011 at 1:06 am
All right, here we go.
As Mike points out, for N=1 the problem is trivial and for N=2 one can quickly see it’s impossible by running through possibilities. For every other N except 6 there exists a Graeco-Latin square, which implies a solution to this problem. However, for N=6 I don’t believe a solution was known until I wrote a C++ program to perform a brute-force search, which came up with this:
I haven’t completely checked it, but I do believe this is a solution for N=6, which solves this problem completely. Now you know, if you’re at a party and this situation comes up.