Life In 19x19

I think that you have an NP-complete problem.

There are weird linkages between S and Q. When pairing the Q-finals, it is presumably possible to have player Z who has played five of the other seven Q-finalists. It therefore makes sense to pair the other two ( call them X and Y ) so that someone is guaranteed to be available to play Z in the semis without duplication. But now there can be a player W who, for similar reasons, needs X to play against V. There is, IMHO, no way to be sure that one can reconcile this short of trying every set of pairings.

Some shortcuts may occur, but categorizing them is a bitch. In the classic NP-complete example, the traveling salesman, I recall that it can be proven that the optimal solution cannot include taking the three longest paths consecutively. The ordering of paths from longest to shortest in the traveling salesman problem is trivial. The ordering of possible pairs in Q-finals is not clearly so.

I think that you just have to brute-force this one.

Li Kao wrote:... there are only 105 possible starting arrangements for single elimination tree with 8 players. ... It's 8!/(2^4*4!)=105

True. But more easily calulated by 7 * 5 * 3 = 105

EDIT: Or, to be complete: 7 * 5 * 3 * 1 = 105.

Harleqin wrote:If you do not have a fixed tree, but instead re-pair each round after the previous has been completed, the proceeding is very simple: just do not repeat a pairing. The rounds are independent then, so you only have to look at the players in the round at hand.

This does not necessarily minimize.

Joaz Banbeck wrote:7 * 5 * 3 * 1 = 105.

Now this explains itself nicely without words, thanks!

RobertJasiek wrote:

Harleqin wrote:If you do not have a fixed tree, but instead re-pair each round after the previous has been completed, the proceeding is very simple: just do not repeat a pairing. The rounds are independent then, so you only have to look at the players in the round at hand.

This does not necessarily minimize.

I think it does, because the players' probability to reach a certain round is equal.

Ok, now we have two theories: NP-complete versus trivial:) Who can prove his theory - Joaz or Harleqin or neither?

Harleqin wrote:

RobertJasiek wrote:

Harleqin wrote:If you do not have a fixed tree, but instead re-pair each round after the previous has been completed, the proceeding is very simple: just do not repeat a pairing. The rounds are independent then, so you only have to look at the players in the round at hand.

This does not necessarily minimize.

I think it does, because the players' probability to reach a certain round is equal.

But the player's probability of reaching a certain round with optimally non-repetitive colleagues is not. And it is affected by pairing choices in the prior round.

The Q-final and the S-final rounds are not truly independent. For a player Z, starting in the Q-finals, it is possible to have three players, W, X, and Y, such that they are the only three players that Z has not played. So to try to be optimal, in the Q-final, Z is paired with one of them - let's choose W.
For the set of all possible Q-final pairings that include the Z vs W pairing, there are two possibilities: either X and Y are paired or they are not paired. If X plays Y, there is a 100% probability that there will be a non-repeat player to pair with Z if he makes it to the S-finals; if X does not play Y, there is a 75% probability that there will be such a person for Z to play.
The rounds are not independent, QED.

From your proof about the implied lemma of the rounds being dependent, I learn that my assumptions were still insufficient. It does not suffice to ask for minimal numbers but rather one must "multiply" each pairing strategy's winning case by conditional probabilities of wins to get the probabilities for each pairing strategy to cause a certain expected number of repetitions in both rounds. Only then can one choose the overall minimum.

Hi, Robert,

you have got E-Mail.

Thomas

There are 105 possible first round pairings. They generate 70 possible quartets for for the semi-finals, leading to 28 possible finals pairs. Thus the upper bound for the total number of possibilities is 205800. That is well within brute-force range.

Joaz Banbeck wrote:There are 105 possible first round pairings. They generate 70 possible quartets for for the semi-finals, leading to 28 possible finals pairs. Thus the upper bound for the total number of possibilities is 205800. That is well within brute-force range.

The room to work with is not that big.

You have those 105 combinations for the pairing of the first round with 16 combinations of possible outcomes each.

The four players in each of this outcome-combination could be paired in 3 different ways in round 2. What does not matter, because you are watching for the minimum of the number of doubled pairs.

Take the average of the 16 second round (minimum) numbers and add it to the number of doubled pairs in the respective first round combination.

Check the minimum of the 105 concluding sums and chose one of the first round combinations with this minimum value.

I am doubtfull about the number of 105 combinations possible

in my idea there are 315 different combinations:

There are 35 ( 8!/(2 x 4! x 4!) ways to split 8 players in two groups of 4

In every group of 4 there are 3 different ways to do the tournament

giving a total of 35 * 3 * 3 = 315 combinations.

but maybe I am wrong: "What makes 2 combinations different ?"

willemien wrote::study: I am doubtfull about the number of 105 combinations possible

in my idea there are 315 different combinations:

There are 35 ( 8!/(2 x 4! x 4!) ways to split 8 players in two groups of 4

In every group of 4 there are 3 different ways to do the tournament

giving a total of 35 * 3 * 3 = 315 combinations.

but maybe I am wrong: "What makes 2 combinations different ?"

You are wrong. You count pairings multiple times.
(a-b, c-d), (e-f, g-h) is equivivalent to
(a-b, e-f), (c-d, g-h) and (a-b, g-h), (c-d, e-f)

Matti wrote:

willemien wrote::study: I am doubtfull about the number of 105 combinations possible

in my idea there are 315 different combinations:

There are 35 ( 8!/(2 x 4! x 4!) ways to split 8 players in two groups of 4

In every group of 4 there are 3 different ways to do the tournament

giving a total of 35 * 3 * 3 = 315 combinations.

but maybe I am wrong: "What makes 2 combinations different ?"

You are wrong. You count pairings multiple times.
(a-b, c-d), (e-f, g-h) is equivivalent to
(a-b, e-f), (c-d, g-h) and (a-b, g-h), (c-d, e-f)

But (a-b, c-d), (e-f, g-h) , (a-b, e-f), (c-d, g-h), (a-b, g-h), (c-d, e-f) ARE different.

IF you see it as an immutable tree and think about the games that will happen after the first round.

Supposing the first mantioned player wins:

in (a-b, c-d), (e-f, g-h) the hext games will be a-c and e-g
in (a-b, e-f), (c-d, g-h) the hext games will be a-e and c-g
in (a-b, g-h), (c-d, e-f) the hext games will be a-g and c-e .
(and these are all different)


But if you see the rounds as independent of each other you are right.

You guys are over-complicating it.

You have 8 people on 4 boards. Pick one player; there are 7 people that he can be paired with. Then there are 6 people left. Pick one of them; there are 5 people that he can be paired with. Now there are 4 people left. Pick one of them; there are 3 people that he can be paired with. You are now at the last board, with 2 people left and there is only 1 way to pair them.

7 * 5 * 3 * 1 = 105