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

Dec 30, 2009

Top Card

Source: Asked to me by Nikhil Garg (Sophomore, IIT Delhi)

Problem:
We have a deck of n cards with cards labeled from 1 to n. Starting at any configuration , we repeat this : If the top card has number k , we reverse the order of top k cards. Prove eventually that 1 would be the top card.

I was able to solve it. Very interesting problem. :D

Update (03/01/10):
Solution: Posted by me in the comments!! Thanx to Giridhar and KP Ashwin (CSE, IITB) for the help.

Dec 28, 2009

Uniform Candy Distribution

Problem:
n children are sitting around a circular table. Each child starts out with an integer number of candies. The following step is repeated:
Every child who has an odd number of candies is given another piece of candy by the teacher. Each child now has an even number. Now every child passes half of his/her candy to the child on his/her left.

Prove that eventually all the children will have the same amount of candy.

Source: Puzzle Toad, CMU

Update (30/12/09): Solution: PDF Document from CMU Site

Dec 23, 2009

Gaadi chalao

Problem: A set of fuel dumps on a circular racetrack have just enough gasoline for one car to make one round trip. Prove that there exists a fuel dump from which one car, starting with an empty gas tank, can complete the round trip.

Source: Read it in many puzzle books. This form taken from Manku's blog.

Update (30/12/09) Solution: From the site cut-the-knot.org in comments!!

Fate of Ships

Four ships are sailing on a 2D planet in four different directions. Each ships traverses a straight line at constant speed. No two ships are traveling parallel to each other. Their journeys started at some time in the distant past. Sometimes, a pair of ships collides. A ship continues its journey even after a collision. However, it is strong enough only to survive two collisions; it dies when it collides a third time. The situation is grim. Five of six possible collisions have already taken place (no collision involved more than 2 ships) and two ships are out of commission. What fate awaits the remaining two?

Update June 18, 2010
Solution: Let z-axis denote time. let x- and y- axes denote the 2D planet. Then the four trajectories are straight lines. Since no collision involved more than two ships, these four lines must all lie in a plane. So, one might be tempted to believe that the two other ships will also collide. But, they might have collided in negative time. So, it cannot be decided from the given information that the two ships will collide or not?

This can be made clearer through the following two diagrams. In the first one, the four ships move such that there is no collision between the two ships. In the other diagram, the four ships move such that there is a collision between them.


Thanks to Vivek Jha (Then Junior Undergraduate, EE, IITB - Now Senior Undergraduate) for the solution

Dec 20, 2009

The Best Horse

Problem: You are the chief guest at an auction, where some number of horses will be auctioned, one after the other, randomly permuted. You are a connoisseur of horses, and can judge whether one horse is ‘better’ than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better?

Source: Fifty Challenging Problems in Probability with Solutions by F Mosteller

Disclaimer/Hint: If you are even half like me, you would love attempting this puzzle. Just do it using basic math and you will hit it right. The solution would even imply "Birthday Paradox" beautifully. :)

Update: (22/12/09) Solution posted by Giridhar in comments.

Dec 17, 2009

Kirkman's schoolgirl problem

Source: Classic combinatorics problem. Read it at a lot of places. Also in wikipedia Wiki Link

Problem: Nine schoolgirls are to be arranged in three rows and three columns on four different days so that any pair of schoolgirls is in the same row on exactly one of the four days.

Update:(18/12/09) Hint was wrong and hence removed. Solution by Giridhar in comments. Some discussion by me in comments.

Dec 10, 2009

Empty Bucket

Source: Tejas Hiremani (EE, IITB) asked this question. I had read it before in Peter Winkler's puzzle book and Carnegie Mellon's Puzzle Toad site. Nice problem.

Problem:
Given 3 buckets containing x,y,z litres of water. Assume buckets have "large" size. x, y, z are integers. You can move water from one bucket to another only if the bucket to which water is being transferred doubles the amount of water it has. So, all moves have to of the form:
If water is being moved from bucket containing x litres to bucket containing y litres. After the operation, the bucket containing y litres has 2y litres and the first bucket has x-y litres. Show that you can always empty one of the buckets. :)

Update (18/12/09):
Solution:
One solution posted by Aaditya Ramdas (CSE, IITB alumnus - Tower Research Analyst) in comments. A different solution posted by me in comments.

Catch me if you can?

Source: Asked to me by Ram Kumar, a frequent visitor to this blog.

Problem:
There's a duck swimming in a circular lake with a wolf at the edge. wolf won't enter water. Duck in water is slower than Wolf on land. Duck on land is faster than the Wolf on land. Given the lake diameter 'd' and wolf speed 'w', what is the minimum speed of the duck in water so that he can escape? what should be his escape strategy?

Hint:
1) Its less than w/4.
2) There is pi involved. :)

Solution:
Answer given by Vivek Jha (EE, IITB) in the comments. Proof of the solution given by me in the comments of one of the earlier posts: http://pratikpoddarcse.blogspot.com/2009/11/polyas-urn-problem.html?showComment=1258400372028#c8784580092886919079

Dividing gold into parts

Source: http://www.crackpuzzles.com/

You have hired a worker to clean your garage. The wage is a gold bar (which has 7 parts like a chocolate bar) for a weeks work. However, you don’t want to give the complete bar in the start. You want to pay the person 1 part for each day of his work. So at the end of first day he should have 1 part, at the end of second day 1 part more (a total of 2 parts), third day 1 part more (3 parts total)…at the end of the week all 7 parts. What is the minimum number of pieces that you should break the gold bar in to pay the worker?

Update: As pointed by Ramdas, this question is not very well framed. There are a few assumptions that you need to make. :)

Infinity Problem

Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied. A new customer wants to check in, how will you accommodate her? What if infinite number of people want to check in, how will you accommodate them then?

Hint: Define infinity. :)

Update (18/12/09): Solution in comments by Nikhil Pandey (CSE, IITB alumnus)

Dec 8, 2009

Ant Collision

Source: Anshum Agarwal (Jaadu) mailed me this problem 2-3 months back. I could solve it. :) Interesting problem.

Problem: Assume 100 ants are moving in 1 dimensional plane. All move with the same speed. Some are moving towards the positive x axis and some towards negative. If a collision occurs between two ants both ants changes the direction. If you are given direction of motion of each ant, how will you calculate the number of collisions that will occur?

Update (11/12/09): Solution: (Provided by Asad in Comments)

Weird Number Sequence

I find number sequences interesting. More because of their abstractness, their ability to surprise you, the infinite possibilities you need to explore, etc, etc. Basically the aha! factor.

I found one today and was completely baffled. I would not say this is the best "puzzle" and so I am posting solution with the problem but still interesting as it is weird :)

Problem:
What comes next? 1, 11, 21, 1211, 111221….

Solution:
Highlight the part between the * symbols for the answer.
* It’s known as Morris Number Sequence. What happens basically is you count the number of times a number appears in the sequence and write in next. So first number is 1 read as one 1 leading to the next number 11, which in turn is two 1. Therefore the next number in sequence is 21. 21 is read as one 2 one 1 leading to the next number in sequence 1211 which is now read as one 1 one 2 two 1 i.e. 111221. Next number becomes 312211 followed by 13112221, 1113213211 & it continues. :) *

Dec 7, 2009

Number of Locks and Keys

Problem:
7 thieves wanted to lock the treasure looted from a ship. They wanted to put locks to the treasure where each lock had multiple keys. Find the minimum number of locks N and minimum no. of keys K with every thief subject to the following conditions:-
All the locks should open each time a majority of thieves(4 or more) try to open the locks.
At least one lock remains unopened if less than 4 thieves try opening them.
All locks should have same no. of keys.
All thieves must have same no. of keys with them.

Source:
Shamir's paper on Secret Sharing Scheme states this problem and gives the answer with the explanation that its written in standard Combinatorics books

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

Expected Number of HH

Source: Placement Paper of one of the CS companies


Problem: A coin is tossed 10 times and the output written as a string. What is the expected number of HH? Note that in HHH, number of HH = 2

Example: In 3 tosses
HHH (2 HH)
HHT (1 HH)
HTH (0 HH)
HTT (0 HH)
THH (1 HH)
THT (0 HH)
TTH (0 HH)
TTT (0 HH)
Expected number of HH in 3 tosses = 2/8 + 1/8 + 1/8 = 0.5

Update (11/12/09): Solution:  Posted by Asad in Comments!!

Dec 5, 2009

Random point in a circle

This was the killer one. Interesting problem asked to me in one of the interviews.

You are given a black-box which returns a random number between 0 and 1. Give an algorithm to generate a point in the circle of radius 1.

(I was able to solve this but I must admit, its a difficult problem)

Update (December 10 2009) : To make things concrete: The black-box here returns a random number "uniformly" between 0 and 1. The question is to find a point "uniformly" in a unit circle. This would mean that the probability that a random point in the circle lies in a smaller concentric circle of radius r (r<1) is r^2. Solution by Jaadu in comments!!

Break the sticks

Three question related to stick breaking. A stick is of length 1.

1) The stick drops and breaks at a random point distributed uniformly across the length. What is the expected length of the smaller part? (Source: DB interview)

2) In the above experiment, what is the expected length of the larger part? (Source: Made it up)

3) In the third experiment, the stick is dropped and breaks at two points. What is the probability that the three pieces could form a triangle? (Source: V.K.Bansal notes, MathOverflow.net)

Update (18/12/09): Solution: Partial solution by Aaditya Ramdas (CSE IITB 2005-2009) and Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) and complete solution by me in comments.

Ants on a Cube

This was asked to me on Dec 1 in campus interviews of one of the companies.

We have a cube. An ant is on one of the corners. It moves randomly with equal probability in all the three directions. What is the expected number of steps to reach the opposite corner.

Note that the probability of the ant reaching the opposite corner in 2 steps is 0, in 3 steps is 6/27, in 4 steps is 0 and so on..

(I was able to solve it :D)

Update (11/12/09): Solution posted by Anshum (Jaadu, CSE, IITB) in comments!!

Dec 2, 2009

Placements and Puzzles!!!

Some real stud people told me that my blog helped them a lot in their interviews at IITB Campus placements. I am really happy about that. I must admit that my blog helped me too :P. In Morgan Stanley QM interview, about half the questions that were asked to me were from my blog. (Although I never pretended that I am thinking and then solving. I always told them that I have seen this problem before. But still, it gives you an extra delta point). In Deutsche Bank GMC interview, more than half of the questions were from the blog. I would really recommend all puzzle enthusiasts and also people who would be preparing for placements 2010-2011 to solve the book (Mathematical Puzzles: A Connoisseur's Collection) by Peter Winkler. Thanx for all your reviews on the blog. I am especially happy as I got responses from many friends after they were placed that my blog helped them. :)

Thanx junta!

Best of Luck!

Nov 25, 2009

Nearest Point problem

This was the question asked to Anirudh in his google interview. He could not do it (who cares! He got the job :D)
I could give a vague but correct answer :)

You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.

Of course, O(n) can be done {Compare best-so-far value for each point}
But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.

:) Interesting problem. Interesting solution.

Nov 23, 2009

Blind flipping

Four tumblers are placed at the corners of a square table. A blind gnome and an evil goblin take turns to play a game. The blind gnome gets to choose a subset of the four tumblers and flip them simultaneously. Effectively, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues: the evil goblin rotates the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?



Source: One of the questions in the placement paper of a quant company at another IIT

Update (11/12/09): Solution by Me, Jaadu and Ramdas in comments!!

Nov 14, 2009

Missing Digit

2^29, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2^29.

This question was posed to me by Dinesh Dharme (CSE, IITB). Simple but interesting puzzle!!

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

Nov 11, 2009

Polya's Urn Problem

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn?

Source:P. Winkler's Puzzles book. (Chapter: Probability).

Solution:
Highlight the part between the * symbols for the answer.
*This problem can be reformulated as the following problem.

Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent.

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest urn contains n/2 balls or 1 ball (or any number of balls between 1 and n/2) are all same. So, expected number of balls in the smaller urn is asymptotically n/4. :)

I am happy!! Happy Happy Joy Joy!! *

Nov 10, 2009

Flipping Bits in a Matrix

Puzzle: An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?

Source: Gurmeet Singh Manku's Blog where he said that he saw it in an old Russian problem book.

Solution:
Highlight the part between the * symbols for the answer.
* There are 36 3×3 blocks and 25 4×4 blocks. Given a sequence of blocks, the same effect is achieved no matter in what order the blocks are chosen. If the same block occurs two times in a sequence, their effect is nullified. Thus, a sequence of blocks is equivalent in effect to some subset of the 36 + 25 = 61 blocks. Starting with all zeros, at most 2^61 distinct configurations out of 2^64 possible configurations of the matrix can be reached. This means that we may not be able to remove all the ones from the original matrix. *

Fundoo question!!

Lets Call 50

I saw this puzzle on the site http://www.crackpuzzles.com/

Suppose two players are playing a game where we call integers. The first person who calls 50 wins. The rules are that the first person calls a number between 1 and 10. After that any new number that is called must exceed the last number by at least one and no more than by 10. For example: If the last number called is 15, then the next number that is called must be between 16-25.
I give you the first mover advantage, devise a strategy to win.

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

Minimum and Maximum

Source: IITM Friend (who did not want his name to be disclosed). Also read it once in CLR (Introduction to Algorithms)

Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons?

Update (11/12/09): Solution by Ameya and Me in comments !!

Nov 8, 2009

Weighing problems

These problems was posed to me by friends at NBHM Nurture Programme 2007 at IMSc Chennai

Problem 1:
A shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. How many minimum weights and name the weights you will need to measure all weights from 1 to 1000.

Solution 1:
Highlight the part between the * symbols for the answer.
*The numbers 1,2,4,8,16... This is optimal as each number has exactly one binary representation. So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, 512. :) *

------------------------------------------------------------------------------

Problem 2:
Same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2, by placing 3 on one side and 1 on the side which contain the substance to be weighed. How many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.

Solution 2:
Highlight the part between the * symbols for the answer.
* The numbers 1,3,9,27,81,243,729. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, -1}. So, this is optimal. *

------------------------------------------------------------------------------

Problem 3:
This is the most difficult one. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.

Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.

Solution:
Highlight the part between the * symbols for the answer.
* This is a problem to be solved by Gray code.

A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.

For this answer we need as many blocks as per Solution to Problem 1. For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1 - 125 range.
Now if we want to make packets of all weights from 1 to & we will do the following

001 We measure 1kg,using 1kg block.
011 We measure 3kg by placing 2 kg block also
010 We remove 1kg block and measure 2 kg.
110 We add 4kg weight and measure 6kg weight
and so on

Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with
1111 110
1111 111
So, it means that I can weigh all packets from 1 to 125 with only 125 shifts

A naive method was taking ~ 2^7*7/2 = 448 shifts :) *

Nov 6, 2009

Choose the maximum of two number

Source: P. Winkler

I write two different numbers in the range [a,b], one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen.

Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct.

Solution:
Highlight the part between the * symbols for the answer.
* I would choose a number randomly in the range [a,b]. Add 0.5 to it and save the number as k in my memory. If the number I see in one hand is less than k, I would say that the number in the other hand is greater. In the other case, I will say that the number in the other hand is less.


One can prove that here, winning probability is greater than 0.5
Let the number that comes out is k'


If k' less than k,
I am doing well when other number is either greater than k or between k' and k


If k' greater than k
I am doing well when other number is either less than k or between k' and k


So, the probability is greater than half, though getting an epsilon is not possible.


Answer :) *

Update(05/02/10): Thanx to Aaditya Ramdas for pointing out a "mistake" in the problem (discussion in comments). Problem statement changed slightly and is correct now. :)

Cyclic Strings

Found it in collection of Jian Li, CS Department, University of Maryland

Given 2 cyclic strings, both consisting n distinct letter,namely a permuatation of 1 to n.
the problem is to find a rotation of one string that minimize the swap distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other)

Can you give an O(nlogn) algorithm?
This is a difficult problem. So, think hard!!

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

Four Ants - HC Verma

Solved a more difficult problem in HC Verma 5-6 years back.. :)

Four bugs are on the corners of a 1 meter square. Each bug always faces the next bug (on the next clockwise corner). If they all walk forward at the same speed until they meet, how far does each bug travel?


Solution: 
Highlight the part between the * symbols for the answer.
*Since the bugs always move perpendicular to each other, so when they meet at the center they have traveled a distance equivalent to their initial separation i.e. 1 m.

If some of you remember, in the HC Verma problem, the three ants were moving in a equilateral triangle of side-size 1. The three ants were such that 1 is following 2, 2 is following three and three is following 1. By symmetry, they would meet at the centre. The time taken was 2/3v as you had to take components along the line joining the two ants. So, v(1+cos60) was the real relative speed along the line joining two ants. So, time taken was 2/(3v). So, the distance traveled was 2/3. :)*

Chicken Nuggets

Heard this problem many times. This problem is everywhere.

You can go to a fast food restaurant to buy chicken nuggets in 6-pack, 9-pack or 20-packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?

Solution:
Highlight the part between the * symbols for the answer.
*Yes. The number is 44

All numbers can be written in the form 3n-1, 3n or 3n+1. Now taking all nos. of the form 3n, all such numbers (except 3) can be formed by combination of 6 and 9.
Now let us take all numbers of the form 3n-1 which are greater than 20, starting with 23, 26, 29.... now again using the same concept like in the last part if we subtract 20(i.e. including a 20 nugget pack) from these numbers, the rest can be formed by combination of 6 and 9 other than 23 which would be the largest such number so far.
Similarly we will take all numbers of the form 3n-2 which are greater than 40, starting with 43, 46, 49.... and we will use the same concept like in the last part, if we subtract 40(i.e. including two 20 nugget packs) from these numbers, the rest can be formed by combination of 6 and 9 other than 43 which would be the largest number and so the answer to the puzzle is 44.*

Nov 5, 2009

IBM Ponder This November Challenge

I am happy.. I am amongst the first few people to solve IBM Ponder This November Challenge.. This puzzle, unlike the last one, is really challenging and requires mathematical skills.

I am posting the puzzle. IBM Guys would post the solution in a month's time.
IBM Page

What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1) divisor of a number between 2 and 166 (inclusive)?

We are asking for the exact answer in two cases:
In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?
On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.

* For example, the smallest divisor of 105 is 3, and of 103 is 103.

Update (26-05-2011)
Solution:
First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments!
Second part: Posted by Siddhant Agarwal, EE IITB 2011 Alumnus in comments!

Nov 2, 2009

No division operator and O(n)

Some site said that this is a google interview question:

There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i].

B[i] = (product from j = 1 to N, j not equal to i) A[i]

Example:

Input:[4, 3, 2, 1, 2]
Output:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!!
Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!

Oct 30, 2009

Another Coin Problem

Jaadu asked me this question in a Convex Optimization Class this semester. I was able to solve it. He said it was in one of Diwan Sir tutorials. :)
Interesting puzzle!!

You are given N coins (assume N to be of the form 2^k). Some are light and other are heavy.You are given one weighing machine. What is the number of weighing required to find the number of coins that are heavy?

A hint:
Try to divide the coins in two equal parts such that each have both have same number of heavy coins.

Previously asked coin puzzles:
Coins Puzzle
Consecutive Heads
Five Thieves and Bounty

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

Update (11/12/11): Weighing machine here is a weighing balance. Its a function isXgtY {Input X: Set of Weights, Input Y: Set of Weights, Output Bool 1 if X>Y and 0 if X<=Y}

Coins Puzzle

Once again.. Another coin puzzle after this and this (I wonder whether puzzles have anything else other than hats, kings and coins :D)

I heard this from Rushabh Sheth (Mech Sophie) who got it from Vivek Jha (Elec Thirdie).

There are 100 coins on the table out of which 50 are tail-face up and 50 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two equal halves such that both have equal number of coins with tails face up. (This obviously implies that the two have equal number of coins with heads face up)

Second part: There are 100 coins on the table out of which 10 are tail-face up and 90 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two halves (not necessarily equal) such that both have equal number of coins with tails face up.

Update (02/01/10): Sorry for inducing confusion in the system. :P Solution given by Vivek Jha, posted in comments by me!!

IBM Ponder This Puzzle

IBM Launches one puzzle every month in its "Ponder This" section. I just came to know about it day before yesterday and sent my solution for the active challenge.

Check my name at http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/October2009.html

The Puzzle is not mathematical though :P

Complete the following sequence:
1, 13, 2, 1, 5, 3, 2, 1, 4, 4, 7, 3, 1, 5, 3, 5, ?, ?

Hint: The solution is related to a quote about mathematicians.
You can do it only if you know it. Thinking does not really help!! :)

PandeyJi (Nikhil Pandey) said that he was able to solve it. :)

Solution: IBM guys will post it on their link in 2 days anyways! :)

Oct 29, 2009

Technician from IIT

This puzzle was asked to me last year by Manish Agarwal. He said that the answer was 20km.

A 120 wire cable has been laid firmly underground between two telephone exchanges located 10km apart.

Unfortunately after the cable was laid it was discovered to be the wrong type, the problem is the individual wires are not labeled. There is no visual way of knowing which wire is which and thus connections at either end is not immediately possible.

You are a trainee technician and your boss has asked you to identify and label the wires at both ends without ripping it all up. You have no transport and only a battery and light bulb to test continuity. You do have tape and pen for labeling the wires.

What is the shortest distance in kilometers you will need to walk to correctly identify and label each wire?

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

King's Poisonous Wine

Jaadu asked me this puzzle during our work visit to IBM Pune

Problem:

You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1024 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.

The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.

You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.

You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.

What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?


Solution:


Highlight the part between the * symbols for the answer.
* 10 prisoners must sample the wine.

Number all bottles using binary digits. Assign each prisoner to one of the binary flags. Prisoners must take a sip from each bottle where their binary flag is set.

With ten people there are 1024 unique combinations so you could test up to 1024 bottles of wine.

Each of the ten prisoners will take a small sip from 512 bottles. Each prisoner will have at least a fifty percent chance of living. There is only one binary combination where all prisoners must sip from the wine and in that case, all the 10 prisoners die. *

Oct 28, 2009

Find your number

This puzzle again is from Haidong's website.

Problem:
There are n people, each with a unique number from 1 to n. There are n identical lockers, each of which contains a paper with a unique number from 1 to n on it. However, you have no idea which locker contains what number. The purpose is for everyone to find the locker with his own number. Each one can open at most n/2 lockers and, once he looks at the number, he has to close the locker. If another person wants to see the same locker, he has to open it again himself. They can't exchange information with each other. Prove that there exists a certain constant that no matter how big n is, those people can always devise a strategy so all of them can find their own numbers with probability larger than that constant.

Note: this is surprising because if everyone picks n/2 lockers independent of other people, the probability that all of them find their own numbers is 1/(2^n), which goes to 0 as n goes to infinity.

I don't have a solution to this problem and the hint says "Use permutation theory from the group theory". Also, the non-zero probability obtained is 1 - ln 2, which is approximately 0.3. Someone please help me with this.

Update (11/12/09) Solution posted by "Anonymous" in comments!!!

Another Hat Puzzle

Another hat puzzle (One of the previous hat puzzles was this)

Source: Stanford student Haidong Wang

A teacher puts on 10 hats of either red or blue on 10 students. Each one can see the hats on all other 9 students, but not his own. The teacher tells them that at least one of the hat is blue. The teacher asks each one to write down the color of his hat if he's sure about it, or he can write down "don't know" if he can't deduce its color. Everyone reveals their answer at the same time and all of them write "don't know". The second day, they gather again and the teacher puts on the same hats. Each one has to think about the color of his hat again. This time, still no one can figure out his hat color (i.e. everyone writes down "don't know"). This game repeats in the same way on third day, fourth day, ..., until the ninth day. Still no one figures out. However, on the tenth day, everyone writes down the correct color of his hat. So explain what happened? And what's the color they wrote down? Assume throughout the 10 days, those students do not communicate with each other. And also assume everyone is smart and knows everyone else is smart, and so on.

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

See a car

Problem:
If the probability of observing a car on a highway in 20 minutes time is 609/625 then what is the probability of observing a car in 5 minutes time on the same highway (considering all the factors involved to be uniform)?

Solution:
Highlight the part between the * symbols for the answer.
*Probability of seeing a car in 20 minutes = 609/625
=> Probability of not seeing a car in 20 minutes = 1 - 609/625 = 16/625
=> (Probability of not seeing a car in 5 minutes)^4 = 16/625
=> Probability of not seeing a car in 5 minutes = (16/625)^(1/4)
=> Probability of not seeing a car in 5 minutes = 2/5

Hence, the Probability of seeing a car in 5 minutes = 1 - 2/5 = 3/5*

Tukde tukde

Consider a loop of string of unit length. Suppose we cut the string independently and at random in n places. This will divide the loop into n pieces.

1. What is the expected (average) size of the smallest piece?
2. What is the expected (average) size of the largest piece?

If you can't find an exact answer the asymptotic behaviour (to leading order) as n goes to infinity will suffice.

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

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(1,1) + f(0,1) + f(1,0) + f(0,0)]
f(1,1) = 1/4[f(0,2) + f(0,0)]
f(1,0) = 1/4[f(0,1) + f(0,0)]
f(0,1) = 1/4[f(1,2) + f(1,0) + f(0,2) + f(0,0)]
f(0,2) = 1/4[1 + f(1,0) + 1 + f(0,0)]
f(1,2) = 1/4[1 + f(0,0)]

Solving f(0,0) = 361/1699

\m/ \m/ Finally

2) For the second part, let the answer be x

x = 1/2*(1+x) + 1/4*(2+x) + 1/4*2 {i.e T + HT + HH}
So, x = 6

3) For the third part, let the answer be y
y = 1/2(1+y) + 1/4(2+y) + 1/8(3+y) + 1/8(3) {i.e. T + HT + HHT + HHH}
y/8 = 7/4
y = 14

Answer :)

Update (Nov 16, 2010): Solution to Part 1 added by me.

Expected Value

Roll a die, and you get paid what the dice shows. if you want, but you don't have to, you can roll the die again and get paid what the second roll shows instead of the first. What is the expected value?

Update (11/12/09): Solution by Pintu Kumar (CSE, IITB) in comments!!
Update (21/01/10): Solution posted by Pintu was wrong. Correct solution posted in comments by me!!

Oct 22, 2009

Mean minimum distance for N random points on a one-dimensional line

Posted by Mensen at mathoverflow.net
Very interesting problem (Very difficult actually)

Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. What is the probability 'p' that the minimum distance between any pair of these points is larger than some value 'k' or an expression for the mean minimum distance (MMD) for a pair of points in the set - referring to the smallest distance between any two points that can be found, not the mean minimum/shortest distance between all possible pairs of points.

Good problem :D ... I am happy!!!

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

Oct 13, 2009

9 balls

From Saurabh Joshi

Problem :
9 balls, 8 identical and 1 is lighter. You need to find out in 4 weights, which one is lighter. Sounds simple? Well, hold on. You are given 3 balance weight machines, out of which one is defective. You do not know which one is defective. Also, defective machine can give any outcome ( >, =, < ) irrespective of what you put on the machine. Now, can you find out which ball is lighter weighing only 4 times in total? Update:
Easier problem: A defective machine always outputs the same result. Its pointer always moves in the same direction.

Tougher problem: The defective machine gives a random result <, >, = all the time


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

Bulb Puzzle

Source: P. Winkler

In a circle are light bulbs numbered 0 through n-1 all initially on. At time t, you examine the bulb number t mod n, and if its on, you change the state of bulb t+1 mod n. If bulb t is off, you do nothing.

Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on.

Update (Nov 5 2009) : Thanx vivek, the small problem updated. Bulbs numbered 0 to n-1 instead to 1 to n. Thanx. Solution in comments!!

Oct 11, 2009

Walking Ants

Jaadu mailed me this problem today. I was able to solve it and I am happy. This is an "intelligent" problem. Solution so elegant that you will fall in love with it. :)

Assume 100 ants are moving in 1 dimensional plane, all move with the same speed. Some are moving towards the positive x axis and some towards negative. If a collision occurs between two ants both ants changes the direction. If you are given direction of motion of each ant, what is the number of collision that will occur? Give an algorithm. :)

Update (11/12/09): Solution by A Rustle (Prathmesh, CSE, IITB) in comments !!

Oct 9, 2009

Losing at Dice

When six dice are rolled, the number of different numbers which can appear range from 1 to 6. Suppose that once every minute, the croupier rolls six dice and you bet $1, at even odds, that the number of different numbers which appear will be exactly 4.

If you start with $10, roughly how long will it be, on average before you are wiped out?

:)

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

Shoot me!!

Source: P. Winkler

In a room stand n armed and angry people. At each chime of a clock, everyone simultaneously spins around and shoots a random other person. The persons shot fall dead and the survivors spin and shoot again at the next chime. Eventually, either everyone is dead or there is a single survivor.

As n grows, what is the limiting probabality that there will be a survivor. :)

Treat at H8 canteen for the person solving it first :)

Oct 7, 2009

Bol Baby Bol

Bol Baby Bol

Source: P. Winkler

You have an opportunity to make one bid on an object, whose value to its owner is, as far as you know, uniformly random between $0 and $100. What you do know is that you are so much better at operating the widget than he is, that its value to you is 80% greater than its value to him.

If you offer more than the widget is worth to the owner, he will sell it. But you get only one shot. How much should you bid?

Update (11/12/09)
Solution: (First solved by Jaadu)
Highlight the part between the * symbols for the answer.
* He should not bid (or bid 0$) !! Explanation in comments!! :) *

Oct 5, 2009

Top 3 out of 25 horses

Problem posed to me by Ankit Goyal (Civil, H2)

There are 25 horses. You want to find the best 3. Of course having a race and finding the top 3 is easy, but the constraint is that only 5 horses are allowed to race at once. Find the top 3 horses having minimum number of races.

Solution:

Post your answer here. The first to reply with a correct answer (except Ankit) gets an H8 canteen treat!!!

Update (11/12/09): Solution by angush (Ankur Mishra, H7, IITB) in comments!!

Semi-circle covering n points : Puzzle

Problem : (Posed by Saurabh Joshi, IIT Kanpur in his blog)

Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

Solution :
Highlight the part between the * symbols for the answer.
*
If a semi-circle covering all n points, indeed exists, then, a semi-circle covering all n points and starting from one of the points in a clock-wise direction also exists.

So, given a semi-circle which starts at one of the point in clock-wise direction. The probability that the rest of the n-1 points will be in that semi-circle is 1/(2^(n-1)). So for n such semi-circle, the probability will be n/(2^(n-1)) *

:)

Oct 4, 2009

The King's salary

Puzzle:

After the revolution, each of the 66 citizens of a certain country, including the king, has a salary of $1. The king can no longer vote, but he does retain the power to suggest changes - namely, redistribution of salaries. Each person's salary must be a whole number of dollars, and the salaries must sum to $66. Each suggestion is voted on, and carried if there are more votes for than against. Each voter can be counted on to vote "yes" if his salary is to be increased, "no" if decreased, and otherwise not to bother voting.

The king is both, selfish and clever. What is the maximum salary he can obtain for himself, and how long does it take him to get it? (from P.Winkler, loosely inspired by real historical events in Sweden)

Update (11/12/09) Solution: Highlight the part between the * symbols for the answer. * 63$ (Thanx to Deeepanshu (Civil, H2) for explanation in comments!! [What a fool I had been :(], Solution provided in Winkler)

To start with there are 66 citizens (including the king) with a salary of $1.
King first proposes that 33 citizens have their salaries doubled to $2, at the expense of the remaining 33 (himself included). 33 citizens whose salaries are being doubled are voting "for" and king is also voting "for" while giving away his $1. So, we have 33 "for" votes and 32 "against" votes. Proposition passed. We now have 33 citizens earning $2 and 33 citizens (including the king) without the salary.
Next, king increases the salaries of 17 of the 33 salaried workers to $3. 17 votes "for", "16" against, others do not care.
In the same manner king slowly reduced the number of salary-receiving citizens to 9, 5, 3, 2. At this point there are two citizens earning $33 each.
As a last trick, king bribes three paupers with $1 each to help him turn over the two big salaries to himself, thus finishing with a royal salary of $63.

As pointed out by Shantanu in comments, the king can take 65$ (!!!) if he is allowed to vote. *

Sep 6, 2009

Josephus Problem - Puzzle

Read about this in Concrete Mathematics - Knuth some time back... Interesting problem

There are n persons in a circle, numbered 1 to n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary).

Math at :
http://en.wikipedia.org/wiki/Josephus_problem

Solution:

In case of 13,
The order in which people die are
xxx0
xx01 {Since last bit of 13 was 1, hence xx01, otherwise it would have been xx11}
x111 {Since secondlast bit of 13 was 0, hence x111, otherwise it would have been x011}
0011 {Since thirdlast bit ....}

So, you would want to be 1011

So, we can see that the solution for a general n is
in the bit representation of n, add a bit 1 at the end and remove the first bit

So, for 1101 -> 1011

For 10,
order of killing is 2, 4, 6, 8, 10, 3, 7, 1, 9
So left is 5
1010 -> 0101

For 15,
order of killing is 2, 4, 6, 8, 10, 12, 14, 1, 5, 9, 13, 3, 11, 7
1111 -> 1111

For 7,
order of killing is 2, 4, 6, 1, 5, 3
0111 -> 1111?? 0111

For 6,
order of killing is 2, 4, 6, 3, 1
0110 -> 1101?? 0101

So, if the output is >n, we should be making the first bit 0

I suppose.. thats the answer.... :)

Aug 23, 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 explanation by Maoo with arguments from PD
Solution:
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

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

Followup:
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

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

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