Looking for help with real life logic puzzle

[lucasdmiller]

Here is my situation: There will be 6 total couples competing in a "Couples Olympiad" this Friday at our house. We are having 3 rounds of games with 3 different games each round. Each game is played between two couples.

So for example, in Round 1:
Couple 1 might be playing against Couple 2 in Candy Land, while Couple 3 & 4 are playing Jenga and Couples 5 & 6 are playing Boggle.
Then after that, Couples 4 & 6 would play Candy Land, while Couples 2 & 5 play Jenga and Couples 1 & 3 play Boggle, which would mean that the following would have to happen:
Couples 3 & 5 play Candy Land, 1 & 6 play Jenga and 2 & 4 play Boggle. And that would be round 1. Then in round 2 & 3 there would be three new games respectively in each.

Here is what I would like to accomplish: each couple needs to play in each of the 3 games in each round (no one plays the same game twice), but I would like the couples to rotate through who they compete against. So since there are a total of 9 games, I would like for each couple to compete against 4 of the other couples twice and compete against one other couple once. And it is ok if a couple ends up playing another couple twice in one round.

So far the best schedule I could figure out ended up having a couple compete 3 times against 1 couple, twice against 2 others, & once against the remaining 2 [See Below]
So, 1) is my goal possible & 2) can anyone figure out the schedule for me?

Here is my best attempt:

Round 1
Candy Land: 1 v 2
PIG: 3 v 4
Guess Who: 5 v 6

Candy Land: 4 v 6
PIG: 2 v 5
Guess Who: 1 v 3

Candy Land: 3 v 5
PIG: 1 v 6
Guess Who: 2 v 4

Round 2
Connect Four: 1 v 4
Jenga: 2 v 3
Boggle: 5 v 6

Connect Four: 2 v 6
Jenga: 1 v 5
Boggle: 4 v 3

Connect Four: 5 v 3
Jenga: 6 v 4
Boggle: 1 v 2

Round 3
Pictionary: 3 v 6
Fastrack: 4 v 5
Trivia: 1 v 2

Pictionary: 1 v 4
Fastrack: 2 v 3
Trivia: 5 v 6

Pictionary: 2 v 5
Fastrack: 1 v 6
Trivia: 3 v 4

[Proginoskes]

That's a tough one, and it's more of a combinatorial puzzle than a logic puzzle. (You probably should have posted this a few days ago.)

There might be some parity conditions that suggest that your arrangement is best possible.

[tcamolesi]

You can represent each round using an undirected graph, where each vertex represents a couple and each edge is a game played between them. Since a couple must play 3 games each round, each vertex must have 3 edges.

Now, there are 2 restrictions that are imposed by the scheduling in each round:

1. No two couples can play against each other twice in the same round (i.e. you can only have one edge joining two vertices in the graph):

Suppose you have the following matches in a round: (1,2), (1,2), (1,3), (2,4) and you try to schedule it, the result would be:

Code: Select all

           | Game 1 | Game 2 | Game 3  |
Candy Land | 1x2    |        |         |
PIG        |        | 1x2    |         |
Guess Who  |        |        | 1x3/2x4 | -> You'd have to schedule both 1x3 and 2x4 in the same slot


Since you can't have the same couple appearing in the same row of the table (no one plays the same game twice) and they also can't appear in the same column (no one can play two games at the same time), you can't have two couples playing against each other twice in the same round.

2. You can't have K3 (complete graph of 3 vertices) as a subgraph of your game graph.

Suppose you have the following games in a round: (1,2), (1,3), (2,3) and (1,4). The scheduling table would be:

Code: Select all

           | Game 1 | Game 2 | Game 3  |
Candy Land | 1x2    |        |         |
PIG        |        | 1x3    |         |
Guess Who  |        |        | 2x3/1x4 |


Therefore, this arrangement is also impossible.

With those two restrictions and the imposed number of edges per vertex, the game graph must be bipartite K3,3. I'm no graph theorist and I have no idea of how to formally prove this, but I couldn't find any graph that meets those restrictions and isn't bipartite. Any graph with a 5-face isn't admissable and those with 4-faces and 6-faces are K3,3.

So, now we have to create 3 K3,3 graphs - one for each round - trying to minimize the number of times a pair of couples face each other (that is: they appear in different sets). Here's the best I could do:

Round 1:({1,2,3} vs {4,5,6})
Round 2:({1,4,5} vs {2,6,3})
Round 3:({1,3,6} vs {2,4,5})

In this arrangement, there are 2 pairs of couples that play 3 times against each other: (3,4) and (3,5)

By the way, your arrangement was:

Round 1:({1,4,5} vs {2,3,6})
Round 2:({1,3,6} vs {2,4,5})
Round 3:({1,3,5} vs {2,4,6})

Here, there are 3 pairs of couples that play 3 times against each other: (1,2), (3,4), (5,6)

[lucasdmiller]

Thank you both for your assistance. Glad to know I can stop trying to figure out a solution!

[mike-l]

Your solution is best, Tomtom's doesn't have 4 playing 5.

Here's the full proof:

To expand on Tomtom's statements, he's shown that if a couple plays another couple more than once, they must play each other the whole round, and for every couple, none of their opponents in a round can play each other that round. It is possible for a pair of couples to play each other every game of a round, but this requires every couple to do so, for then there are only 4 couples remaining, and Tomtom has already showed that a round robin cannot be scheduled, so some couple must double up, and thus triple up, forcing the final pair of couples to triple up as well.

Assuming it's not a round as above, Tomtom's right that the arrangement must be K_3,3, which is easy to see. Take any couple, their three opponents can each not play each other, so must play the other 2 couples (as well as the selected couple).

The question is then if there are 3 partitions of [6] into two sets of 3 such that every element is paired with every other element at some point (the pairing represents a round they don't play each other in). Suppose such a set of partitions existed. Then 1 is paired with 6 numbers, so must be paired with some number at least twice, without loss of generality call that number 2, and assume they are paired with 3 and 4 in the first two partitions. Then 1 and 2 must both be paired with 5 and 6 in the third, which is impossible.

So some couple must play another couple 3 times.

Now, suppose there's a round of couples facing off 3 times. Without loss of generality, say its 1v2, 3v4, 5v6. 1 needs to play 3,4,5,6, so there must be at least one round of the K_3,3. Say he plays 3, then he must also play 4, or else 3 would have to play 4 a fourth time. But then there's only one spot left for 5 or 6, so 5 and 6 will play a fourth time. So if there's a 'face-off' round, then some couples must meet 4 times or some couples will not meet at all. This is inferior to posted solutions.

In Tomtom's arrangement, 4 and 5 never meet. Indeed, any time a couple plays 2 other couples 3 times, those two couples can never meet, since they are always in the same partition, the one opposite the player the are playing 3 times.

Suppose couple 1 meets couple 2 three times. Then they must play 2 couples (say 3,4) twice and 2 couples once (say 5,6). 2 will then play 3,4 once and 5,6 twice. So each of 3-6 has 6 games with the other 3. 3 may not play 4 all three rounds, as they could not then both play 1 twice. Similarly 5 and 6 cannot play each other all 3 rounds. If 3 plays 5 all 3 rounds, then 4 must play 6 all 3 rounds, as after placing 1 and 2 on opposite partitions, and 3 and 5 on opposite partitions, only one spot remains per partition. This is possible, it corresponds to your solution.

So the only other possibility is that all the remaining couples play each other twice. 3 playing 4 twice, since they both play 1 twice, necessitates the rounds being 1,3 v 4, 1,4 v 3, and 3,4 v 1, as the 2 rounds where 3 plays 4, neither 3 nor 4 can play 1 both rounds, as the other would not have time to play twice against 1. Similarly, the 3 rounds must be 2,5v6, 2,6v5, 5,6v2. Without loss of generality, this makes the setup (since 2 must always play 1):

1,3,5 v 2,6,4
1,4,6 v 2,5,3
1,5,6 v 2,3,4

and 3 plays 6 every time, and never plays 5, a contradiction.

So the only solution that has every team playing every other team at least once and not more than 3 times, is the one you posted.