Problem #114

In a certain building the square rooms are arranged in a rectangular m×n array. Each room has exactly three doors leading to other rooms. Note that there may be more than one door between two rooms and we will ignore any doors leading to the outside. Two examples of such configurations are shown below for a 3×4 array.

• How many ways can we place the doors in a 2×n array so that one can go from any room to any other room? For example, this is possible for the configuration on the left, but not for the one on the right.

• What about a 3×n array?

The solution will be posted shortly.

Back to the Advanced Problem Archives