[Banana]

The best puzzles in world are one that looks tantalizing solvable but after few (well, many!) attempts, you're not so sure anymore!

So, I'm asking for help here.

Given those constraints:

We have 16 players.

They are to play in a group of 4 each and meets 5 time. So that's a grand total of 20 different groups.

Each player must play other exactly once.

At first, it seems solvable, given that as a given player must have 15 opponent, and he participates in a group five times, that's 3 opponents per group times 5 meetings, which is 15. The trouble is I'm not enough of a mathematician to discern the algorithm required to generate the 20 unique groups required to ensure that each player play only one other player exactly once, or prove that this is impossible. I've attacked this heuristically, and the best I've got so far is 15 groups before I run in any conflicts.

So... anyone care to attack this or show an proof that this is in fact impossible?

BTW, if anyone doesn't mind a spoiler, here is a website that provides different examples of various configuration for allocating players, but not any like the above: Linky

[scratt]

Are you looking for a programmatic solution?
Or a general algorithm?

Short of finding a fantastic and reliable source for a 'general algorithm' personally I'd probably attack this in C by generating a list of 16 names, and then create arrays of each possible play group for each of those names against groups of 3 players from the other 15.

I'd then pattern match those generated groups against groups from each of the other players until I got the smallest number of non-duplicate sets.

In theory that would give you the answer...

I am not sure if this is purely an academic exercise in which case a piece of QAD code could solve it for you quite quickly if you break it down into simple no-brainer steps (to eliminate logic errors). Or if you actually want to apply this to something and need a 'production' solution?

[Banana]

Pssttt... This is an AppleOutsider, not Programmer's Nook.

Just a general algorithm, though I'd be intrigued to see a example.

In my case, I experimented with a table of unique 3-way pairs (e.g. 012, 013, 014... DEF), then selected a player with a 3-way pair to form a group, then deleted all other 3-way pair that had one of six possible pair from the newly formed groups then moved on to next group. But I then ran out of possible rotations and noted that not all players get equal amount of opportunity to play. Whether this is because my algorithm was crap or because I'm solving a impossible problem, I don't know yet.

[Enki]

This is just a constraint satisfaction problem along the lines of "8 Queens". There are several types of approaches that will work to find the answers in relatively reasonable amounts of time.

[709]

1A 2A 3A 4A _ 1B 2B 3B 4B _ 1C 2C 3C 4C _ 1D 2D 3D 4D (so, we get that out of the way...all the letters play each other).
1A 1B 1C 1D _ 2A 2B 2C 2D _ 3A 3B 3C 3D _ 4A 4B 4C 4D (and now the numbers).
1A 2B 3C 4D _ 2A 3B 4C 1D _ 3A 4B 1C 2D _ 4A 1B 2C 3D (follow the numbers and letters).
1A 2C 3D 4B _ 2A 3C 4D 1B _ 3A 4C 1D 2B _ 4A 1C 2D 3B (follow the numbers, then skip a letter).
1A 3B 4C 2D _ 2A 4B 1C 3D _ 3A 1B 2C 4D _ 4A 2B 3C 1D (follow the letters, then skip a number).

1A 2A 3A 4A   1B 2B 3B 4B   1C 2C 3C 4C   1D 2D 3D 4D1A 1B 1C 1D   2A 2B 2C 2D   3A 3B 3C 3D   4A 4B 4C 4D1A 2B 3C 4D   2A 3B 4C 1D   3A 4B 1C 2D   4A 1B 2C 3D1A 2C 3D 4B   2A 3C 4D 1B   3A 4C 1D 2B   4A 1C 2D 3B1A 3B 4C 2D   2A 4B 1C 3D   3A 1B 2C 4D   4A 2B 3C 1D

I think that works...but my brain just handed me a restraining order, so I'll have to check my thought-process later.

[edit]: Fuck, my last train of thought is wrong. Hmm...
[edit2]: Fixed. ?
[edit3]: Cleaned it up a bit for clarity.

[scratt]

Originally Posted by Banana Pssttt... This is an AppleOutsider, not Programmer's Nook.

You try to help, and all you get is snide comments!

I think in code.. what can I say...

[Banana]

I think my description wasn't clear... Perhaps a example.

Meeting #1

0123456789ABCDEF

Meeting #2

048C159D26AE37BF

Meeting #3

05AF16BC278D349E

Conflicts is inevitable in meeting #4 and #5 given the groups above.

Hope that helps a bit.

[Banana]

Originally Posted by scratt You try to help, and all you get is snide comments!

Given the economy in US, snide comment is worth a fair value.

I think in code.. what can I say...

Nothing wrong with it! I simply did it heuristically only because I didn't feel that I had sufficient grasp on the problem and figured that by trial and error would help me notice patterns, but I suspect the problem is that I get locked in one track and thus become oblivious to the solution.

[709]

I found it easier to give each "person" a number and letter to keep track of them. My post above probably wasn't clear about that. I'll clean it up.

Here's mine reconfigured by your naming system:

1234567890ABCDEF159C260D37AE48BF16AF27BC389D450E10E82AF53BC649D717F6289A350F46AC

[Banana]

OH!

Sorry, didn't catch that. Now that I've read this, this was what I did in my early attempt, thinking that this was solved by a "magic square" or something like that...

This has conflict; 0 and 5 plays each other twice on third & fifth rotation. There was another conflict but I got distracted and lost it... Edit: 9 and A also played each twice on first and fifth rotation.

[709]

Shit!

The 9 and A is a typo in my tranlation, but the 0 and 5 is a bugger.

[Banana]

Yeah, tell me about it.

Been whacking at this for a month since someone mentioned that problem on another forum.

[leachboy]

Let me make sure that I understand your requirements. You have 16 players. They are playing a game in which 4 players compete against one another. You want each player to play every other player exactly once.

If my understanding above is correct, then in mathematical terms you are looking for a Pairwise Balanced Design or Balanced Incomplete Block Design of order 16 and blocksize 4. You're in luck because it turns out that one (and only one) exists. Here it is, copied from the CRC Handbook of Combinatorial Designs. Each column is a game.


0 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 5 6
1 4 7 a d 4 5 6 9 4 5 6 8 4 5 6 7 8 9 7
2 5 8 b e 7 b 8 c c 7 9 a 9 8 a b b a c
3 6 9 c f a d e f e f b d d c f e f e d

[Banana]

See, that's the problem. I'd never knew a Pairwise Balanced Design until it hit me on head.

Much thanks!

[Moogs]

While this puzzle thing has its intellectual advantages, I find that examining certain binary manifestations of the human genome can aid in solving the mysteries of life.

[Banana]

Uh, I'm sorry. I got distracted. Can you please repeat that?

[leachboy]

Glad to help. I'll also point out that if you wish to arrange these 20 games into 5 meets, you can do it. Label the meets W, X, Y, Z, and V.


0 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 5 6
1 4 7 a d 4 5 6 9 4 5 6 8 4 5 6 7 8 9 7
2 5 8 b e 7 b 8 c c 7 9 a 9 8 a b b a c
3 6 9 c f a d e f e f b d d c f e f e d
W X Y Z V V Y Z X Y Z V X Z V Y X W W W


In general, if you have n teams, you can set up a tournament like this if, when you divide n by 12, you get a remainder of 1 or 4. The reminder of 1 or 4 guarantees that you can get everyone to play everyone else exactly once, but it does not guarantee that you you can divide the games up nicely into meets.

[Banana]

That's quite a fascinating property. Why a reminder of 1 or 4, and why divide by 12, I wonder?

[leachboy]

Originally Posted by Banana That's quite a fascinating property. Why a reminder of 1 or 4, and why divide by 12, I wonder?

I can tell you why those conditions are necessary, but I'm not sure how to show that they are sufficient. There are two things you have to look at.

1. Consider any one particular player. In each game he plays three other players, so the number of other players must be a multiple of 3. So we get that n-1 is a multiple of 3.

2. Now count the total number of games that must be played. Since there are n players, there are n(n-1)/2 distinct pairs of players. Since each game has four players, each game uses up 6 pairs. Now the number of games = number of pairs ÷ number of pairs per game, so the number of games is n(n-1)/(2*6) = n(n-1)/12, and that must be an integer.

Now we need to figure out which integers satisfy both of the conditions above. Note that you can write any integer n as 12k+r, where k is an integer and r is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, or 11. Now by condition 1, n-1 must be a multiple of 3, so n must be a multiple of 3, plus 1. This eliminates all numbers except for those of the form 12k+1, 12k+4, 12k+7, and 12k+10. Now check to see which of these satisfy condition 2.

(12k+1)(12k)/12 is a whole number
(12k+4)(12k+3)/12 is a whole number
(12k+7)(12k+6)/12 is not a whole number
(12k+10)(12k+9)/12 is not a whole number

So the only numbers that could possibly work are numbers that are of the form 12k+1 or 12k+4.

[Banana]

Very fascinating. This is quite beautiful.

The trouble is that I didn't have a good grasp of mathematic to express this clearly. I only had a vague notions and did had realized that there were going to be 6 pairs that would be duplicate for any given group of 4 but didn't know what to do with it from there, so to speak.

[billybobsky]

Another way to think about it is that you need at least 1 odd man out or the ability to create a new game of loose pairs...

[709]

Yeah, it's pretty elegant. Neat.

I certainly never would've got there by the train I was on, but then again I'm not a mathologist.

[Robo]

People who like brain teasers like these (okay, they're not quite this complicated) should check out Professor Layton for the DS. It is super fun and the anime scenes are cute. Level 5 isn't paying me to say this, I promise! I just love the game so much and not many people have played it. It's the first part of a three-part story - with luck, we'll see the second part in early 2009.