I just finished hosting a Euchre tournament at work that was meant to get people to meet other people in the company. This is the third time I've hosted this type of tournament. The first two times, we had 28 and 36 people play 7 rounds and I could not figure out a schedule that allowed for everyone to play with another play a maximum of one time. This time, we had 80 people play 8 rounds and I had no issue guaranteeing that everyone person was scheduled against others a maximum of one time. I'm considering altering the format for our next tournament and I want to know if there is a formula or algorithm that can be used to either:
- Determine the maximum number of rounds (r) that can be scheduled to guarantee each person is only scheduled to play with another person a maximum of one time throughout the tournament, given p number of participants.
OR
- Determine the minimum number of participants (p) that are needed to guarantee that each will be scheduled against another participant a maximum of one time, given r number of rounds.
The format of the tournament is: for each round, I schedule 4 people to a group. They play 3 games, one with each other group member as their partner. So, each participant plays against 3 other people in each round. Points are reported to me and the sum of points/wins is totaled to determine a ranking. There is no elimination. You can assume that the number of participants is a multiple of 4.
The way that I've scheduled this, up to this point, is to put the names in a column in a spreadsheet and use a formula that based on the table number (t:1-20), seat number (s:1-4), a seed number for the round (r:1,4,5,7,9,11,13,17), and number of participants (p) that would pick a person from the list and put them into that seat. The basic formula is something along the lines of
i = ((((t - 1) * 4) + (s - 1)) * r + 1) % p
It also accounts for if p is divisible by r by adding 1 each loop through the list. I'm not sure if this is necessarily the most efficient way to schedule, but I doubt that it is. Before the first tournament, I tried writing a program to do the schedule via recursive backtracking and it did not come up with one. I assume that this is due to the limited number of participants.
I'm not sure if this is a P vs. NP issue, but it seems like there could be some elegant solution as is the case with most other tournament formats. If there is a formula or algorithm to determine this, I can keep this in mind while altering the format in the future.
Thanks for any insights on this.