### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,314)
- misc (3)
- project euler (2)
- puzzle (78)
- puzzle# (21)
- site news (54)
- tantalizer (80)
- teaser (7)

### Site Stats

- 217,165 hits

Programming Enigma Puzzles

19 September 2018

Posted by on **From New Scientist #996, 15th April 1976** [link]

Uncle Tom’s bungalow is well endowed with doors, as you can see. He locks them each night, to keep out things that go bump. He would dearly love to do it by passing through each door just once and locking it behind him, so as to finish safely locked up in his bedroom. Alas, it cannot be done. Ah, but wait a minute. It could be done, if he had one of the doors bricked up. By Jove, that’s it.

Precisely which door would he be better without?

[tantalizer445]

%d bloggers like this:

See also:

Enigma 25,Enigma 108,Enigma 120,Enigma 1338.This Python 3 program runs in 284ms.

Run:[ @repl.it ]Solution:He would be better without door “C”.Labelling the rooms 1, 2, 3, 4, 5, 6 and “outside” 0 we can construct a graph with the rooms as nodes and the doors as edges.

A Eulerian path (a path that visits all the nodes using each edge once), can only exist if the start and end node have odd degree and the remaining nodes have even degree.

The nodes in our graph have degrees (= number of doors):

So we have too many nodes with odd degree. Removing an edge will reduce the degree of the connected nodes by 1, and we can only remove one edge. So we need to remove the edge from two nodes of odd degree that are connected together.

The only two nodes of odd degree that are connected together are 1 and 2. The door between rooms 1 and 2 is C. So eliminating door C gives us a graph where rooms 5 and 6 have odd degree and the remaining rooms have even degree, so we can make a path between room 5 and room 6 that passes through each of the remaining doors. So if one of these rooms is Tom’s bedroom he can start in the other one and finish in his bedroom with all the doors locked.

Here is a diagram of path between rooms 5 and 6 that passes through each door (except C) once.

It might be easier just to keep door C permanently locked, rather than brick it up.

Note that to lock all the doors he will have to leave and re-enter the house 3 times through different doors.