Crazy Man in the Waiting Room (Puzzle 2)

Points : 8

A crazy man enters the waiting room where there are 25 fans. There are 25 switches outside the room one each for a single fan. The switch board is faulty because when any open switch is closed; all other open switches also get closed instantly.

There are no speed regulators available with the fans. However, the fans do take appreciable time to attain maximum speed when switched on and the same time when switched off. All the fans are equivalent.

What is the minimum number of visits to the waiting room to figure out the correct matching?

In each visit, the man is allowed to be in the room for a very short time so that he can just view the states of all the fans and can not stay any longer.

Assume that the switches to be opened are hit at the same time. Heating effects are not to be considered.

Can you generalize the result for n fans and n switches?

Solution

Before solving this problem for 25 switches let us make a strategy based on the given conditions to identify x switches corresponding to x fans that can be detected in 1 pass through the door. Under the given conditions during one pass we can identify only three sets of fans.

One’s that are in the On State i.e in the continuously moving state.

One’s that are in the Off State i.e those that are not moving at all.

One’s that are moving but slowing down continuously.

The criteria for only these three states is based on the fact that these three states can be easily identified by the naked eye.

Other factors like taking the variable speed’s of the fan into account is not possible since we do not have any instrument to measure the speed of fans and if we take into account the variation in speed of the fans then how to identify that how many no of fans can be identified using this criteria?

So due to this fact we take only three states of the fans.

Now we can identify three states of these fans by initially turning on some switches, then closing them, turning another set of switches and then moving inside the room will let us identify these three set of fans so the problem can now be solved using Divide and Conquer approach.

Let T(n) = Number of times one has to enter into room to look at the bulbs.

T(n) = T(n/3) + 1

(Since we reduced the problem of size n into three sub-problems of size n/3 which will be solved in parallel and it took us one visit to do so)

= {T(n/9) + 1} + 1 = T(n/9) + 2

= T(n/27) + 3

and so on

= T(n/3(x-1)) + (x-1)

where  x= log3 n and T(3) = 1(i.e we can solve a problem of three in just one pass).

T(n) = T(3) + (x-1)

= 1 + (x-1)

= x

= LIF(log₃ n). (Where n is the total number of switches).

Where LIF denotes Least Integer Function.
Hence the total no of visits for n=25 is 3.

Points Distribution

• 3 points for finding the minimum number of visits for n=25 and providing its explanation
• 5 points for generalizing the result and proving the derived formula

For any query post your question below.