CSE Blog - quant, math, computer science puzzles

Source: Sent to me by Prateek Chandra Jha (IIT Bombay) Problem: This problem is inspired by the Cheryl's Birthday Puzzle ( FB Post , Guardian Link ). Paul, Sam and Dean are assigned the task of figuring out two numbers. They get the following information: Both numbers are integers between (including) 1 and 1000 Both numbers may also be identical. Paul is told the product of the two numbers, Sam the sum and Dean the difference. After receiving their number, the following conversation takes place: Paul: I do not know the two numbers. Sam: You did not have to tell me that, I already knew that. Paul: Then I now know the two numbers. Sam: I also know them. Dean: I do not know the two numbers. I can only guess one which may probably be correct but I am not sure. Paul: I know which one you are assuming but it is incorrect. Dean: Ok, I also know the two numbers. What are the two numbers? Disclaimer: Its not a puzzle for 14-15 year olds like Cheryl's

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Source:   Mind Your Decisions Blog Related Problem:   Expected Length of Last Straw - Breaking the back of a Camel - CSE Blog Problem: Your boss tells you to bring him a cup of coffee from the company vending machine. The problem is the machine is broken. When you press the button for a drink, it will randomly fill a percentage of the cup (between 0 and 100 percent). You know you need to bring a full cup back to your boss. What’s the expected number of times you will have to fill the cup? Example:  The machine fills the cup 10 percent, then 30 percent, then 80 percent–>the cup is full plus 20 percent that you throw away or drink yourself. It took 3 fills of the cup.

Source: Puzzle Toad CMU Problem: You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite. You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people). Is it always possible to produce such a list?

Source: Puzzle Tweeter who took it from Mind your decisions Problem: A camel is loaded with straws until it's back breaks. Each straw has a weight uniformly distributed between 0 and 1, independent of other straws. The camel's back breaks as soon as the total weight of all the straws exceeds 1. Find the expected weight of the last straw that breaks the camel's back. Update (18th June 2014): Solution posted by me (Pratik Poddar) in comments

Source: Steve Miller's Math Riddles Problem: A square has a quarter in each corner. You are blindfolded and must get all quarters to be heads up or all to be tails up. You will be told when you have done this. You may flip however many you want, then ask if you are done (this constitutes a turn). The square is then rotated/spun an undisclosed number of times. You then get another turn and so on… Is there a strategy that is guaranteed to work in a finite number of moves, and if so, what is that smallest number of moves you need to be 100% you’ll be able to have all heads up or all tails up? The same problem is there on the blog - in a different form - asked more than 50 months back :-) - Blind Flipping - CSE Blog

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm? Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly. Update (24 June 2014): Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks claimtoken-52ac74fbddf1e

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: Tricky Question. Let f be a continuous, real-valued function on reals such that limit_{n \rightarrow \infty} f(nx) = 0 for all real x. Show limit_{x\rightarrow \infty} f(x) = 0.

Source: Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: For a given positive integer n, what would be the minimum no. of weights required so that we can weigh all positive integers <= n Follow up Generalized problem: If we have k copies of each distinct weight, then what is the minimum no. of distinct weights required ? Old Related Puzzle: There is a very different popular problem but knit in the same story (posted 4 years back on the blog): Weighing Problem Note : Weights are of integer values only.

Source: Sent to me by Vinayak Gagrani (CSE IITB Alumnus 2013) Problem: There are 289 students. We have to divide them into 17 groups of 17 each every day. The groups have to be such that no two students who have been previously on some group together can be formed a group again. How many days can we do this ? Extension: Can this be generalized for any N^2 students?

Source: IBM Ponder This - June 2012 - Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m > 1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins. What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ? We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game. Update (24 June 2014): Solution:  Posted by Gowtham Kumar (PhD Student, Stanford, IITM Alumnus) and me in comments!

Source: Solved it during Algorithms Course under Prof Diwan , and discussed with Nikhil Jain (IT BHU 2008 Alumnus, Product Manager at AskLaila) Problem: 1. (Easy)  Consider a n x m rectangular grid. The problem is to find the number of shortest (or monotonic in this case) paths along the edges of the cell that start at (0,0) and end at (n,m). A monotonic path is a path always moving towards the goal, i.e. consists of moving up or right but not down or left. Figure 1 illustrates such a path for a grid of size 5 x 3. 2. (Difficult)  Now we need to print all monotonic paths that do not go above the diagonal y = x. Figure 2 shows such a path. Note that the path in figure 1 goes above the diagonal, hence not desirable in this case. How many such paths exist for n x m grid (n >= m)? Disclaimer: The first problem is too simple, and the second is very challenging. Have fun :-)

Source: Original problem adapted from the "Ants Problem" (Link removed) at " CMU ACM Programming Contest " . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle  . Problem also available at  J. Paulson Programming Blog Problem: You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction. Walking Ants Puzzle  earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off? The new problem is : Given the starting positions and directions of all the ants, which ant(s) are the last to fall off? Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve. ( Readers Please ignore: Technorati claim:  6QVZ8YSY6XSD ) Update (24 June 2014): Solution:  Posted by Strilanc and me in comments!

Source:   The Math Factor  (contains spoilers) - also tweeted on What Would Martin Gardner Tweet Problem: The number of 1′s in this paragraph is ___; the number of 2′s is ___; the number of 3′s is ____; and the number of 4′s is ___. Bonus Research Follow-up Problem: The number of 1′s in this paragraph is ___; the number of 2′s is ___; …..(and so on) and the number of N’s is ___. For N=2 or 3, there are no solutions (Asking that all the numbers we fill in are between 1 and N); for N=4 there are two. For N=5 there is just one, for N=6 there are none and beyond that there is just one. Prove it. claimtoken-51f4577649b8d

Source:  http://www.math.utah.edu/~cherk/puzzles.html Problem: Prove that for any natural N, 1000^N - 1 cannot be a divisor of 1978^N - 1 Short and Sweet :)

Source: Introduced to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: An N by N matrix M has entries in {0,1} such that all the 1's in a row appear consecutively. Show that determinant of M is -1 or 0 or 1. Disclaimer: I could not solve it but I have an awesome solution sent by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012) Update (2/4/2013): Solution posted by Amol Sahasrabudhe (IITB 2004 Alumnus, Ex-Morgan Stanley Quant Associate, Deutsche Bank Quant Associate) and Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments! Thanks a ton. I have posted the solution provided by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012). All three solutions are essentially the same.

Source:  (Romanian Informatics Olympiad ONI'03, extended team selection) ( ^ Representative diagram of Huffman Encoding. No relevance in the problem) Problem: A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have  N<=36  symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the  N  symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in  O(N^4)  time, and use  O(N^3)  space.

Source: Puzzle collection by Raphael Reischuk Problem: Assume the following 3-player game consisting of several rounds. Players A and B build a team, they have one fair coin each, and may initially talk to each other. Before starting the first round, however, no more communication between them is allowed until the end of the game. (Imagine they are separated in different places without any communication infrastructure.) A round of the game consists of the following steps:  (1) the team gives one dollar to player C.  (2) Both A and B toss their coins independently.  (3) Both A and B try to predict the other's coin by telling the guess to C. (No communication: A does not know the outcome of B's coin toss, and vice versa, nor the guess).  (4) If C verifies that both A and B guess the other's coin correctly, then C has to give 3 dollars back to the team.  Should C play this game? Previously Asked Coin Puzzles: Coin Balancing Coins Puzzle...

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student) Problem: Given any two triangles in a plane construct a line which bisects both their areas. Background: In fact the existence of such a line is true in a very general setting - for any two polygons in a plane there exists a line which bisects both their areas. In fact its true for any two Jordan measurable sets in a plane. Further generalized version is called the Ham Sandwich Theorem and is proved using Borsuk Ulam Theorem.

Source:   15 Puzzle Problem:  The   15-puzzle   (also called   Gem Puzzle ,   Boss Puzzle ,   Game of Fifteen ,   Mystic Square   and many others) is a   sliding puzzle   that consists of a frame of numbered square tiles in random order with one tile missing. The object of the puzzle is to place the tiles in order (from figure at left to figure at right) by making sliding moves that use the empty space. Prove that the 15 puzzle in the configuration as shown on the left is not solvable. Related Links: I made this fb game yesterday night - 9 Puzzle over Movie Posters - Movie Sliding Puzzle Sam Loyd published some great puzzles in his time. One book that gets recommended a lot is "Sam Loyd's Cyclopedia of 5000 Puzzles tricks and Conundrums" ( Amazon , Flipkart ) Update: (24/12/2012) Solution provided by Raghuram Kowdeed (IIT Kanpur) in comments! Update: (24/12/2012) Same solution posted by Sai Teja Pra...