“
The painter was allowed to exit the room and reenter it at another door.”
I maybe a hick from the sticks and a stranger to fair play and compassion…
But in this instance; I agree the wording is ambiguous – and if it constrained your answer then consider it changed from (another) to ‘any’ door.
Your answer working with the options as you saw them is correct.
Light switches:
Mark pushes the right buttons.
The puzzle can be solved by the following recursive algorithm for pushing the buttons numbered from 1 to n. If n = 1 and the light is off, push button 1. If n > 1 and the light is off, apply the algorithm recursively to the first n − 1 buttons.
If this fails to turn the light on, push button n and, if the light is still off, apply the algorithm to the first n − 1 buttons again.
The recurrence for the number of button pushes in the worst case is M(n) = 2M(n − 1) + 1 for n > 1, M(1) = 1, whose solution is M(n) = 2n − 1.
Alternatively, since a switch can be in one of the two states, it can be thought of as a bit in an n-bit string in which 0 and 1 represent, say, the initial and opposite states of the switch, respectively.
The total number of such bit strings (switch configurations) is equal to 2n; one of them represents an initial state, the remaining 2n − 1 bit strings contain the one that will turn on the light bulb. In the worst case, all these 2n − 1 switch combinations will have to be checked.
To accomplish this with the minimum number of button pushes, every push must produce a new switch combination.
There are several algorithms that start with a bit string of n zeros and generate all the other 2n −1 bit strings by changing just a single bit at a time.
The most well-known of them is the so-called binary reflected Gray code, which can be constructed as follows. If n = 1, return the list 0, 1. If n > 1, generate recursively the list of bit strings of size n − 1 and make a copy of this list; then add 0 in front of each bit string in the first list and add 1 in front of each bit string in the second list; finally, append the second list in reversed order to the first list.
For example, the algorithm generates the following bit string sequence for n = 4:
0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000
To return to the puzzle, we can number the switches from 1 to n right to left and use the sequence of the Gray’s code bit strings for guidance about which buttons to push: if the next bit string differs from its immediate predecessor in the ith bit from the right, we push button number i. For example, for four switches, it will guide us to push the buttons in the following sequence:
121312141213121.
The first solution is based on the decrease-by-one strategy. The second solution takes advantage of two strategies: representation change (to represent switches and their buttons by bit strings) and decrease-by-one (to generate the Gray code).
The puzzle was proposed and solved by J. Rosenbaum in 1938 [Ros38] by the method described above—years before the U.S. patents were granted for the Gray code invention.
M. Gardner mentioned this puzzle in his article about Gray codes [Gar86, p. 21]; the article also included applications to two better-known Lois Gros who should be considered a true inventor of this code in view of Gros’1872 book on the Chinese Rings [Knu11, pp. 284–285].
Can you link all the dots with six lines?
Given an n×n point lattice (intersection points of n consecutive horizontal and n consecutive vertical lines on common graph paper), where n > 2, cross out all the points by 2n − 2 straight lines without lifting your pen from the paper.
You may cross the same point more than once, but you cannot redraw any portion of the same line.
(A ‘greedy’ solution for n = 4, shown in Figure 1, has seven lines instead of the six required by the A2K schools Superintendent.)
FIGURE 1. Crossing 16 points by 7 lines.
