wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> tennis competition
        
(Message started by: gert1 on Jan 28th, 2004, 12:23pm)
Title: tennis competition
Post by gert1 on Jan 28th, 2004, 12:23pm
Please help and my collegue with this puzzle:


[b][/b]You are asked to make a tennis match schedule for 9 persons. They play doubles, so each round one person is spare for fetching balls. The first round may be: 1-2 vs 3-4 and 5-6 vs 7-8. There is one problem: every round you have to switch partners and opponents, so that every combination occurs only once and every opponent is only met twice during the tournament of  9 rounds. E.g. If you are player 1 you play with nr 2 once and against him twice (with different partners).

The question is: can you make the schedule or prove that this is impossible. What is then a sub-optimal schedule (best mix of opponents)?

Next question: expand to 12 players (with 11 rounds), 13, 16, 17 (17 rounds) players and so on.
Title: Re: new riddle: tennis competition
Post by THUDandBLUNDER on Jan 28th, 2004, 11:35pm
I don't think it's possible for 9 players in 9 rounds.

Here's a solution for 8 players in 7 rounds:

Round 1 --  1 and 2  vs  3 and 4     5 and 6  vs  7 and 8
Round 2 --  1 and 3  vs  5 and 7     2 and 4  vs  6 and 8
Round 3 --  1 and 4  vs  5 and 8     2 and 3  vs  6 and 7
Round 4 --  1 and 5  vs  2 and 6     3 and 7  vs  4 and 8
Round 5 --  1 and 6  vs  3 and 8     2 and 5  vs  4 and 7
Round 6 --  1 and 7  vs  4 and 6     2 and 8  vs  3 and 5
Round 7 --  1 and 8  vs  2 and 7     3 and 6  vs  4 and 5

And for 12 players in 11 rounds, each round containing 3 matches:

[ab | ce]    [hi | kd]     [jg | lf]
[ac | df]     [ij | le]      [kh | bg]
[ad | eg]    [jk | bf]     [li | ch]
[ae | fh]     [kl | cg]    [bj | di]
[af | gi]      [lb | dh]    [ck | ej]
[ag | hj]     [bc | ei]    [dl | fk]
[ah | ik]     [cd | fj]     [eb | gl]
[ai | jl]       [de | gk]   [fc | hb]
[aj | kb]     [ef | hl]     [gd | ic]
[ak | lc]     [fg | ib]     [he | jd]
[al | bd]     [gh | jc]    [if | ke]

The above are examples of 'Balanced Incomplete Block Designs' (BIBDS).
Search for Block Design at http://mathworld.wolfram.com/ for a somewhat technical explanation.

In the second, v = 12, k = 4, lambda = 3, b = 33, and r = 11.
Similar block designs exist for v = 4n, k = 4, lambda = 3, r = 4n - 1, and b = n(4n - 1) for all positive n.
Hence a solution should also exist for 16 players (v = 16).
Title: Re: new riddle: tennis competition
Post by Quetzycoatl on Jan 29th, 2004, 8:03am

on 01/28/04 at 23:35:26, THUDandBLUNDER wrote:
Similar block designs exist for v = 4n, k = 4, lambda = 3, r = 4n - 1, and b = n(4n - 1) for all positive n.


I think v = 9  may work. v = 5 works and, unless I am misunderstanding, it does not fit the criteria described above.

12 v 35     4 sits out
13 v 54     2 sits out
14 v 23     5 sits out
15 v 24     3 sits out
25 v 34     1 sits out
Title: Re: new riddle: tennis competition
Post by Guest on Jan 29th, 2004, 10:45am
I think Thudandblunder wasn't taking into consideration that one player sits out. I don't have a solution yet, but here's a fairly simple suboptimal way to solve it.
Arrange nine points around a circle and connect them with straight lines in every possible way to make the pairings. The simultaneous pairings are denoted by all parallel lines. So, for example you get 1 and 2, 3and9, 4and 8, and 5and6 in the first match up. Now you have to pair up the pairs as opponents. So, to pick 1's opponents you must choose one line parallel to each of 1's matchups, such that every other point is used twice. In the drawing, that will create a closed circuit, visiting the other 8 points once, with no two lines parallel to each other nor perpendicular to point 1's radius. An example circuit would be 2,3,9,7,8,5,4,6,2. Matching each of those lines with the 1 line that is parallel to it gives a solution (suboptimal in this case). The match ups would be
12v39  48v57
13v58  49v67
14v23  59v68
15v78  24v69
16v79  34v25
17v26  89v35
18v45  27v36
19v46  28v37
29v47  38v65
That is optimal for player one (and player 4). But, for example, player 2 plays opposite player 3 four times and never plays opposite 8. It has perfect pairings but the oppositions are off a total of 24 times. I'm sure there's a better solution, and my method may not be the one that will find it.
Title: Re: new riddle: tennis competition
Post by Guest on Jan 29th, 2004, 11:06am
Note: Actually the solution I gave is off by 12 oppositions, not 24.
Title: Re: new riddle: tennis competition
Post by THUDandBLUNDER on Jan 29th, 2004, 11:46am

Quote:
I think Thudandblunder wasn't taking into consideration that one player sits out.

Yes, I was.

v = 9 is much harder than v = 5 because we have 2 matches going on simultaneously,
thus drastically reducing our options. I still believe it's impossible.
Title: Re: new riddle: tennis competition
Post by SWF on Jan 29th, 2004, 5:10pm
1-2  3-4         5-6  7-8     9
1-9  5-7         2-4  6-8     3
3-8  6-9         2-5  4-7     1
4-8  3-7         2-9  1-6     5
2-3  7-9         4-6  1-5     8
1-3  5-8         6-7  4-9     2
3-6  1-7         5-9  2-8     4
3-9  4-5         2-7  1-8     6
2-6  3-5         1-4  8-9     7
Title: Re: tennis competition
Post by THUDandBLUNDER on Jan 29th, 2004, 6:33pm
Hmm...may the force be with you, SWF.  ;)
Title: Re: tennis competition
Post by gert1 on Jan 31st, 2004, 7:24am
That is great SWF.
How about 13 and 17 players, is there a general method to find these schedules?
Title: Re: tennis competition
Post by why_linux_BSD_rule on Jan 31st, 2004, 8:18am
C(9,2) = 36
which means 36 unique combinations can be found.
i.e. if players are from A,B,C.........I then
A,B and B,A will both not be included here.

Two such courts would make it 4 teams playing with one spare (to collect balls :-))
thus each round you will get rid of 4 combinations. Thus you need 9 rounds (because 9X4=36)
to exhaust all combinations.

Try the same case for the 13, 17 ......... (maybe you have to increase the court number to get it in a desired number of times)
I HOPE I am on the right track.
Title: Re: tennis competition
Post by THUDandBLUNDER on Jan 31st, 2004, 6:56pm
I think this is what you are looking for:

http://www.jdawiseman.com/papers/tournaments/individual-pairs/individual-pairs.html
Title: Re: tennis competition
Post by gert1 on Feb 2nd, 2004, 12:45am
thanks, this site is exactly what I'm looking for.
May the force be with you too ::)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board