Puzzle: Locker box and padlocks

Problem: Boris and Natasha live in different cities in a country with a corrupt postal service. Every box sent by mail is opened by the postal service, the contents stolen, and the box never delivered. Except: if the box is locked, then the postal service won't bother trying to open it (since there are so many other boxes whose contents are so much easier to steal) and the box is delivered unharmed.

Boris and Natasha each has a large supply of boxes of different sizes, each capable of being locked by padlocks. Also, Boris and Natasha each has a large supply of padlocks with matching keys. The padlocks have unique keys. Finally, Boris has a ring that he would like to send to Natasha. How can Boris send the ring to Natasha so that she can wear it (without either of them destroying any locks or boxes)?

Solution: They follow the following sequence of steps:
(1) Boris sends a locked box containing the ring to Natasha
(2) Natasha locks this box with her own padlock and sends it back to Boris
(3) Boris removes his padlock and then sends back the box to Natasha
(4) Natasha unlocks her padlock and gets her hands on the Ring

Puzzle: Table with four coins

Problem: A square table has a coin at each corner. Design an execution sequence, each of whose steps consists of one of the following operations:

* ONE (O): The operation chooses a coin (possibly a different one with each execution of the operation) and flips it.
* SIDE (S): The operation chooses a side of the table and flips the two coins along that side.
* DIAG (D): The operation chooses a diagonal of the table and flips the two coins along that diagonal.

such that at some point during the execution (not necessarily at the end), a state where all coins are turned the same way (all heads or all tails) obtains.

Solution:
There are 3 types of configuration possible:
(a) all coins have same face up
(b) 3 coins have same face up (and 1 has the other face up)
(c) 2 coins have same face up (and other 2 have the other face up)

Config (a) is the desired final position. Configs (b) and (c) are potentially one step away from the final position F (where all coins have same side facing up). However, is there a config such that we can choose one of O, S or D and then we are guaranteed to reach the final desired position F ? Yes, there is. A special case of config (c) where the diagonally opposite coins have same face up is such a penultimate position:
H T     T H
T H  or  H T
Applying the D operation here will definitely result in F.

Perhaps our goal then should be to reach this position F' from other positions.

If two coins along a side have same face up, then F can be reached through F' by the following sequence: S, D.
Therefore, F can be reached from config (c) by the following sequence: D, S, D.

If a single coin is face up, then we have the following sequence towards F: O, D, S, D.

Applying this sequence to config (b) will definitely lead to F. Applying this sequence to config (c) however might result in config (b). Therefore this sequence must be repeated:
O, D, S, D, O, D, S, D.

This is the desired sequence of operations which will guarantee that the final position F is reached at some time during its execution.

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

Problem: Number Partitioning

Had a go to derive a formula for the number of partitions of a number. Initially, tried to compare it with the 'pirates and gold bars' problem and see if I could derive some formula based on similar reasoning. After this failed attempt, decided to come up with a recursive formula.

Suppose you order the partitions by increasing size, and within a partition order the elements in weakly increasing order. For example, you write the partitions of 4 as:
4
1 3
2 2
1 1 2
1 1 1 1

Now, consider a way of generating all the partitions of a given size k. Suppose these partitions are to be arranged lexicographically. Then, the first partition consists of (k-1) 1s followed by the number n-(k-1). For example, the first 4-sized partition of 8 would be:
1 1 1 5

The next partition is generated by taking 1 away from the rightmost element (rightmost_elem) and adding it to the previous element. This process should be continued upto the point where the elements within the partition cannot be arranged in weakly increasing order. So, we have:
1 1 1 5
1 1 2 4
1 1 3 3
(cant go for 1 1 4 2)

For each of the partitions generated above, partitions for the (k-1) leftmost elements can be generated keeping the rightmost element constant. Hence, this can be viewed as a recursive process of generating sub-partitions for the number (n - rightmost_elem), each of size (k-1). Also, while generating these sub-partitions, the maximum value of any element should not exceed the value of the rightmost_elem.

This idea of recursive sub-partitions is captured by the following recurrence equation:
And the following equation generates all partitions of a number:
We also need to take care of the end conditions properly. If k ==1, only 1 partition is possible and when n==k, only 1 partition is possible i.e. T(n,1,max) = 1 and T(n,n,max) = 1.

Problem: Pirates and gold bars

Problem: There are 13 indivisible, identical gold bars that are to be divided among 5 pirates. In how many ways can this be done ?

[ The reason I attempted this problem was because of two things involved in it: pirates and gold.]

Solution: Suppose you have 4 knives that you can place at any position in between the gold bars and the number of gold bars pirate i gets is the number of gold bars between knife i-1 and knife i where knife 0 and knife 5 are imaginary knives.

The problem may now be visualized as permuting the 13+4 elements out of which 13 are alike and 4 are alike.

Number of ways = fact(17) / (fact(13) * fact(4)) = 17C4

Generalization: The number of ways in which n gold bars may be divided among m pirates is (n+m-1)C(m-1) = (n+m-1)Cn

Path towards the solution: The problem may be viewed as placing (m-1) dividers so as to get m parts from the array of gold bars. Each of the (m-1) dividers may be placed at any of the (n+1) positions. Therefore, the solution could be (n+1)^(m-1). However, the dividers themselves are not distinct and we are counting a particular division more than once. In other words, the divisors are all alike. Hence, now we have to consider the sequence of gold bars interspersed with divisors of length (n+m-1) out of which n are alike and (m-1) are alike.

Similar problems:

(1) The number of positive integer solutions to x1 + x2 + ... + xk = n where x1,x2,...,xk >= 0.

[Here, the total number of gold bars is n and pirate i is given the number of gold bars equal to xi.]

p->next:

(1) Number partitioning and Partition functions

(2) Young diagrams

Program: Permutations and combinations

After a long hiatus from writing mind-numbing and skull-cracking(i.e. meaningless and inefficient) programs which used to be my hallmark, I have decided to reestablish myself. And this time, the target is the field of combinatorics. Yes, this time I have decided to attack and desecrate an entire field with my thoughts and observations rather than restrict myself to individual problems.

As a part of this massacre, I had a go at writing a couple of programs to generate permutations and combinations. I proudly present thee these programs:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 * In order to generate permutations of a string, say, abcde,
 * pluck 'a' and then generate all permutations of bcde,
 * pluck 'b' and generate all permutations of acde,
 * pluck 'c' and generate all permutations of abde,
 * and so on.
 */

void rotate_left(char *a)
{
  int i, n = strlen(a);
  char temp = a[0];
  for(i=0;i<n-1;i++)
      a[i] = a[i+1];
  a[i] = temp;
}

int gen_perms(char *prestr, char *str)
{
  static int nperms = 0;
  int i, n, np;
  char *tempstr, *newprestr;

  n = strlen(str);
  np = strlen(prestr);

  if(n==1) {
      printf(prestr);
      printf(str);
      printf("\n");
      nperms++;
      return nperms;
  }

  tempstr = (char*)malloc(n*sizeof(char));
  newprestr = (char*)malloc((np+2)*sizeof(char));

  for(i=0;i<n;i++) {
      strcpy(tempstr, str+1);

      strcpy(newprestr, prestr);
      newprestr[np]=str[0];
      newprestr[np+1]='\0';

      gen_perms(newprestr, tempstr);
      rotate_left(str);
  }
  free(newprestr);
  free(tempstr);

  return nperms;
}

void generate_perms(char *a)
{
  int nperms = gen_perms("", a);
  printf("\nTotal number of permutations: %d\n", nperms);
}

int main(int argc, char *argv[])
{
  int i,n;
  char *a;

  if(argc!=2) {
      printf("\nUsage: generate_perms <numelems>\n");
      return 1;
  }
  sscanf(argv[1], "%d", &n);

  if(n<0) {
      printf("\nInvalid input\n");
      return 1;
  }

  a = (char*)malloc((n+1)*sizeof(char));
  for(i=0;i<n;i++)
      a[i]='a'+i;
  a[n]='\0';

  generate_perms(a);

  free(a);
  return 0;
}

- - - - - -

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 * In order to generate, say 3 letter combinations of string abcde,
 * pluck 'a' and then generate all 2 letter combinations of bcde,
 * discard 'a', then pluck 'b' and generate all 2 letter combinations of cde,
 * discard 'b', then pluck 'c' and generate all 2 letter combinations of de,
 * and so on.
 */

int gen_combs(char *prestr, char *str, int nc)
{
static int ncombs = 0;
int i, j, n, np;
char *newprestr;

n = strlen(str);
np = strlen(prestr);

if(nc==1) {
  for(i=0;i<n;i++) {
    printf(prestr);
    printf("%c\n",str[i]);
    ncombs++;
  }
  return ncombs;
}

newprestr = (char*)malloc((np+2)*sizeof(char));
strcpy(newprestr, prestr);

for(i=0;i<n;i++) {
  newprestr[np]=str[i];
  newprestr[np+1]='\0';

  gen_combs(newprestr, str+i+1, nc-1);
}
free(newprestr);

return ncombs;
}

void generate_combs(char *a, int nc)
{
int ncombs = gen_combs("", a, nc);
printf("\nTotal number of combinations: %d\n", ncombs);
}

int main(int argc, char *argv[])
{
int i,n,r;
char *a;

if(argc!=3) {
  printf("\nUsage: generate_combs <c> <r>\n");
  return 1;
}
sscanf(argv[1], "%d", &n);
sscanf(argv[2], "%d", &r);

if(n<0 || r<0 || n<r) {
  printf("\nInvalid input\n");
  return 1;
}

a = (char*)malloc((n+1)*sizeof(char));
for(i=0;i<n;i++)
  a[i]='a'+i;
a[n]='\0';

generate_combs(a, r);

free(a);
return 0;
}