CSE Blog - quant, math, computer science puzzles

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 org anizing 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. :() Solution: Posted by Nikhil Garg (Sophomore, CSE, IITD), Rajendran Thirupugal

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

Source: Problem 1.27 from the book "Heard from the Street" Problem: 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? Update(18/02/10): Solution: Posted by Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments!! Explanation and a different solution

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? Update(12/02/10): Solution: Posted by Shantanu Gangal (CSE IITB Alumnus and BCG Consultant) in comments!!

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

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. Solution: Update (02/03/10): Solution posted by Nikhil Garg in comments!

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. Update(08/02/10): 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!!

Problem: 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 h