Proposed by Toby Walsh
The problem is to timetable a party at a yacht club. Certain boats are to be designated hosts, and the crews of the remaining boats in turn visit the host boats for several successive half-hour periods. The crew of a host boat remains on board to act as hosts while the crew of a guest boat together visits several hosts. Every boat can only hold a limited number of people at a time (its capacity) and crew sizes are different. The total number of people aboard a boat, including the host crew and guest crews, must not exceed the capacity. A table with boat capacities and crew sizes can be found below; there were six time periods. A guest boat cannot not revisit a host and guest crews cannot meet more than once. The problem facing the rally organizer is that of minimizing the number of host boats.
boat number | capacity | crew size |
---|---|---|
1 | 6 | 2 |
2 | 8 | 2 |
3 | 12 | 2 |
4 | 12 | 2 |
5 | 12 | 4 |
6 | 12 | 4 |
7 | 12 | 4 |
8 | 10 | 1 |
9 | 10 | 2 |
10 | 10 | 2 |
11 | 10 | 2 |
12 | 10 | 3 |
13 | 8 | 4 |
14 | 8 | 2 |
15 | 8 | 3 |
16 | 12 | 6 |
17 | 8 | 2 |
18 | 8 | 2 |
19 | 8 | 4 |
20 | 8 | 2 |
21 | 8 | 4 |
22 | 8 | 5 |
23 | 7 | 4 |
24 | 7 | 4 |
25 | 7 | 2 |
26 | 7 | 2 |
27 | 7 | 4 |
28 | 7 | 5 |
29 | 6 | 2 |
30 | 6 | 4 |
31 | 6 | 2 |
32 | 6 | 2 |
33 | 6 | 2 |
34 | 6 | 2 |
35 | 6 | 2 |
36 | 6 | 2 |
37 | 6 | 4 |
38 | 6 | 5 |
39 | 9 | 7 |
40 | 0 | 2 |
41 | 0 | 3 |
42 | 0 | 4 |