Welcome to WHIZZKIDS '97

On this website you will find information about the Whizzkids '97 Contest. This mathematics challenge has been sponsored by CMG (consultants in information technology) and was published by De Telegraaf (a Dutch newspaper) on September 6, 1997. Deadline for solutions was October 21, and the Awards Ceremony took place on November 27 in Amsterdam. The problem to be solved has been designed by Jan Karel Lenstra (EUT/CWI), Emile Aarts (EUT/Philips Research) and co-workers.

Competition was open for everybody, and there was a special category for professionals (i.e., those who are involved in mathematics and computing science research and teaching).

The problem

An English description of the problem and some explanation of the rules is available on our Eindhoven website. A complete Dutch description was available, at the time of publication of the puzzle, at CMG. The problem is to organize a meeting between parents and teachers, where the length of the conversations is given, and where the order of the conversations per parent is almost fixed. The problem contains features of a flowshop, but it is more general. A description of the parents' requests is given in following table. A numerical description is obtained from the numerical requests file.

Solutions

We received 343 submissions. In some of these some mistakes were made like overlapping interviews, or solutions not satisfying the requested order. The contest has been won by Paul Hoogendijk, a professional who recently obtained his PhD in Computing Science at our Department. He found a schedule with a length of 469 minutes and a total time of 5241 minutes. Gantt charts displaying the conversations are given in the following table.


Parents agenda	Teachers agenda

A numerical description of Pauls solution is given in file with the best solution found. Note that this is not necessarily the optimum solution. As far as the first criterion is concerned, however, we can prove a lower bound of 469. The proof involves a branch-and-bound search over all potential schedules of length 468. In this search 19509 nodes are evaluated, and the computations take approximately 65 hours on a Pentium II, 266 MHz. The ranking of the top contributors can be found the ranking list. Actually the professionals did do better than in 1996. Of course students can spend much more time on the real-life instances of combinatorial problems...

We hope that everyone has enjoyed this puzzle and look forward to a next one.

This page was modified last on: December 23, 1997,
by Cor Hurkens (wscor@win.tue.nl)