CSE Blog - quant, math, computer science puzzles

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 ...

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. Update (11/12/09): Solution in comments!!

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 ot

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 elem

I got this puzzle from Gurmeet Singh Manku's blog. Awesome CS guy he is. Good one! Give it a try. Original Link 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 –

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.&q

In a country, where people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. Who will be more in the country(boys or girls)? Intuitively, I and many of my friends thought it to be boys. Which seems fine as the society favours boys. But calculation shows that they would be equal. How? Suppose there are N couples. Note that each couple would have exactly one boy. So, no. of boys born is equal to N. Counting the no. of girls. N/2 parents would have no girl child. N/4 would have exactly 1 girl child, N/8 would have exactly two girl children, N/16 would have exactly 3 girl children and so on.... So, Expected no. of girls from N couples would be S: S = 1*N/4 + 2*N/8 + 3*N/16 + 4*N/32 + .......... 2S = N/2 + 2*N/4 + 3*N/8 + 4*N/16 + 5*N/32 + ............. So, S = N/2 + N/4 + N/8 + N/16 + ..... S = N So, Expected no. of boys = Expected no. of girls. Equal sex ratio. :)

India is a developing country. Most of us are seeing India's future as a developed country. Will IT play a role in this? I strongly feel "yes". I also feel that India's development would depend on the idea that how many Indians are willing to adapt to the Open Source Business Model. I present two ideas on why open source is a boon for India. The first would be on the basis of the facts suggesting that India cannot realise one laptop per child dream if it is using proprietary software. Open source is cheap, better, affordable, reliable. Open-source software meets the basic criteria of useful and affordable that people and businesses in emerging economies such as India need to adopt them. " To koi ye kyun le, wo na le ". As pointed out in the red hat articles with exact numbers, open source would cut down the cost by a lot and help people realise the dream. To add to it, Indian industries are mostly small or medium scale, which adds to the need of using affor