| |
|
|
HOMEPAGE van WHIZZKIDS 1997
Op deze website wordt informatie gegeven over de Whizzkids wedstrijd.
Deze wedstrijd wordt gesponsord door
CMG en gepubliceerd in de Telegraaf.
De te kraken problemen zijn ontworpen door professor Jan Karel Lenstra (TUE/CWI)
en professor Emile Aarts (TUE/Philips Research) en hun medewerkers.
De Whizzkids 1996 puzzel was een groot succes en trok velen met een interesse
in het kraken van lastige problemen. Meer dan 900 deelnemers deden hun best
een verdeel en routeerschema te bedenken voor 4 krantenjongens die samen 120
kranten moesten bezorgen in Manhattan. Fikse geldprijzen werden uitgereikt op
een ceremonie die plaats had in Amsterdam, op 29 november, 1996. Daarom werd er
ook weer in 1997 een Whizzkids puzzel verzonnen.
Deelname was open voor iedereen: scholieren, studenten en ieder ander handige
puzzelaar. Ook voor professionals was er mogelijkheid tot deelname. Nota bene:
In 1996 werden de professionals verslagen door de Eindhovense studenten!!
De Whizzkids 1997 editie werd bekendgemaakt in de Telegraaf van zaterdag 6
september, 1997. Sluitingsdatum voor inzendingen was 21 oktober, 1997, en de
feestelijk prijsuitreiking vond plaats op donderdag 27 november, 1997, in het
NewMetropolis Centrum voor Technologie in Amsterdam. Op deze website is een Engelse versie weergegeven voor deelnemers die de
Nederlandse beschrijving niet kunnen lezen. Een volledige, Nederlandstalige
website was te vinden bij CMG. Hier werden
reglement, probleembeschrijving, en
antwoordformulieren beschikbaar gesteld.
We hebben 343 oplossingen ontvangen. Kennelijk was deze opgave een stuk moeilijker dan
die van vorig jaar. In enkele inzendingen werden fouten gemaakt zoals het laten
overlappen van gesprekken (helaas, een ouder kan niet op twee plaatsen tegelijk zijn,
en datzelfde geldt voor een leraar), of het niet eerbiedingen van de volgorde eis van
de ouders.
De wedstrijd is gewonnen door
Paul Hoogendijk, een professional uit Eindhoven (gepromoveerd in de Informatica).
Zijn oplossing is een rooster met een lengte van 469 minuten. De ouderavond, die om
16.00 uur begon, eindigt daarmee om 23.49. De totale verblijftijd voor de
ouders in zijn oplossing bedroeg 5241 minuten.
Paul's oplossing is visueel weergegeven in de volgende zogenaamde Gantt charts.
We hopen dat iedereen veel plezier aan de puzzel heeft gehad en zien uit naar volgend
jaar..
Het probleem
Het probleem in het kort: organiseer een ouderavond waarop ouders met leraren kunnen
overleggen over het wel en wee van de leerlingen. Elke ouder heeft een verlanglijstje
ingediend met daarop de namen van de leraren die hij/zij wil spreken, de lengte van
het gesprek, en een gedeeltelijk vastgelegde volgorde. De eisen van de ouders zijn
vastgelegd in onderstaande tabel. In een bijgevoegd tekstbestand is een
numerieke beschrijving van de instantie gegeven.
Oplossingen
Een numerieke beschrijving, met starttijden, is te vinden in tekst met de beste oplossing. Merk op dat dit
niet betekent dat het ook de gegarandeerd beste oplossing is! We
kunnen wel laten zien dat een oplossing met een rooster korter dan 469 niet
bestaat. Het bewijs bestaat uit een branch-and-bound procedure die impliciet alle
potentiele roosters met een lengte van 468 aftelt. Hierbij worden 19509 knopen
geevalueerd en het rekenwerk duurt zo'n 65 uur op een Pentium II, 266 MHz.
De winnaars staan vermeld in
ranglijst. Dit jaar hebben de professionals
de studenten net weten te verslaan.
Rooster voor ouders
Rooster voor leraren
This page was modified on: December 23, 1997, by Cor Hurkens (wscor@win.tue.nl)
