Feb 19, 2010

Sweet Heart Mix Tape

Source: Placement test of one of the Algorithmic Trading Firms coming to the campus. Also in UC Berkeley, Spring 2001 Final Exam for CS170 (Efficient Algorithms and Intractable Problems)

Problem: Pratik is organizing a mix tape for his sweetheart, Pratiksha. The tape will have her top N songs of all time. Pratik was going to determine the order of these songs on his own, but then Pratiksha found out about his little project. Being an obnoxiously demanding woman, she has now given Pratik a price function f which takes a pair of songs [si,sj] as input, and returns a real number that quantifies exactly how good song sj sounds after song si, in her opinion. (Note that f([si,sj]) may not be equal to f([sj,si]).)

Write an O(n^2*2^n) algorithm for Pratik that will determine a song order which maximizes the total transition goodness of the mix tape. (If the maximum is not achieved, Pratik will be dumped. :()

Posted by Nikhil Garg (Sophomore, CSE, IITD), Rajendran Thirupugalsamy (Research Assistant, Stony Brook University) and "Anonymous" in comments!!

Feb 15, 2010

Coin Weighing Problem

Yet another coin problem. Read this today in "Heard from the Street". Found it interesting.

Problem: You are given a set of scales and 90 coins. The scales are of the old balance variety, that is a small dish hangs from each end of the rod that is balanced in the middle. You must pay 100$ every time you use the scales.

The 90 coins appear to be identical. In fact, 89 of them are identical and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing. What is your algorithm to complete this task?

Note that the unusual coin may be heavier than the others or it may be lighter. You are asked to both identify it and determine whether it is heavy or light.

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

Update (18/02/10): Solution posted by me in comments!! A non-optimal but simpler solution posted by Bhanu (M.Tech Student, CSE, IITB). Another solution posted by Suman in comments!! Thanx

Feb 14, 2010

Drunk Guests

Source: Problem 1.27 from the book "Heard from the Street"


A very large number, N, of people arrive at a convention. There are exactly N single rooms in the hotel where the convention takes place. Each guest is given a numbered key for a specific room. Before they even go upstairs, they are all invited to a large party in the banquet hall. To gain admittance to the hall, they have to give up their keys to a doorman. At the end of the evening, the guests are not sober enough to recall their room numbers, so the doorman simply hands out the keys randomly. Each guest ends up spending the night in a random room.

What is the probability that at least one guest ends up in a room he or she was originally assigned?
What is the expected number of guests who end up in a room in which they were originally assigned?

Posted by Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments!! Explanation and a different solution by me in comments!!

Feb 11, 2010

Pebble Piles

Problem: You are given three piles with 5, 49 and 51 pebbles respectively. Two operations are allowed:
(a) merge two piles together or
(b) divide a pile with an even number of pebbles into two equal piles.

Is there a sequence of operations that would result in 105 piles with one pebble each?

Solution: Posted by Shantanu Gangal (CSE IITB Alumnus and BCG Consultant) in comments!!

Feb 10, 2010

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"

Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right now and once every month earlier, on an average I go out once every 15 days. So, I like approximately 60 girls every month. That means I have liked approximately 3,600 girls in 5 yrs.)

Going ahead with this number, slow as I am in developing human relationships, I need at least 3 dates to "test" whether I like this girl or not. So, If I am to date all 3600 girls, I need 11000 dates. Even if I am "seeing" multiple girls together, I need 30 years to date all of them. So, clearly problem reduces to selecting a smaller subset of girls.

Which girl should I ask?

Lets remind you of the scene from the movie: The Beautiful Mind. Suppose all the guys are equally smart and intelligent. Suppose you are there in a bar with a few friends and there is a group of beautiful girls all of whom are brunettes, except one blonde. Most people would like to approach blonde first, however this is not a good strategy as Nash points out:

If we all go for the blonde, we block each other and not a single one of us is going to get her. So then we go for her friends, but they will all give us the cold shoulder because nobody likes to be second choice. But what if no one goes to the blonde? We don’t get in each other’s way and we don’ t insult the other girls. That’s the only way we win“.

This means that the prettiest girl in the group would always be there to be asked. No one would ask her out as everyone would be too afraid. Consider a guy who decides to talk to the blonde.

There are three possibilities:
1) He talks to the blonde and gets accepted. (Gets x points)
2) He talks to the blonde and gets rejected. He cannot go to the brunette now. (Gets 0 points)
3) He does not talk to the blonde and goes to the brunette directly. (Gets y points)

Note that x>y>0

Assume there are N guys and N girls (I am not talking about an IIT situation)
Each guy (since none of them is gay) has 2 possible actions (talk to blonde or talk to brunette). So, the sample space has size 2^n.

However, a particular guy gets x points if the guy approaches blonde while all others do not. Let us assume that the probability that a guy approaches blonde girl is p. So, for me to approach blonde, the award associated with it is x(1-p)^(n-1). While in the other case, the reward I get is y. So, the pareto optimal equilibrium point is the point when x(1-p)^(n-1) = y

So, p = 1 - (y/x)^(1/N-1)

1) At N approaches infinity, p tends to zero. That is people are more afraid to ask the most beautiful girl out.
2) If you are a beautiful girl and you know that N is large, don't be choosie. Just go out with one of those N guys (I am one :P)
3) If you are a guy and y value for you is very small, you don't have a lot to lose. Go for the prettiest girl.
4) Whatever it is, I know the math behind this article is flawed. Read it and forget about it. You are a fool if you argue with me and a gentleman/gentlewoman if you leave nice comments!! :)

Update(11/02/10): Had a lot of small mistakes earlier. Improved it. :)

Feb 9, 2010

Checkers Problem

Source: Nikhil Garg (Sophomore, IITD) mailed them to me.

Problem 1:
A checker starts at point (1,1). You can move checker using following moves :

1) if it is at (x,y) take it to (2x ,y ) or (x,2y)
2) if it is at (x,y) & x>y take it to (x-y,y)
3) if it is at (x,y) & x<y take it to (x,y-x)

Characterise all lattice points which can be reached.

Problem 2:
You have a checker at (0,0) , (0,1) , (1,0), (2,0), (0,2), (1,1) each. You can make a move as follows:

if(x,y) is filled  & (x+1,y) and (x,y+1) both are empty, remove checker from (x,y) & put one at each of (x+1,y) and (x,y+1)

Prove that under this move , you can not remove checker from all the six initial points.

Update (02/03/10): Solution posted by Nikhil Garg in comments!

Feb 7, 2010

Invert the Cups

Source: Techfest 2010 Puzzle Hut

Problem: It is desired to invert a set of n upright cups by a series of moves in each of which n-1 cups are turned over. Show that this can always be done if n is even  and never can be done if n is odd.

Solution: Posted by Ankush Agarwal (2nd yr, CSE, IITB), Dinesh Dharme (4th yr, CSE, IITB), Nikhil (2nd yr, IITD) and Siddhant Agarwal (3rd year, EE, IITB) in comments!! For just solution, read Ankush's and Sid's comment!! Proof of bound posted by me in comments!!

Fair Hat Game

A king wants his daughter to marry the smartest of 3 extremely intelligent young princes, and so the king's wise men devised an intelligence test.

The princes are gathered into a room and seated, facing one another, and are shown 2 black hats and 3 white hats. They are blindfolded, and 1 hat is placed on each of their heads, with the remaining hats hidden in a different room.

The king tells them that the first prince to deduce the color of his hat without removing it or looking at it will marry his daughter. A wrong guess will mean death. The blindfolds are then removed.

You are one of the princes. You see 2 white hats on the other prince's heads. After some time you realize that the other prince's are unable to deduce the color of their hat, or are unwilling to guess. What color is your hat?

Note: You know that your competitors are very intelligent and want nothing more than to marry the princess. You also know that the king is a man of his word, and he has said that the test is a fair test of intelligence and bravery.

Source: http://www.folj.com/

Solution: Posted by Ankush (Sophomore, CSE, IITB) in comments!!

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...