Puzzle: Lockers

Problem: In a school common room there are 100 locker boxes. At tiffin, 100 students line up outside the common room. One by one, they come in. The 1st student opens every locker box. The 2nd student closes every even locker box. The 3rd student changes the state (opens if closed, closes if open) of every 3rd locker box. And so on. The nth student changes the state of every nth locker box.

After the 100 students have done their job, which are the locker boxes that remain open?

Solution: Consider locker numbers 3,4,6 as examples. Locker 3 is opened by 1st student and closed by the 3rd student and remains closed. Locker 4 is opened by 1st student, closed by 2nd student and reopened by 4th student. Locker 6 is opened by 1st student, closed by 2nd student, reopened by 3rd student and closed by the 6th student. So, out of these three, locker 4 remains open.

A locker number n will be accessed by all those students with number i where i is a factor of n. Consider only distinct pairs of factors of n i.e. only one pair out of (n1,n2) and (n2,n1). Therefore, for all such factor pairs (n1,n2) of n, one of them will open the locker and the other will close the locker. However, if n1==n2, then locker will remain in the open state. In other words, for all numbers n which are squares, the corresponding locker will remain open.

In this particular case with 100 lockers, only the lockers with numbers which are squares will remain open i.e. 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Puzzle: Ends of the Noodles

Problem: There is this weird man who goes to a noodle shop and orders noodle soup. He asks for exactly 100 noodles in his soup.

Once his noodle-soup arrives, he gets to work. He extracts two noodle ends from under the soup, ties a knot, and lets it slip into the soup again. He does the above 100 times - so that now all the noodle ends are tied.

Now he reaches his hand into the soup. What is the probability that he would extract a garland containing all the 100 noodles?

Solution: I attacked this problem from various directions because I was not sure of the direction. This led to a lot of confusion and more thoughts until the number of thoughts were growing combinatorically at a prohibitive rate. I finally landed upon the solution though and wore the garland.

I am initially presenting the other approaches and solutions. It is left to the reader (if any) to determine why each one is correct or incorrect. The correct solution is presented at the last.

Solution 1: This was the first one I came up with. Let us the consider the case of failure of formation of the garland. This might happen if he shorts a noodle at the first attempt, or if he shorts it at the second attempt, and so on. The probability that he shorts a noodle at the first attempt is given by 100/(200C2). This is because two noodle ends may be chosen in 200C2 ways and a noodle may be shorted in 100 ways (since there are 100 noodles). The probability that he shorts a noodle at the second attempt is 99/198C2, and so on. Therefore, the probability of failure is given by:

[formula being created using math symbols .. coming soon]

And, the probability of success is P = 1 - P'. For example, if there are 2 noodles, then the probability of success comes out to be 2/3, while for the case of 3 noodles, the probability of success comes out to be 7/15.

Solution 2: The process of selecting a noodle end may also be considered to be the process of selecting a noodle itself. In this case, when we select two noodle ends, we are selecting 2 noodles with repetition allowed. This is another way of looking at the problem. Consider the 2-noodle case where the noodles are named A and B. Then there are 3 possibilities for selecting two noodles - (A,A), (B,B) and (A,B). Only case is favorable to us and hence the probability of success is 1/3.

In the 3 noodle case, there will be 2 steps of noodle selection. For the first step, we 6 possibilities: (A,A), (B,B), (C,C), (A,B), (B,C), (A,C). After this, the second step is nothing but the 2-noodle case. Each of these cases will generate 3 more cases for a total of 18 cases. 9 of these are rejected. Further, for the (A,B), (B,C), (A,C), only one of the 3 cases generated for each is favorable. Hence, only 3 cases are favorable. The answer is therefore 3/18 = 1/6. However, this argument is getting complicated and as confusing as a lump of noodles.

Solution 3: In the above solution, observe that many cases are repeated. Consider the 3-noodle case. Starting from (A,A) we may reach the case where all 3 noodles are shorted. But this may also be reached from (B,B) and (C,C). Also, the noodles are really indistinguishable from one another. Perhaps, we should be considering only the configurations that we land up with at the end of the noodle-ends tying process.

In that case, for the 2-noodle case, only 2 configurations are possible:
1 1 (both noodles shorted)
2 (garland formed)

For the 3-noodle case, only 3 configurations are possible:
1 1 1 (all three noodles shorted)
1 2 (a garland of two noodles shorted and another single noodle shorted)
3 (garland formed)

These are nothing but the partitions of the number, and therefore the probability is then 1/p(100) where p(100) denotes the number of partitions of 100. In general, the probability is 1/p(n).

Correct Solution: This solution is actually a corrected version of Solution 1. What did we miss out in Solution 1 then ? We are considering the cases of failure. He may either fail at the first step by shorting a noodle or he may fail at the second step by shorting a noodle, and so on. More precisely, he may fail at step i if he shorts a noodle at step i and has not shorted any noodle in the previous (i-1) steps. We had missed out this "and part" in calculation of the probabilities !

Therefore, for the 3 noodle case, we have:
P' = 3/(6C2) + (1 - 3/(6C2))(2/4C2) = 1/5 + 4/5 * 1/3 = 1/5 + 4/15 = 7/15
and
P = 1 - P' = 1 - 7/15 = 8/15

Similarly, for the 100 noodle case.

[formula being created using math symbols - coming soon].

Enough of noodles. I am not going to eat them for a long time now. And even if I decide to do so, who knows ? I might end up trying to form a garland after all.

Puzzle: Bulb and switches

Puzzle: There is one bulb inside a room but three switches outside the room. Only one of these switches operates the bulb. There is no way to see the state of the bulb from outside the room.

You have to fiddle with the switches, enter the room once and only once, and have to be able to tell which switch operated the bulb. What will you do?

If you have answered the first question, extend the problem to four switches.

Solution: The first problem with 3 switches was already known to me. The idea is simple. Flick on one of the switches, say switch 1, for quite some time, say about half an hour. Flick it off and flick on a different switch, say switch 2. And then enter the room.

- If the bulb is glowing, switch 2 is the correct switch
- If bulb is not glowing, but is hot, then switch 1 is the correct switch
- If bulb is not glowing and is not hot, then switch 3 is the correct switch

We now have to extend this problem to four switches. The underlying idea is simple. Note that there are two parameters involved - state(on/off) of the switch, and temperature(hot/cold) of the switch. Together, they form 4 distinct combinations. Once this is realized, we have to now figure out a strategy such that each of these combinations points to a unique switch.

The strategy is as follows. First, turn on 2 switches for quite some time, say half an hour (say switch 1 and switch 2). Then, turn one of them off (switch 2) and turn a different switch on (switch 3). With abated breath, enter the room.

- If bulb is glowing and is hot, switch 1 is the correct switch
- If bulb is glowing but not hot, switch 3 is the correct switch
- If bulb is not glowing but is hot, switch 2 is the correct switch
- If bulb is not glowing and is not hot, switch 4 is the correct switch

Enough of flicking switches and examining bulbs now. Lets flick them all off and retire for a nice slumber.

Problem set: Handshakes

Problems::
(1) Determine the number of handshakes in a party of n people if every person shakes hands with every other person
(2) Prove that there are atleast two people with the same number of handshakes
(3) Prove that the number of persons with odd handshake count is even
(4) A couple hosts a party for three other couples, so there are a total of eight people at the party. When people arrive, they start shaking hands. Not everybody shakes everyone else's hand. In fact, nobody shakes hands with his or her partner, and nobody shakes his or her own hand. So, the most hands anyone could shake is 6, and, of course, the least might be zero. After all the hand shaking is over, the host asks the seven other people and finds that they have each shaken a different number of hands. How many hands did the host shake?

Solutions::
(1) Determine the number of handshakes in a party of n people if every person shakes hands with every other person
Solution: Two people for a handshake can be selected from n people in nC2 ways. The total number of handshakes is therefore nC2.

(2) Prove that there are atleast two people with the same number of handshakes
Proof: Suppose the handshake count of every person is different. Maximum handshake count possible is (n-1). Therefore, the distinct handshake counts have to be n-1, n-2, ..., 0 for the n persons. However, if (n-1) is the handshake count for a person, then he must have shaken hands with all other people and handshake count 0 cannot exist - a contradiction. Hence, there must be atleast two people with same handshake count.

(3) Prove that the number of persons with odd handshake count is even
Proof: To begin with, when no hands have been shaken, the total odd handshake count is 0 (even).
Case 1: If two people having odd handshake count shake hands, then both their handshake counts become even and the total odd handshake count has decreased by 2.
Case 2: If a person with odd handshake count shakes hands with a person having even handshake count, the former's handshake count becomes even and the latter's becomes odd. Hence, the total odd handshake count stays the same.
Case 3: If two persons having even handshake count shake hands, then the total odd handshake count increases by 2.

Therefore, the total handshake count either stays the same, or changes by 2. Also, it is even (0) to begin with. Hence, by induction, the number of persons with odd handshake count is even.

(4) Host handshakes problem
Solution: Let the other seven people be p0,p1,...,p6 where p0 has shaken 0 hands, p1 has shaken 1 hand and so on. Let x be the number of hands shaken by the host.

Then, we can go back in time according to the following state sequence:

(0,1,2,3,4,5,6) x
0,(0,1,2,3,4),0 x-1 (p0 and p6 are a couple)
0,0,(0,1,2),0,0 x-2 (p1 and p5 are a couple)
0,0,0,(0),0,0,0 x-3 (p2 and p4 are a couple)

p3 and the host are a couple and (x-3) must be equal to 0. Therefore, x=3.
Hence, the host shook 3 hands and so did his wife.

Problem set: Bipartite graphs

Problems::
(1) Give an algorithm that bipartises a graph G if possible, else returns failure
(2) P.T. a bipartite graph G with odd number of vertices is nonhamiltonian
(3) Give an algorithm to determine the hamiltonian path in a directed, acyclic graph

Solutions::
(1) Algorithm to bipartise a graph G: If the graph is bipartite, the algorithm divides the set of vertices V into two groups V1 and V2 such that all edges of G have one endpoint in V1 and another in V2. If not, the algorithm returns failure.

Initial conditions:
V1={}, V2={}
label(v) = 2, for all vertices v

Algorithm:
----------
add any vertex v from V to the queue Q
add v to V1
label(v) = 0

while(Q is not empty)
remove a vertex v from Q
for each vertex w adjacent to v
  if label(v) == label(w) /* v and w belong to the same vertex set */
      return failure
  else
      if label(w) == 2
      add w to the vertex set not containing v
      enqueue w in Q
      label(w) = 1 - label(v)
  endif
  endif
endfor
endwhile

return success

Running time of the algorithm is O(n^2) since it has to traverse all the edges of the graph.

(2) P.T. a bipartite graph G with odd number of vertices is nonhamiltonian:
Proof:
This is quite a simple proof.

Suppose n1 and n2 are the number of vertices in the two vertex sets V1 and V2 of the bipartite graph. Since, the number of vertices is odd, either n1 is greater than n2 or n1 is less than n2. Without loss of generality, suppose n1 > n2. Further suppose that the graph is such that there exists a path that starts from a vertex in V1 and alternately visits vertices from V1 and V2. Such a path will end at a vertex in V1 after having visited all vertices in V2. However, since n1>n2, one or both of the following may hold:
(a) the ending vertex is not the same as the start vertex, or,
(b) all vertices in V1 are not visited by the path.

Therefore, such a path that visits all vertices and is also a cycle cannot exist. Hence, a bipartite graph with odd number of vertices is nonhamiltonian.

Bipartite graph with even number of vertices: What happens if the graph has even number of vertices ? Suppose that this is the case and |n1|=|n2|. Also, further suppose that each vertex has even degree. In this case, is the graph necessarily hamiltonian ? The answer is no. This is because, at first glance it appears that either a hamiltonian cycle exists or there are disjoint cycles in the graph. This needs to be probed further.

(3) Give an algorithm to determine the hamiltonian path in a directed, acyclic graph
Algorithm: Initiate a DFS keeping a count of the number of vertices visited along the depth-first path so far. Also, label the current vertex with the current count. When this count becomes equal to the number of vertices of the graph, n, return success. On success, the vertices have been enumerated in an order that indicates their order along the Hamiltonian path. These can then be printed out in this order. Alternatively, an ordered list of vertices could be maintained. Also, if count never becomes equal to n, then return failure.

Further, a directed, acyclic graph will necessarily have at least 1 vertex with indegree 0 (this can also be proved). If the graph has 2 or more such vertices, then no hamiltonian path exists. If there is only 1 such vertex, then DFS may be initiated from such a vertex. This optimization can be used although it is not used in the algorithm outlined below.

Algorithm:
----------
label(start) = 1
label(v) = 0, for all other vertices v

hampath(start)
   status = find_hampath(start, 1)
   if status == true
           print_hampath(start, 1)
   endif
end hampath

find_hampath(vertex v, int count)
   label(v) = count
   if count==n
           print "hampath found"
           return true
   endif

   for each vertex w adjacent to v
           if label(w) == 0
                   flag = find_hampath(w, count+1)
                   if flag == true
                           return true
                   endif
           endif
   endfor
   return false
end find_hampath

print_hampath(vertex v, int count)
   print v
   for each vertex w adjacent to v
           if label(w) == count+1
                   print_hampath(w, count+1)
           endif
   endfor
end print_hampath