CSE Blog - quant, math, computer science puzzles

This is a variation of the problem discussed some time back:  Don't roll More . Just published the solution to the earlier problem . Thought it would be interesting to solve this problem taken once again from the book "Heard on The Street". Problem:  You have 52 playing cards (26 black and 26 red). You draw cards one by one. A red card pays you a dollar. A black card costs you a dollar. You can stop any point you want. Cards are not returned to the deck after being drawn. What is the optimal stopping rule in terms of maximizing expected payoff? Also, what is the expected payoff following the optimal rule? Hint: Try the problem with 4 cards (2 red, 2 black) :) Update(29/01/10): Question was incomplete. Added more information. Solution: (Update (05/02/10)) Idea posted by Aman in comments!! Solution posted by me in comments!! The problem/solution is very difficult and not so beautiful. Its not very mathematical though. Do this only if you have time and you...

Problem: Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates I have read and solved many problems like these. Can people post some similar interesting problems using gates. I was asked one such question in my Deutsche Bank Interview which I was not able to answer. Update(09/02/10): Solution: Solution posted by Sid in comments!! Update(23/06/14): Solution: Interesting link shared by divby0 in comments!

Source: Puzzle Toad, CMU Problem: A hungry lion runs inside a circus arena which is a circle of radius 10 meters. Running in broken lines (i.e. along a piecewise linear trajectory), the lion covers 30 kilometers. Prove that the sum of all turning angles is at least 2998 radians. Update(05/02/10): Solution: Solution posted by me in comments!!

I solved IBM Ponder This October 2009 Challenge and IBM Ponder This November 2009 Challenge and now solved this very interesting puzzle at IBM Ponder This January 2010 Challenge I am happy!! My name on IBM's research site three times in 4 months. :) Problem: Present a computation whose result is 5, being a composition of commonly used mathematical functions and field operators (anything from simple addition to hyperbolic arc-tangent functions will do), but using only two constants, both of them 2. It is too easy to do it using round, floor, or ceiling functions, so we do not allow them. Source: IBM Ponder This January 2010 Challenge Solution: IBM guys would post it on their site by February 2010 :) Three different solutions given by Piyush (Fourth year, IITM), Aniesh Chawla (Fourth year, IITD) and me (Fourth year, IITB) :). All posted in comments!! Thanx to Anirudh Shekhawat urf Maoo (CSE, IITB & Google) for help in the last step :)

Some basic math olympiad problems: Divisible by 289? For how many integers x, x^2 - 3x - 19 is divisible by 289? Perfect square? For how many positive integral values of n, the expression n(4n + 1) is a perfect square? Update (23/01/10)(05/02/10): Solution: Posted by Aaditya Ramdas (CSE IITB Alumnus & Tower Research), Piyush Sao (Senior Undergrad, EE, IITM) and Nikhil Garg (Sophomore, IITD) in comments!!  Thanx.

Source: Insight (IITB Newsletter) Questech Problem : In a land far away, there is a village threatened by an hundred-headed beast. This beast can only be killed by cutting of all the hundred heads. Legend says that any brave warrior can cut off exactly 10, 20, 30 or 40 heads at one time. However with each of these, 40, 2, 60 and 4 new heads appear respectively. The village has lost several brave warriors against this beast. Can you save the village from this beast ? Update(21/01/10): Solution: Solution provided by Bhanu Prakash (M.Tech Student, CSE, IITB) in comments!!

Source: +Plus Magazine Problem: You're in a glitzy casino in Las Vegas. Having tried your hand at everything from Roulette to Black Jack, you've managed to lose most of your money and have only one dollar left. What's worse, with all the champagne and everything, you've misbehaved and the management has made it very clear that you're not allowed any more games. But you need two dollars to get the bus back to the hotel. Two shady-looking characters at the bar offer you a game: they have a pile of 15 stones. Each of you in turn is to take your choice of 1, 2, 3, 4 or 5 stones from the pile. The person who takes the last stone gets one dollar from the person who drew previously, and the third person neither wins nor loses. You're to draw first. You're sure that both of the other players will play to their best personal advantage and won't make any mistakes. Should you agree to play the game? Update(23/01/10): Solution: Posted by Gir...

Source: Gazette of the Australian Mathematical Society Problem: Two people, Give and Take, divide a pile of one hundred coins between themselves as follows. Give chooses a handful of coins from the pile and Take decides who will get them. This is repeated until all coins have been taken or until one of them has taken nine handfuls. In the latter case, the other person is allowed to take all of the remaining coins in the pile. What is the largest number of coins that Give can be sure of getting? Update (05/02/10): Solution: Solution by Aaditya Ramdas  (CSE, IITB alumnus & Tower Research) in comments!! Further explained by me in comments!!

Source: http://www.qbyte.org/puzzles/puzzle14.html Problem: (An interesting counting exercise) In how many ways, counting ties, can eight horses cross the finishing line? (For example, two horses, A and B, can finish in three ways: A wins, B wins, A and B tie.) Update(21/01/10): (simple combinatorics problem) Solution: Solution posted by Nikhil Garg (Sophomore, IIT Delhi) in comments!! Update(06/02/10): Interesting solution posted by Aman too.

Source : Puzzle Toad, CMU Problem: Each hat is black or white. The people are standing in a circle. Now our n hat wearing friends are standing in a circle and so everyone can see everybody else's hat. The hats have been assigned randomly and each allocation of hat colors is equally likely. At a certain moment in time each person must simultaneously shout "my hat is black'' or "my hat is white'' or "I haven't a clue''. The team wins a big prize if at least one person gets the color of his hat right and no one gets it wrong (saying "I haven't a clue'' is not getting it wrong). Of course, if anyone gets it wrong, the whole team is eliminated and this is painful. The prize is big enough to risk the pain and so devise a strategy which gives a good chance of success. Update (29/01/10): Solution:  Posted in comments by me. Update (06/02/10): Previous solution deleted. Solution reposted with more explanation. :)

Suppose N mothers live in a city. Half of them have one child and half of them have two children. That means that an average mother has 1.5 children. Suppose we pick the sexual orientation of every child by rolling dice. Let’s assume that a child has a 10% probability of being homosexual. The number of mothers with one child who is homosexual is 0.05N . The number of mothers with two children both of them homosexual is 0.005N . The number of mothers with two children with only the first child homosexual is 0.045N , which is the same as the number of mothers of two children with only the second child homosexual. The total number of mothers who have two children with at least one of them homosexual is 0.095N . Let’s calculate the average fertility of a mother with at least one homosexual child. It is (1*0.05N + 2*0.095N)/(0.05N + 0.095N) = 0.24/0.145 = 1.66 . The resulting number — 1.66 — is much bigger than 1.5, the average number of children for a mother. This means there is a ...

Source: Variant of a sub-problem in my seminar presentation on " Security Attacks on RSA " . Very interesting (and difficult) algorithms problem. Problem: An array of length n+1 is populated with integers in the range [1, n]. Find a duplicate integer (just one, not all) in linear time with O(1) space. The array is read-only and may not be modified. Solution: Update(20/01/10): Solution (from Gurmeet Singh Manku's blog) posted in comments!!

Source: Tanya Khovanova’s Math Blog Problem: The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake? Reference: This is a followup to the following problem http://pratikpoddarcse.blogspot.com/2009/08/cap-puzzle.html Update(24/01/10): Solution : Posted by me in comments (taken from a recent blog entry by Saurabh Joshi, IIT Kanpur)

Among Top 10 in India in Indian Sudoku Championship Elimination Round :) Indian Sudoku Championship 2010 Sudoku, dubbed as the hottest puzzle sensation since the Rubiks Cube gained worldwide popularity in early 2005. The first World Sudoku championship (WSC) was held in March 2006 in Lucca, Italy. The 5th WSC will be held in April 2010 in Philadelphia, USA. Logic Masters India in association with TechFest at IIT Bombay, invites you to test your logical skills in the Indian Sudoku Championship and get an opportunity to represent India at the WSC. All resident Indian nationals, irrespective of age, can participate in Indian Sudoku Championship. The sudoku-solving skills of contestants will be tested through the regular Classic sudokus as well as different sudoku variations which appear in the WSCs. Top rankers at the Indian Sudoku Championship will be eligible to represent India at the 5th World Sudoku Championship to be held in Philadelphia in April 2010. Rules and Regulations...

Story: I remember that I used to believe that shuffling cards more makes the pack "more" randomized. It turns out that if I was perfect, I would have given serious advantage to my opponents. Lets see how. :) Source: William Wu's Puzzle Page Puzzle : A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, …, 51, the new sequence is 0, 26, 1, 27, 2, 28, … With repeated in-shuffles, shall we ever get back the original order? In how many iterations? The shuffling technique described in the puzzle is known as the Faro Shuffle . Update(12/01/10): On a related note, I was searching for optimal shuffling algorithms and found this an interesting read. Update (14/01/10): Solution posted by me in comments!!

Source: Wikipedia (Classical "Exchange Paradox" problem) Problem: The setup: The player is given two indistinguishable envelopes, each of which contains a positive sum of money. One envelope contains twice as much as the other. The player may select one envelope and keep whatever amount it contains, but upon selection, is offered the possibility to take the other envelope instead. The switching argument: Denote by A the amount in the selected envelope. The probability that A is the smaller amount is 1/2, and that it's the larger also 1/2 The other envelope may contain either 2 A or A /2 If A is the smaller amount, the other envelope contains 2 A If A is the larger amount, the other envelope contains A /2 Thus, the other envelope contains 2 A with probability 1/2 and A /2 with probability 1/2 So the expected value of the money in the other envelope is: This is greater than A , so swapping is favored After the switch, reason in exactly the same ma...

Source: Taken from the book "Heard on The Street" (Problem 4.2 in Revised 9th Edition) by Timothy Falcon Crack. Saw a very similar problem in the placement test of a hedge fund coming to campus. (Cannot disclose the name. Policy signed :P) Problem: I will roll a single die not more than three times. You can stop me immediately after the first roll, or immediately after the second, or you can wait for the third. I will pay you the same number of dollars as there are dots on the single upturned face on my last roll (roll number three unless you stop me sooner). What is your playing strategy? Update(06/02/10): Solution: Posted by Vivek Kumar Jha (Elec IITB 3rd yr B.Tech) in comments!! Generalized solution by Aman !!

Source: Jaadu a.k.a Anshum Agarwal (Fourth Year, CSE, IITB and to be Tower Research Analyst) gave me this question. Said question from Tutorial of Prof. Sundar's course "Approximation Algorithms" Problem: There are n letters and n envelopes. Your servant puts the letters randomly in the envelopes so that each letter is in one envelope and all envelopes have exactly one letter. (Effectively a random permutation of n numbers chosen uniformly). Calculate the expected number of envelopes with correct letter inside them. Disclaimer: Not easy :P Update (10/01/10): Solution: Posted by Giridhar (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!! Nice solution. Update (21/01/10): With the help of Asad Ali (EE, IITB Alumnus), a different solution  posted by me in comments!!

Source: Peter Winkler book, Placement quant company interview, Wikipedia Problem: 1) How many times do you need to flip a coin before you expect to see both heads and tails? 2) How many times do you need to roll a die before you expect to see all the numbers 1-6? 3) A company — say Coca-Cola, for concreteness — is holding a contest where everyone who collects one each of n different "coupons" wins some prize. You get a coupon with each purchase of a Coke, and each coupon is equally likely. What’s the expected number of Cokes you have to buy in order to collect all the coupons? Update (10/01/10): Solution posted by Giridhar (IITK alumnus, Yahoo! Engineer) in comments!!

Source: Puzzle Toad, CMU Problem: Gridville is a perfect city. It is laid out as an nXn grid and each of n^2 families inhabits its own square. A developer o ers to buy k < n plots at a price of one billion Wazooli's per plot. If a plot is bought, the family will move out and the plot will be used for growing Garbash, the most valuable commodity in GridWorld. If at any time, a family plot has two Garbash plots adjacent to it, the smell of the Garbash will cause them to leave and the developer will buy up the plot for a mere million Wazooli's and start growing Garbash. After, 10 years, the developer agrees to clean up and replace the plots by family homes, unless everybody has left. The developer will not disclose where he plans to put his k initial plots. Should the inhabitants of Gridville take the money, given that they want to gt back to normal in 10 years? Different version of the problem: Source: Peter Winkler book "Mathematical Puzzles: A Connoisseur...

Source: " The Second Book of Mathematical Puzzles and Diversions " by Martin Gardner Problem: A chessboard has squares that are two inches on the side. What is the radius of the largest circle that can be drawn on the board in such a way that the circle's circumference is entirely on black squares?

Source: Puzzle collection of K. Rustan M. Leino, Microsoft Research Problem: You're on a government ship, looking for a pirate ship.  You know that the pirate ship travels at a constant speed, and you know what that speed is.  Your ship can travel twice as fast as the pirate ship.  Moreover, you know that the pirate ship travels along a straight line, but you don't know what that line is.  It's very foggy, so foggy that you see nothing.  But then!  All of a sudden, and for just an instant, the fog clears enough to let you determine the exact position of the pirate ship.  Then, the fog closes in again and you remain (forever) in the thick fog.  Although you were able to determine the position of the pirate ship during that fog-free moment, you were not able to determine its direction.  How will you navigate your government ship so that you will capture the pirate ship?:) Update(10/01/10): Solution: Thanx to Suyash Roongta (Firs...

Suggested to me by Giridhar Addepalli (IITK CSE Alumnus, Yahoo! Sr. Software Engineer). Nice puzzle. Original Source is "Thinking Mathematically" ( Amazon Link ). Giridhar posts nice mathematical problems on his blog . Interesting puzzle. It is not an easy problem. But the experience of getting stuck trying to solve the problem is in itself rewarding. Hint: Try and specialize. Organize the results of specialising. Make a conjecture, however wild. Check and prove your conjecture. Followup : Given by Giridhar on his blog. Using this, find an O(1) space algorithm to "rotation of array" problem where you are asked to rotate the array by a given amount k. For example, rotating Array containing 3, 5, 9, 14, 1, 2, 11 by 3 positions will yield 14, 1, 2, 11, 3, 5, 9. O(k) space algorithm is of course trivial. Can you find an O(1) space algorithm?

Problem: There are five holes arranged in a line. A hermit hides in one of them. Each night, the hermit moves to a different hole, either the neighboring hole on the left or the neighboring hole on the right. Once a day, you get to inspect one hole of your choice. How do you make sure you eventually find the hermit? Source: Puzzle collection of K. Rustan M. Leino, Microsoft Research Update (02/01/10): Give a deterministic strategy to find the hermit such that the hermit knows our strategy and would want to escape. Update (03/01/10): Solution: Partial solutions provided in comments by Saurabh Agarwal (CSE, IITB 2006-2010) and Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer). Detailed solution posted by me in comments!! Update (20/12/10): A general solution for n holes posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!