Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Aug 23, 2009

Five Thieves and Bounty

Another puzzle from Krishnamurthy Iyer's website

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 explanation by Maoo with arguments from PD
Highlight the part between the * symbols for the answer.
* When there are only two thieves left, oldest would never accept anything offered by younger, so younger would anyway get killed. So, 2nd oldest would never let the third oldest get killed. So, whatever the 3rd oldest offers to oldest and 2nd oldest, it would be accepted. So, he would offer them nothing and 2nd oldest would have no choice but to support him. Since, this way, oldest and second oldest are not getting anything, they would prefer whatever the 4th oldest proposes. So, fourth oldest would give 1 coin to oldest, 1 to 2nd oldest and nothing to 3rd oldest. They will have no option but to support him. So, if the youngest child offers 2 coins to oldest, 0 to 2nd oldest, 1 coin to 3rd oldest and 0 coins to 4th oldest.. The oldest and third oldest thieves would support him.

So, youngest, i.e I can go away with 997 coins. :) *

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.

Update (11/12/09): Solution in comments!!

Aug 22, 2009

Cap 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?

Another one from Gurmeet's blog

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 deduce their own hat color and say it aloud. *

What if hats come in 10 different colors?

Thanks to Gurmeet for personally helping me with the solution.

Highlight the part between the * symbols for the answer.
* How about ordering the c colors and allowing the first c-1 gnomes to announce the parity of the lowest c-1 colors among the last n-c+1 gnomes. Parity may be represented by the lowest two colors. The remaining n-c-1 gnomes can then deduce their own hat colors. So, for 10 different colors, maximum 9 gnome have to die.*

Better solution: (By Gaurav Bubna)
Highlight the part between the * symbols for the answer.
* Instead of each guy saying the parity of just one color, he can use the binary representation to announce parity of more than one color at the same time..

since everyone can announce a number between 1-10, the first 4 people would say a number between 0-7 to announce the parity of 3 colors.. This way maximum 4 people need to die.*
Update (12/01/10):
Even Better solution for the followup: (By Gurmeet Singh Manku - IIT Delhi, Stanford, Google Research)
Highlight the part between the * symbols for the answer.
*Let colors be labeled 0 thru c-1. The tallest gnome computes s, the sum of all the numbers he sees. Then he announces the color corresponding to s mod c. All other gnomes can now deduce their own cap colors, one by one!*

Puzzle: Working Computer

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)

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. So, T(n) < T(n/2) + n, i.e T(n) < 2n

So, in less than 2n comparisons, we will be able to find a working computer :) *

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.
Original Link
The solution proposed by Gurmeet was wrong. I have added a comment and I hope it would be corrected in some time.

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, where s is the sum of numbers he sees. With this strategy, if the sum of all N numbers equals m mod N, then the m-th gnome is guaranteed to announce the number of his own hat! *


Aug 16, 2009

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." Our dear President Abdul Kalam says: "The unfortunate thing is that India still seems to believe in proprietary solutions". Companies like Sun and IBM have been active supporters of Open Source since a long time. To some extent, Yahoo! and Google too support open source. But Microsoft has always been against open source. Ravi Venkatesan, chairman of Microsoft India, says it is no longer an either/or option. We firmly believe that multiple platforms can and should co-exist and recognize both the advantages of open source and the fact that platform heterogeneity is a reality in today's environment. Our focus is on enabling our customers to connect to other platforms, applications and data easily." In his view, despite its greater initial cost, Microsoft software is a better value than the open source alternatives. "Versus Linux, we deliver a clear value proposition to our customers. The USP of the Microsoft platform and our range of offerings is our end-to-end stack of offerings and our focus on integrated innovation. Customers, too, have matured in their view and there is almost universal recognition that Linux is not 'free', and that Linux today resembles more a commercially driven technology. Customers are beginning to look at Linux vendors like any other commercial software provider, focusing on the overall business advantage, value for money and the risk associated with making long-term technology investments." But isn't open source better for a "poor" country like India? Not at all, answers Venkatesan. "We should look at technology discussions in perspective, and when we do we will find that it has nothing to do with a country being poor or rich, but more to do with reliability of the framework, affordability and relevance. We should not confuse affordability with 'price' but should look at the TCO or lifecycle cost, including cost of access." Now, since I have put views from both the parties, what we can conclude is that if TCO of open source software is reduced (its not easy to calculate TCO, hence the problem), there is not argument to favour MS Windows over Linux. Expert suggestion from Wharton: "India needs to contribute more aggressively to the process of open source development. We have an opportunity to establish leadership in this space. India has a lot of creativity, and it is just a matter of time before that is reflected through open source software." In other words, the future of open source in India is still an open question.

 Best of Luck. :)

 (Inspiration and Quotes from Articles on http://knowledge.wharton.upenn.edu)

Aug 13, 2009

Amazing Boy Girl Paradox

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

Aug 3, 2009

Open Source is a Must for India

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 affordable IT products in India. Secondly, the fact that India has been only a "service-based" IT industry, is not too encouraging for me. If India has to succeed, India has to make a choice. The choice to start product based industries in India. If India has to "control" the world IT industry, it has to be developing products independently. Open source provides an even playing field to all. It is to be said here that Open Source is a business model, key term being business. It is not doing something for free (well, ya, ok). Indians can earn a lot of money using GPL. The plan is to compete with the existing companies by distributing stuff for free while still earning revenue from training, resources, donation and advertisement. All the views are entirely mine and I will be happy to answer questions and discuss more.