Math Is Fun Forum

Complexity

Member

From: Denmark

Registered: 2013-12-27

Posts: 16

A pairing problem

Being a very social drinker I have come across a problem which I need some help with. I will try to make a sober analogue problem. Here goes:

Suppose a group of

people are to play exactly

matches with

available tables.

Each match has following restrictions:
Exactly two players are playing.
None of the players have met in a match before.
None of the players have played at that table before.

---------------------------------

I hope I mentioned everything needed. So for uneven amount of tables (and therefore matches) it is pretty clear that you could just divide the number of people into two sets, ie. {1,3,5...} and {2,4,6..}. Then you can place {1,2}, {3,4}, {5,6}... at each of their own table in the beginning and then just rotate all uneven numbers one place to the right and all the even numbers one place to the left.

It is not possible to solve the problem with

, but it is if

. For 

I have found a solution as well, but is rather complicated compared to 

and uneven

since I can't just permute two disjoint groups.

I suspect that this problem is solvable for all

, but can anyone proves this? And can anyone come up with an algorithm that is not bruteforce to solve this for each

?

Nehushtan

Member

Registered: 2013-03-09

Posts: 957

Re: A pairing problem

I don't get it: why is it not possible to solve the problem with n = 2?

---

240 books currently added on Goodreads

Complexity

Member

From: Denmark

Registered: 2013-12-27

Posts: 16

Re: A pairing problem

Because n=2 means two tables. Let's call those A and B. Now this means there is a total of 4 players. Let's call those 1, 2, 3 and 4.

We must have 2 rounds of games:

Round 1: Place player 1 and 2 at table A. For table B we then have player 3 and 4.
Round 2: Player 1 and 2 cannot sit at the same table as in the round before, so both of them has to move table. Since only table B is available they can only face eachother which is breaking the rule "None of the players have met in a match before."

Last edited by Complexity (2017-07-28 20:16:44)