Description of the 1997 problem, with pointers.
A KID GOES TO SCHOOL ...
A WHIZZKID SENDS HIS PARENTS AND WINS Dfl.5,000.-
School is open tonight. The teachers don't talk to the students but to their parents. The students are eagerly waiting for their parents to come back home. But nobody knows at what time they will return, because the parents are wandering along the corridors and the teachers are impatiently waiting for the next parents to see. Who is responsible for the timetable? Well, you are!
WHAT SHOULD YOU DO?
You must construct a timetable for the parents' evening. There are two groups
of people: 20 parents and 15 teachers. A total of 197 conversations has to be
scheduled. A teacher can see only one parent at a time, and a parent can see
only one teacher at a time. The parents' evening starts at 16:00 hours and must
be completed as early as possible. The 15 teachers are denoted by A, B, C, D,
E, F, G, H, J, K, L, M, N, P, and R. The parents are denoted by numbers ranging
from 1 up to 20.
Parents have expressed their conversation requests by means of capital-number
codes. D15 indicates a request for a conversation with teacher D
that lasts 15 minutes. The requests are given by sequences. The sequence
(D15)(A6) denotes that the parent first wants to see teacher D
for 15 minutes, and next teacher A for 6 minutes. A
sequence of character-number combinations in between brackets denotes that the
sequence in which the conversations take place doesn't matter. Thus,
(D15,A6) denotes that teacher D can be visited either before or
after A. A listing of the conversation requests is given in the
attached
local gif file
and also in
our local numerical data file (text-file).
You don't have to take the time needed to go from one teacher to the other into
account; so the conversations can follow each other directly in time.
YOUR SOLUTION
The timetable you need to construct must indicate for each parent the sequence of teachers that he is going to see during the evening, together with the starting times of the conversations. The solution should fit in the solution form. An alternative timetable, indicating for each teacher the sequence of parents, together with the starting times, is also accepted.
Mrs. Hosman for example has issued the following request: (D15)(A6,B8,G10). Then the sequence D16:30, B16:45, G17:20, A17:30 indicates that she will see teacher D at 16:30, teacher B at 16:45, teacher G at 17:20, and finally teacher A at 17:30. She can go home at 17:36.
Your solution should be a timetable that meets all the parents' conversation requests and has minimum length. The parents' evening starts at 16:00 and ends when the last parent can go home. You should indicate this point in time on the form. You also should try to minimize the run time of the parents.
The jury collects all submitted solutions. It first checks the correctness of a solution. Next the correct solutions are ordered with respect to their lengths. If solutions have equal lengths, the total run time of the parents is taken into account. This is the sum of the run times of the individual parents, where the run time of a parent is the length of the period from the moment he starts his first conversation until he can go home.
WHAT ARE THE PRIZES?
CMG has donated a number of considerable cash prizes. The general category has ten prizes: Dfl. 5,000.-, Dfl. 4,000.-, Dfl. 3,000.-, and Dfl. 2,000.-, and six prizes of Dfl. 1,000.-. There are three additional prizes for the best high school student, the best high school class, and the best university student, respectively. Students that submit as member of their class are not allowed to submit individually. There is a category for professionals (those who are professionally involved in mathematics or computer science) with three prizes: Dfl. 5,000.-, Dfl. 2,500.-, and Dfl. 1,000.-. Participation is subject to rules described (in Dutch) in the game regulations. In particular they say that solutions resulting from a joint effort may be submitted, but only under the condition that they be marked as such, and contain the names of those involved.
Submissions should arrive before October 21, 1997, at
Lubbers en Dijk Notarissen P.O. Box 53040 1007 RA Amsterdam The Netherlandsmentioning "WHIZZKIDS97"
The jury consists of Profs. Emile Aarts and Jan Karel Lenstra of the Eindhoven University of Technology. The winners will be announced on November 27, 1997, at a ceremony in the newMetropolis science and technology center in Amsterdam.
GOOD LUCK
Brochures and info at:
CMG Nederland B.V. Department for Communication P.O. Box 159 1180 AD Amstelveen The Netherlands + 3120 50 33 000
This page was modified last on: December 23, 1997, by Cor Hurkens (wscor@win.tue.nl)