CTK Insights

In their textbook Discrete Algorithmic Mathematics authors Stephen Maurer and Anthony Ralston offer a light-hearted example [pp. 217-221]:

When checking into a hotel nowadays, sometimes a guest receives a four-digit "combination", not a key. On the door of each room is a keypad. Any time those four digits are entered in the proper sequence (regardless of what has been entered previously), the door opens. What is the minimum number of digits the burglar must use to be certain of entering the correct four-digit key in sequence?

Solution

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

When checking into a hotel nowadays, sometimes a guest receives a four-digit "combination", not a key. On the door of each room is a keypad. Any time those four digits are entered in the proper sequence (regardless of what has been entered previously), the door opens. What is the minimum number of digits the burglar must use to be certain of entering the correct four-digit key in sequence?

Solution

The burglar must choose a de Bruijn sequence and start punching the keys one after another. Any de Bruijn sequence of length four formed with 10 symbols is

4 + (4¹⁰ - 1) = 4¹⁰ + 3

digits long. (For, the total number of four-decimal-digit sequences is 4¹⁰.)

The burglar will probably do well to use a mechanical finger controlled by a computer program. Maurer and Ralston have conveniently considered a reduced problem of a hotel with 16 rooms. In such a hotel naive owners could use a binary keypad for the total of 16 four-digit combinations. The de Bruijn sequences in this case are all 19-digit long (4 + 4² - 1). The burglar may pick any.

Related posts:

1. First Applications of Helly's Theorem
2. Engaging math activities for the summer break - Day 17
3. A Combinatorial Gem: Sum Multisets