Math problem

[LGM]

I had an SEIV turn to do Last night (my gracious host is running turns manually while PBW is down). Maybe tonight I can tackle writting a program to find combinations for Geo.

It is an interesting problem. This time I will probably write it in Delphi and make it a Windows executible. I'll need to arrange my data a bit better to back track when I get stuck down a blind alley looking for a solution.

I'll publish the code. Delphi code should be fairly easy for C++ or Java programmers to understand as the language is somewhat similiar.

[Erax]

I tried doing 9 on paper myself and I couldn't do it. Probably because I did it much the same way I programmed it.

I did it graphically. I set the players up like this :

1 2 3
4 5 6
7 8 9

Then connected them first horizontally, then vertically, then along the diagonals (you have to imagine that the numbers 'wrap around' for the diagonals). To my surprise, this solved it for nine players.

[tesco samoa]

http://www.singlix.com/download/combinator.html

has the source code for the routine that determines pairing of numbers

It is in turkish but stepping though it will be ok

[Hakuen Kage]

(Loser showed me this thread this morning, I hope I'm not imposing.)

If you were doing it standard elimination style, then it would just be powers of 3. Since each contest would require three participants, you would need three games to fuel each contest. So it would work with 3, 9, 27, 81, 243, 729...

If you want each person to actually play each other person only once, then it's a bit tougher.

In order to determine the number of games it will take for everyone to play everyone, do the following (exactly as Cybersol suggested):

n = Number of players
x = number of games each player must play
z = number of players per game

x = (n-1)/(z-1)

In each game, each player removes two (or the number of people in each game minus one) people from the pool of people that they must play. They obviously don't have to play themselves, so you have to remove from from the total.

From this, we can see that the set with a solution is an odd integer (since x has to be an integer). It is of the form 2x + 1, which in fact means, it is a positive odd integer. Positive because the number of games played must be positive.

Let's try 5. Find x and write down the first player x number of times like so:

1
1

Now go to player two. Since you can't have them playing each other more than once, you need to record it as follows:

1,2
1
2

Proceed to 3

1,2,3
1,
2
3

4:

1,2,3
1,4
2,4
3

5:

1,2,3
1,4,5
2,5
3,4

Here we come to an additional limitation on the number of players required. In this case, we have 10 elements which are not going to fit evenly into games where only three people play at a time. The number of elements must also be divisible by 3 (z).

e = number of elements

e = x * n
or
e = x * [x*(z-1)+1)]

Since e has to be divisible by z

e mod(z) = 0

We can simplify for our particular case

e = 2x^2 + x

So, for all values of x where:

(2x^2 + x) mod(3) = 0

Should be the solutions to your problem. Some of you programmers should be able to write a program to solve that in a heartbeat.

I believe the solutions you will come up with (based on intuition) are that the numbers will be of of the form 3r + 1 and 3r. So all numbers divisible by 3 should work (duh) and all those numbers plus one should work.

Okay, I just verified the 3r + 1 solution set and it works. If someone wants that proof, I'll more than happily post it.

This solves the problem for the number of games that each player must play. So the number of players it works for can be easily backtracked.

2x + 1 = n

So the solution sets for the number of players will be 6r + 1 and 6r + 3. This can actually be seen quite easily by looking at Cybersol's Last post.

With that in mind, someone should be able to easily write a program that uses the method in my example above to arrange the matches. Randomizing it would be tricky, but is still quite doable. Sadly, I can only code in Pascal and I don't have a compiler handy.

Edit: I got my friend's handle wrong. Oops.

[ August 07, 2003, 20:58: Message edited by: Hakuen Kage ]

[Loser]

Somebody asked for a mathematician?
Is he great or what?
Somebody give the teacher an apple.

[SamuraiProgrammer]

Originally posted by Slynky:
One of the good things about chess and its rating system (see my remark about one possible way to have a rating system in SE4 in the "New League" thread) is the wonderful way tournements can be run. Using the rating of the player, you just use Swiss-System pairing and get a tourney done in 4-5 rounds...considering anywhere from 15-30 people.

I play in bridge tournaments where there are 'Swiss' events. It works pretty well in that as you win, you play against people that are winners (and more apt to be at your level). As you lose, you play against others who did not win (and more apt to be at your level).

It ends up being an event that, after the first few rounds, you end up playing against your own level of competition. This makes the matches more enjoyable. Everyone wants to feel competitive.