Linux: Boot linux faster

http://www.ibm.com/developerworks/linux/library/l-boot.html

- focuses on starting stand-alone services in parallel

http://blogs.techrepublic.com.com/10things/?p=387

- 10 tips to make your linux boot faster

Linux: /proc

Nice articles on /proc filesystem:

http://www.ibm.com/developerworks/linux/library/l-proc.html

http://www.linuxjournal.com/article/8381

Linux: kexec

Information about kexec to be found at:

http://en.wikipedia.org/wiki/Kexec

http://www.ibm.com/developerworks/linux/library/l-kexec.html

Puzzle: House Numbers

Presenting a simple but interesting puzzle.

Problem: You live on a street with N houses, where N is between 50 and 500. The houses are numbered consecutively from 1 to N and are all on one side of the street. You notice that all the numbers on one side of your house add up to exactly the same total as all the numbers on the other side of your house. What is the number of your house?

Solution: Let 'x' be your house number. Then,

sum (i=1 to x-1){i} = sum(i=x+1 to n){i}

x(x-1)/2 = {n(n+1)/2 - x(x+1)/2}

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

x^2 = n(n+1)/2

Looking at this equation, the conclusion is that the value of n should be such that:
- n/2 and (n+1) are both themselves squares, or,
- n and (n+1)/2 are both themselves squares

A simple C program indicates that the value of n is 288 and your house number is therefore, 204.

Puzzle: Safe boating

A simple version of the traditional boating and the hungry companions problem follows. Will try to find similar problems and post them as a bunch.

Problem: A boatman has to ferry across a stream a wolf, a goat, and a basket of cabbages. His boat is so small that only one of the three, besides himself, can be contained in it.

How is he to manage, so that the wolf shall have no opportunity of killing the goat, or the goat of eating up the cabbages ?

Puzzle: Water and Wine

Problem: You have two glasses each filled with exactly the same amount of liquid. One containing water, the other, wine.

First take a teaspoon of water from the water glass and pour it into the wine glass. Next stir the wine and water until well mixed. Then take a teaspoon of the water and wine mixture and pour it into the glass of water.

The question is: is there more/less/equal wine in the water glass than water in the wine glass ?

Puzzle: Truth City

Problem: You are on your way to Truth City, where the inhabitants always tell the truth. At one point you reach a fork in the road, with one branch leading to Truth City and the other leading to Lies City, where the citizens are all liars. The road signs at the junction are, as you can imagine, confusing, but there is a man standing there from whom you can ask directions.

The only problem is, you don’t know where he is from – the city where everyone always gives the right answer or the city where everyone lies. If you have time to ask him only one question, what question will ensure that you will be headed in the right direction ?

Puzzle: Hats off

Problem: Inside of a dark closet are five hats: three blue and two red. Knowing this, three smart men go into the closet, and each selects a hat in the dark and places it unseen upon his head. Once outside the closet, no man can see his own hat.

The first man looks at the other two, thinks, and says, “I cannot tell what colour my hat is.”

The second man hears this, looks at the other two, and says, “I cannot tell what colour my hat is either.”

The third man is blind. The blind man says, “Well, I know what colour my hat is.”

What colour is his hat?

Puzzle: Ages of sons

Problem: Two mathematicians meet on a plane.
"If I remember correctly, you have three sons”, says A. “What are their ages today?”.

“The product of their ages is thirty-six”, says B, “and the sum of their ages is exactly today’s date”.

“I am sorry, B”, A says after a minute, “but that doesn’t tell me the ages of your sons”.

“Oh, I forgot to tell you, my youngest son has red hair”.

“Ah, now it’s clear”, A says, “I now know exactly how old your three sons are”.

What are the ages of B’s sons ?

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.