2
$\begingroup$

I have an interesting real life problem that can be turned into an interesting puzzle pertaining to a tournament that can be represented in this way: I have 24 people which are assigned numbers 1 to 24. A team of them are in groups of three.

ex: (1,2,3) is a team. Obviously, groups such as (1,1,3) are not possible. 4 games can arise from these teams, ex: (1,2,3) vs (4,5,6), (7,8,9) vs (10,11,12), (13,14,15) vs (16,17,18) and (19,20,21) vs (22,23,24).

There will be 4 of these games per round as there are always 8 teams, and 7 rounds in the entire tournament. The problem comes when these restrictions are placed: once 2 people are put on the same team, they cannot be on the same team once more. Ex: if (1,2,3) appears in round 1, (1,8,2) in round 2 cannot appear since 1 and 2 are on the same team.

The second restriction is that people cannot face off against each other more than once. Ex: if (1,2,3) vs (4,5,6) took place, then (1,11,5) vs (4,17,20) cannot because 1 and 4 already faced off against each other.

If there are 4 simultaneous games per round, is it possible to find a unique solution for creating and pairing teams for 7 continuous rounds with these criteria met? I'm not sure if there is a way to find just 1 solution without extensive (or impossible amounts of) computational resources, or if its somehow provable that there are 0 solutions. All I'm looking for is just 1 valid solution for 7 rounds, so in that way it can be seen as a nice (or very challenging in my case) puzzle.

$\endgroup$
1

2 Answers 2

4
$\begingroup$

In general, this is just a constraint satisfaction problem and there are usually several ways of solving such problems without using exponential amounts of time/space. Even backtracking works most of the time if you're careful to propagate constraints correctly.

For your tournament in particular:

I encoded your problem as a propositional boolean formula and solved it with a SAT solver. The code I wrote to encode the problem is here. I can solve a 5-round variant to get:

Round 1: (1, 2, 3) vs (4, 5, 6), (7, 8, 9) vs (10, 11, 12), (13, 14, 15) vs (16, 17, 18), (19, 20, 21) vs (22, 23, 24)

Round 2: (1, 4, 13) vs (8, 20, 22), (2, 5, 24) vs (7, 12, 18), (3, 17, 19) vs (9, 16, 21), (6, 10, 14) vs (11, 15, 23)

Round 3: (1, 5, 21) vs (11, 13, 16), (2, 18, 22) vs (9, 17, 23), (3, 12, 20) vs (10, 15, 19), (4, 8, 14) vs (6, 7, 24)

Round 4: (1, 6, 23) vs (12, 17, 24), (2, 7, 14) vs (3, 13, 21), (4, 15, 20) vs (5, 9, 11), (8, 10, 18) vs (16, 19, 22)

Round 5: (1, 10, 20) vs (14, 18, 21), (2, 15, 17) vs (8, 19, 24), (3, 4, 11) vs (12, 13, 23), (5, 7, 16) vs (6, 9, 22)

I could not find solutions for 7 rounds or even 6 within a few days. I played around with some symmetry-breaking constraints to speed up the search a little and the most effective was:

1. The first round is forced to be (1,2,3) vs. (4,5,6), (7,8,9) vs (10,11,12), etc.

2. The first teams are lexicographically ordered throughout rounds, e.g., team 1 is (1,2,3) in round 1, (1,4,22) in round 2, (1,6,8) in round 3, etc.

3. The two teams within each match are lexicographically ordered, e.g., the first match of round 1 is (1,2,3) vs (4,5,6) instead of the other way around

4. All matches within a round are lexicographically ordered by their constituent players, e.g., round 1 is (1,4,22) vs. (7,11,23), (2,5,13) vs. (12,14,21), ... because the tuples of all players within a match are ordered (1,4,7,11,22,23) < (2,5,12,13,14,21)

I could solve a variant of your original puzzle which might be interesting to you since even the 6-round case doesn't seem easily solvable. If you relax your second restriction and allow players to face off at most twice, you can get a 7-round tournament:

Round 1: (1, 2, 3) vs (4, 5, 6), (7, 8, 9) vs (10, 11, 12), (13, 14, 15) vs (16, 17, 18), (19, 20, 21) vs (22, 23, 24)

Round 2: (1, 4, 22) vs (7, 11, 23), (2, 5, 13) vs (12, 14, 21), (3, 16, 19) vs (9, 15, 17), (6, 20, 24) vs (8, 10, 18)

Round 3: (1, 6, 8) vs (13, 18, 23), (2, 15, 20) vs (4, 14, 24), (3, 7, 10) vs (5, 12, 19), (9, 16, 21) vs (11, 17, 22)

Round 4: (1, 7, 15) vs (2, 21, 24), (3, 8, 23) vs (10, 13, 16), (4, 11, 20) vs (6, 17, 19), (5, 14, 18) vs (9, 12, 22)

Round 5: (1, 11, 13) vs (6, 12, 15), (2, 9, 19) vs (10, 21, 22), (3, 4, 17) vs (7, 18, 24), (5, 8, 20) vs (14, 16, 23)

Round 6: (1, 16, 24) vs (18, 19, 22), (2, 4, 7) vs (9, 10, 20), (3, 5, 15) vs (8, 13, 21), (6, 11, 14) vs (12, 17, 23)

Round 7: (1, 21, 23) vs (10, 19, 24), (2, 16, 22) vs (12, 13, 20), (3, 6, 18) vs (7, 14, 17), (4, 8, 15) vs (5, 9, 11)

In fact, even an 8-round tournament is possible with the relaxed constraint.

$\endgroup$
8
  • 3
    $\begingroup$ It looks like person 1 and person 14 face each other in rounds 1 and 3 ... is there a bug in the code? $\endgroup$ Apr 16 at 14:43
  • 3
    $\begingroup$ Whoops, thanks! You're right, I encoded that constraint wrong. Fixed and updated my answer. $\endgroup$ Apr 16 at 17:15
  • 1
    $\begingroup$ Farthest I've gotten is up to the 5 round variant as well and have yet to discover a round 6 solution, so if anyone gets even a round 6 that's also pretty big. $\endgroup$ Apr 16 at 23:06
  • $\begingroup$ @AaronWindsor, did your solver ever find solutions for 6 or 7? $\endgroup$ Apr 21 at 0:26
  • $\begingroup$ @AlexDeCarlo I posted an update in the answer above. $\endgroup$ Apr 21 at 11:46
2
$\begingroup$

SAT-solver symmetry breaking

There are 56 total teams of 3. Let's define a "Golden Triple" as a team where all pairs of team members are opponents at some point.

Each player will have 21 total opponents, avoiding only 2 other players as opponents. So, 24 pairs of players are never opponents out of 276 total pairs.

Each pair of players is on no more than one team of 3. So at most 24 teams are not Golden Triples. So, there will always be a round where at 3 or fewer of the teams are not Golden Triples. That round will have at least 5 Golden Triples. So, 3 of the 4 courts of that round will have a Golden Triple.

Let's call that round Round 1.

Round 1: (1, 2, 3) vs (4, 5, 6), (7, 8, 9) vs (10, 11, 12), (13, 14, 15) vs (16, 17, 18), (19, 20, 21) vs (22, 23, 24)

Without loss of generality, we can assume that (1, 2, 3), (7, 8, 9) and (13, 14, 15) are all Golden Triples. But let's just assume (1, 2, 3) is a Golden Triple. Then we know 1vs2, 2vs3, 3vs1 must happen in 3 separate rounds, and {1,2,3} must be on separate courts in the remaining 3 rounds:

Round 2: (1, ?, ?) vs (2, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
Round 3: (2, ?, ?) vs (3, ?, ?), (1, ?, ?) vs (?, ?, ?), ...
Round 4: (3, ?, ?) vs (1, ?, ?), (2, ?, ?) vs (?, ?, ?), ...
Round 5: (1, ?, ?) vs (?, ?, ?), (2, ?, ?) vs (?, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
Round 6: (1, ?, ?) vs (?, ?, ?), (2, ?, ?) vs (?, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
Round 7: (1, ?, ?) vs (?, ?, ?), (2, ?, ?) vs (?, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
$\endgroup$
3
  • $\begingroup$ There's no extension of this argument to 6 rounds, is there? With 6 rounds, there are T=48 total teams of 3. Each player has 18 total opponents, avoiding 6 other players as opponents, so there are P=72 pairs of players that are never opponents. But we need T > P to assert there's a golden triple somewhere in some round if I understand correctly. In any case, I will try this out on the 7-round encoding! $\endgroup$ Apr 22 at 12:12
  • $\begingroup$ ...avoiding 5 other players as opponents, so...P=60... but still the argument doesn't extend to 6 rounds. It might still be interesting to add in the symmetry breaking to see what the result is, you'll have more information either way (if the search terminates). $\endgroup$ Apr 23 at 0:28
  • 1
    $\begingroup$ Minor improvement: (4,5,6) are together in the first round and playing against (1,2,3). This means that in rounds 5,6,7 they cannot play against (1,2,3) any more and at most two of them can play in the fourth field at the same time, leaving at least one player each round to be a teammate of one of (1,2,3). This means that we can set team 1 in round 5 to be (1,4,?) WLOG $\endgroup$
    – Leo
    Apr 23 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.