46

« Last post by **raydog ** on* October 10, 2022, 04:35:18 PM* »
I am in charge of scheduling for a euchre tournament held by a group of fraternity alums each year, where I have dealt with exactly this problem. My constraints are that we have a variable number of people participating each year, and for our initial seeding round I'd like to have as much "mixing" as possible, so (if possible):

1) everyone plays at a table at least once with every other player (either as partner or opponent);

2) if multiple meetings are required, then we don't have pairs which sit together twice while another pair never meets (or one pair meets each other 3 times while another pair hasn't yet met 2 times);

3) no two players are partners twice.

We also have a time constraint, so play exactly 8 rounds (no more, no less).

I have devised schedules for 15 to 36 players using these constraints, and found many of them by using a computer program (rather poorly designed, as I am not a great programmer) running billions of combinations and trying to find the best one. I let some scenarios run for literally weeks! Truly brute force, but it did produce results.

In the end, I was not able to optimize every scenario, but I think I found some pretty reasonable solutions. I was able to avoid any players ever meeting 3 times, but I wasn't always able to have every possible pair of players meet. I calculated the "ideal" situation by comparing the number of actual parings in the tournament (#tables X # rounds) to the number of different possible pairings = n(n-1)/2, where n is the number of players. I presume this ideal is not always achievable, but it gave me a target to shoot for.

I found ideal solutions for 16, 17, 20 and 27+ players.

For the rest, I found the following:

players never meet (ideal) never meet (my solution)

18 0 5

19 0 12

21 0 7

22 0 19

23 13 27

24 0 8

25 12 26

26 37 52

in the case of 15 players, I think I am still far from optimal: I have 18 pairs never meeting and 6 pairs meeting 3 times! Fortunately, we generally have more than 15 players in attendance.

I'd be happy to share these schedules if anyone is interested, but as they are quite specific and would take a long time to type our I prefer to wait for a specific request. Also, if anyone can improve upon my results (as summarized above), please do let me know.

Finally, is there an easy way to generate the solution for 40 players? I know how to generate the perfect solution for 39 rounds (every player partnering with every other player exactly once and opposing every other player exactly twice), but is there a 13 round solution which has every possible pair meeting exactly once [from which I would just take any 8 games]?

Ray