## Posts

Showing posts from August, 2009

### Five Thieves and Bounty

Another puzzle from Krishnamurthy Iyer's website

Problem
Five thieves have just looted a bounty of 1000 gold coins. The loot has to be divided among them and therein lies the problem. It is then decided that the youngest one will come up with a strategy of division, and the rest will put the strategy to vote. If the strategy is voted with a majority, it will be accepted and will be carried out. Otherwise, the youngest one will be shot and the second youngest will be asked to do the same...and so on. So the problem is, if you are the youngest thief, what will be your strategy, to maximize your share of the bounty? (Assume all thieves have different ages.)

Thieves base their decisions on three factors. First of all, each thief wants to survive. Secondly, each thief wants to maximize the amount of gold coins he receives. Thirdly, each thief would prefer to throw another overboard, if all other results would otherwise be equal

Update (11/12/09):
Solution provided by Jaadu ... Better e…

### Game of Two

This puzzle is taken from website of Krishnamurthy Iyer (Stanford)

Two immensely intelligent players, A & B, engage in a game, the rules of which are as follows. For some natural number N, the board consists of numbers from 1 to N. Each player takes turns to strike off a number from the board, with the added condition that if a number is struck off, then all its divisors should also be struck off. The player to strike off the last number on the board wins. A plays first. Is this game fair? If not, who has a winning strategy for each N and what is it? Else find the best strategy for each player.

### Cap Puzzle

Puzzle:
An evil troll once captured a bunch of gnomes and told them, “Tomorrow, I will make you stand in a file, one behind the other, ordered by height such that the tallest gnome can see everybody in front of him. I will place either a white cap or a black cap on each head. Then, starting from the tallest, each gnome has to declare aloud what he thinks the color of his own cap is. In the end, those who were correct will be spared; others will be eaten, silently.” The gnomes set thinking and came up with a strategy. How many of them survived?

Source:
Another one from Gurmeet's blog

Solution:
Highlight the part between the * symbols for the answer.
*There is no way for the tallest gnome to figure out the color of his own hat. However, all others can be saved! The tallest gnome says aloud “black” if there are an even number of black hats in front of him, otherwise he says “white”. The second tallest gnome can now deduce his hat color. He says it aloud. One by one, all others can deduc…

### Puzzle: Working Computer

Problem:
A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible.

(Once again, posed by Gurmeet Singh Manku on his blog)

Solution:
Highlight the part between the * symbols for the answer.
* [Thanks to Gaurav Bubna for his solution]

Pair up all the computers. In every pair, test one comp with other. We have 3 possibilities - correct correct, correct wrong, wrong wrong. correct correct can only come if both comps are either correct or both wrong. From each such pair just keep one comp.
Note that: Since for wrong wrong pairs and correct wrong pairs, both working can never be the case, so, in correct correct pairs, number of working > no of damaged.
So, the property number of working > no of damaged is preserved in the next iteration.
Note that we reduce number of elements bt more than half…

### Puzzle: What's the number on my Hat?

I got this puzzle from Gurmeet Singh Manku's blog. Awesome CS guy he is. Good one! Give it a try.
The solution proposed by Gurmeet was wrong. I have added a comment and I hope it would be corrected in some time.

Puzzle:
A goblin forewarns N gnomes as follows: “Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free.” The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy?

Solution: (correct version)
Highlight the part between the * symbols for the answer.
* Let gnomes be numbered 0 thru N-1. The i-th gnome should announce (i – s) mod N, …

### India and Open Source Software Part-2

Simon Phipps, Chief Open Source Officer at Sun, says that "India is where so much innovation is happening". The award (1 million\$ grant) is being announced in India because that's where I expect the greatest open source community growth to come from in the near future."

Two questions: Can India lead the world in open source technology? Is it good for the country?

In my last post (link), I talked about how I feel open source is good for the country (perhaps taking a biased view). Let me be more critical now. From an article in Business Standard, "Open source is a profound idea.... The enduring puzzle of India's software companies is their persistent inability to grow from projects to products. Open source is a powerful answer to this problem. Open source reduces the importance of products and raises the importance of services. In the open source world, each programmer builds on the work of others before him. This brings down the cost of development." …