Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2017-07-25 12:16:23

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
?

Offline

#2 2017-07-28 19:24:27

Nehushtan
Member
Registered: 2013-03-09
Posts: 905
Website

Re: A pairing problem

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


Blog
222 books currently added on Goodreads

Offline

#3 2017-07-28 20:15:38

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)

Offline

Board footer

Powered by FluxBB