|
|
 | | From: | Mats Carlsson | | Subject: | Social Golfer Problem "solved" | | Date: | 30 Dec 2004 08:44:10 -0800 |
|
|
 | Context: CSPLib problem #10, the Social Golfer Problem
http://www.csplib.org/
On the reference page, Warwick Harvey writes: "The ``challenge''
therefore is to find a 10-week solution, or prove none exists." Here's
my proof of non-existence.
- Let the golfers be numbered 1 thru 32.
- Without loss of generality, suppose the first week contains the
foursomes {1,2,3,4} and {5,6,7,8}.
- Weeks 2 thru 10 contain nine foursomes containing player 1 and a
total of 27 other players. These must be all distinct and drawn from
(5 thru 32); otherwise, some players would meet twice. At the same
time, the 27 players must contain at most one of {5,6,7,8} to
prevent these players from meeting twice. Since 26 distinct players
cannot be drawn from (9 thru 32), we have a contradiction.
Does anyone see any snags?
Season's greetings, --Mats
|
|
| | From: | Yan Georget | | Subject: | Re: Social Golfer Problem "solved" | | Date: | Thu, 30 Dec 2004 19:28:48 +0100 |
|
|
| > Does anyone see any snags?
Let us consider the foursomes containing player 1.
What about player 5 in week 2, player 6 in week 3, player 7 in week 4,
player 8 in week 5? Then, you have to find 23 different players in [9,32],
which is possible.
Yan
|
|
| | From: | Mats Carlsson | | Subject: | Re: Social Golfer Problem NOT solved | | Date: | 30 Dec 2004 10:27:58 -0800 |
|
|
| I retract what I just wrote. The proof is clearly flawed. The New
Year's Eve champagne must have gone to my head before I even drank it.
--Mats
|
|
| | From: | Andrew John Sadler | | Subject: | Re: Social Golfer Problem "solved" | | Date: | 06 Jan 2005 11:57:25 +0000 |
|
|
| "Mats Carlsson" writes:
> Context: CSPLib problem #10, the Social Golfer Problem
>
> http://www.csplib.org/
>
> On the reference page, Warwick Harvey writes: "The ``challenge''
> therefore is to find a 10-week solution, or prove none exists." Here's
> my proof of non-existence.
> Does anyone see any snags?
Apart from the fact that a solution has already been found :)
[[ 1, 2, 3, 4],[ 5, 6, 7, 8],[ 9,10,11,12],[13,14,15,16],[17,18,19,20],[21,22,23,24],[25,26,27,28],[29,30,31,32]]
[[ 1, 5,13,26],[ 2, 8, 9,31],[ 3, 7,10,30],[ 4,6,15,28],[11,20,21,29],[12,18,23,32],[14,19,24,27],[16,17,22,25]]
[[ 1, 6,11,32],[ 2, 7,14,25],[ 3, 8,16,27],[ 4, 5,12,29],[ 9,17,24,30],[10,19,22,31],[13,18,21,28],[15,20,23,26]]
[[ 1, 7,17,21],[ 2,11,13,24],[ 3, 6,18,22],[ 4,10,16,23],[ 5,20,25,30],[ 8,19,28,32],[ 9,14,26,29],[12,15,27,31]]
[[ 1, 8,18,24],[ 2,12,16,21],[ 3, 9,20,28],[ 4,11,17,27],[ 5,14,22,32],[ 6,19,26,30],[ 7,13,23,31],[10,15,25,29]]
[[ 1, 9,15,22],[ 2, 5,19,23],[ 3,12,17,26],[ 4, 8,13,25],[ 6,14,21,31],[ 7,18,27,29],[10,20,24,32],[11,16,28,30]]
[[ 1,10,14,28],[ 2, 6,20,27],[ 3,21,25,32],[ 4,24,26,31],[ 5, 9,16,18],[ 7,11,15,19],[ 8,17,23,29],[12,13,22,30]]
[[ 1,12,19,25],[ 2,10,18,26],[ 3,11,14,23],[ 4, 7,20,22],[ 5,17,28,31],[ 6,16,24,29],[ 8,15,21,30],[ 9,13,27,32]]
[[ 1,16,20,31],[ 2,15,17,32],[ 3,13,19,29],[ 4,14,18,30],[ 5,10,21,27],[ 6, 9,23,25],[ 7,12,24,28],[ 8,11,22,26]]
[[ 1,23,27,30],[ 2,22,28,29],[ 3, 5,15,24],[ 4, 9,19,21],[ 6,10,13,17],[ 7,16,26,32],[ 8,12,14,20],[11,18,25,31]]
It wasn't found by me I hasten to add, but by a pair of mathematicians
whose names I forget. Warwick Harvey will know the details if you need them.
Ho, hum. On to the next challenge.
|
|
|
