The following "Elevator puzzle" is taken from "The Tokyo Puzzles" by Kojon Fujimura, first published in Japanese in 1969 and subsequently translated into English (Fujimura, 1979).
Figure 1 represents an eightstorey building with three elevators. The shaded cells represent those floors at which a particular elevator calls. Notice that all elevators call at both top and bottom floors and four floors in between. It is possible, given this configuration, to travel between any two floors by riding a single elevator. The question is, if each lift called at three floors in between top and bottom, how many lifts would be required such that any two floors are connected by a single elevator?
Figure 1. Eightstorey building with three elevators, calling at the shaded floors.
OR/MS practitioners will recognize this puzzle as a setcovering problem (Wolsey, 1998). Briefly, a setcovering problem is a binary integer program where the objective function coefficients and righthandsides all have the value 1, all the constraints are of the "greater than or equal to" type and the lefthandside matrix consists exclusively of 1's and 0's.
Given the condition that all lifts must call at the top and bottom floors we may ignore these for the purposes of formulation. We will use the notation E{n, r} to represent an elevator problem with n floors, excluding top and bottom, where each elevator visits r floors in between top and bottom. We then define a matrix C with m rows (where m = _{n}C_{r}) and n columns and each row consists of a particular combination of r floors visited, specifically, c_{i,j} = 1 if the combination i involves a visit to floor j. C contains a complete list of the combinations of r visits. Finally, we define sets M = {1, ..., m} and N = {1, ..., n} and binary decision variables x_{i} = 1 if combination i is adopted.
We wish to minimize the number of elevators (combinations) required subject to the condition that there is an elevator available for each pair of floors. This may be achieved as follows.
An OPL model of this formulation is here and a dataset to solve the problem for six floors and three visits per elevator is here. The solution generated, with top and bottom floors added back, is shown in Figure 2.
Figure 2. Solution for E{6, 3}. An Excel spreadsheet with Solver instructions for this puzzle instance is here.
A brief discussion of this type of puzzle is given by Martin Gardner (1973) and he asks for a solution for ten floors (including top and bottom) with elevators each calling at four floors in between. The dataset for the original problem was created manually but for this larger problem it is more convenient to write a function to automate the process of listing all possible combinations of floors. This is left as a programming exercise for the interested reader.
A dataset to solve Gardner's problem is here and a solution is shown in Figure 3.
Figure 3. Solution for E{8, 4}.
Fujimura, K. (1979), The Tokyo Puzzles, Frederick Muller Limited, London
Gardner, M. (1973), "Elevator Puzzles," Scientific American Vol. 228, No. 2, pp. 106109
Wolsey, L.A. (1998), Integer Programming, John Wiley and Sons

To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here. 

To
reference this paper, please use:
Chlond, M. J. (2006), "A Tokyo Elevator Puzzle," INFORMS Transactions on Education, Vol. 6, No 3,
http://ite.pubs.informs.org/Vol6No3/Chlond/

