Volume 6, Number 3, May 2006
A Tokyo Elevator Puzzle
 
 
Martin J.Chlond
Lancashire Business School
University of Central Lancashire
Preston PR1 2HE
UK
 
 

1. Introduction

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 eight-storey 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. Eight-storey building with three elevators, calling at the shaded floors.

OR/MS practitioners will recognize this puzzle as a set-covering problem (Wolsey, 1998). Briefly, a set-covering problem is a binary integer program where the objective function coefficients and right-hand-sides all have the value 1, all the constraints are of the "greater than or equal to" type and the left-hand-side matrix consists exclusively of 1's and 0's.

2. Formulation

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 = nCr) and n columns and each row consists of a particular combination of r floors visited, specifically, ci,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 xi = 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}.

References

Fujimura, K. (1979), The Tokyo Puzzles, Frederick Muller Limited, London

Gardner, M. (1973), "Elevator Puzzles," Scientific American Vol. 228, No. 2, pp. 106-109

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/