| Ask any Bridge club director. Such movements are published in the
Director's handbook for many numbers of teams. The specific movements
you want are called "Howell"'s. They are actually not used very
much in Bridge tournaments, because they can get very complicated,
and there are no really simple rules that apply to all numbers of
teams. In other words, the pairings for 12 teams behave quite
differently from the pairings for 10 teams. And adding a team at
the last minute, or after the first round, can really screw things
up.
No, the problem is not too simple to pose here. Not by a long shot.
|
| Well, I hate to disagree with anyone who has Lynn's reputation of
being correct, BUT I think that your situation is not all that bleak
Zack.
For an odd number of players there exists a simple algorithim that
unless I'm mistaken, will satisfy all of your requirements:
Given n an odd integer
and r, and j the round and player that you are interested in;
(j is numbered from 0 to n-1)
Calculate p = ((j+r) mod n) + 1
If (p < (n+1)/2) then assign player j to table T = p.
If (p > (n+1)/2) then assign player j to table T = (n-p).
If (p = (n+1)/2) then player j has a bye.
I guess this sounds a litle complicated, but it looks like this:
TABLE ROUND-1 ROUND-2 ROUND-3 ROUND-4 ROUND-5 ROUND-6 ROUND-7
1 1-7 7-6 6-5 5-4 4-3 3-2 2-1
2 2-6 1-5 7-4 6-3 5-2 4-1 3-7
3 3-5 2-4 1-3 7-2 6-1 5-7 4-6
bye 4 3 2 1 7 6 5
Now for an even number of players it is only slightly more involved:
Take the solution for n-1 players (an odd number). Instead
of having one player get a bye, the n-th player will always
play him instead.
Thus our 7-player solution can be made into an 8-player solution
like so:
TABLE ROUND-1 ROUND-2 ROUND-3 ROUND-4 ROUND-5 ROUND-6 ROUND-7
1 1-7 7-6 6-5 5-4 4-3 3-2 2-1
2 2-6 1-5 7-4 6-3 5-2 4-1 3-7
3 3-5 2-4 1-3 7-2 6-1 5-7 4-6
4 4-8 3-8 2-8 1-8 7-8 6-8 5-8
It so happens that these are NOT the pairings used in a Howell movement
(at least according to my Encyclopedia of Bridge). I belive that
this is because bridge tournaments have one more very important
constraint. That is that the "hands" must also be evenly distributed,
and this algorithim does not solve that problem for the even numbered
case. If you look at the 8-player tournament above, replacing "table",
with "hand" you will see that player #8 is always playing hand #4.
Now it is true that permutating the above can produce an acceptable
solution to this problem, but its not always straightforward.
Fortunately for you, Zack pool tournaments usually have no such
requirements. ( 9^} )
-- Barry
|
| Actually the more difficult Bridge problem hints at an evem more
diffcult and much more significant (mathematically) class of problems.
When I was in high school I was very active in our high school debate
team and participated in the season long local high school tounaments.
Now each school had 2 teams, an affirmative team, and a negative
team, as well as one judge, referees the debates.
A debate consists of one schools affirmative team debating
anothers negative team, and is judged by a third schools judge. The
tournaments consisted of one full rotation, that is:
Each schools affirmative team was to meet every other schools
negative team exactly once.
Each schools affirmative team, and negative team was to be judged
by every other teams judge exactly once.
And naturally, a school never debated itself, or was judged by itself.
It turns out that this problem is trivial for an odd number of schools,
but we usually had 12 schools in the tournament, and we would play
one round of the tournament each week, until the full rotation was
completed. For an even number of teams, the problem was not only
difficult, it was widely belived to be impossible, not only by
frustrated tounament directors of various sports, but also by
mathematicians for well over a hundred years.
In Bridge, for instance this kind of tournament is called a "Mitchell"
movement, and an odd number of tables uses exactly the simple solution
that I alluded to earlier. The even numbered movements, however,
compromise by having one table sit idle every round, and another
table playing an extra set of hands. In debate, we compromised
by having all the teams miss being judged once by one judge,
and instead be judged a second time by one other judge.
However, I think that it was when I was a sophomore in college,
this problem was solved for even numbered cases. Although it had
not been previously proven to be impossible, it had been widely
suspected as being impossible. Now however, sucessful examples
were demonstrated for the 6 & 8 numbered cases, and a general theory
and method (I think (?)) had been formulated regarding even numbered
cases.
So, seeing as cookies are the standard prize, I offer a cookie to
each of the first people to:
A) Identify the name of the problem in mathematics, who is
credited with first stating the problem, and finally who solved
it.
B) Give an example of a 12-numbered rotation, WITHOUT looking
it up.
-- Barry
(Note: since it took hundreds of years for someone to find an example
of an even numbered solution you may assume that (B) is VERY hard.)
|
| Re: .5
>> A) Identify the name of the problem in mathematics, who is
>> credited with first stating the problem, and finally who solved
>> it.
>>
>> B) Give an example of a 12-numbered rotation, WITHOUT looking
>> it up.
Answer (I think) and a caveat:
A) According to my Encyclop�dia Brittanica, 15th edition, 1978,
vol 4, pp 946-947 this is a problem in BIB (Balanced Incomplete Block)
designs. The person first stating the problem was T.P. Kirkman in the
19th century. It was finally solved by Dwijendra K. Ray-Chaudhuri and
R.M. Wilson in 1970. (� a cookie (?) 8-) ).
B) I think you want a solution giving 11 rounds. After much
delibiration (sp?) and head scratching I can't come up with a solution.
I can only come up with a 9-round solution. Clearly this is not
satisfactory, because not every affirmative team gets to meet every
negative team. Oh well, much keener minds than mine have been working
on this for more than 100 years, so I don't feel too disappointed.
Wildrik 8-)
|