CSE Blog - quant, math, computer science puzzles

Source: Alok Goyal (Stellaris VP) puzzle blog Problem: This is another famous puzzle in the Martin Gardner collection, and variations of this puzzle exist in different “sizes”. This particular one has been picked up from The Colossal Book of Short Puzzles and Problems, Puzzle 9.18. Replicating the puzzle as is. Lenox R. Lohr, president of the Museum of Science and Industry in Chicago, was kind enough to pass along the following deceptively simple version of a type of combinatorial problem that turns up in many fields of applied mathematics. A traveler finds himself in a strange town without funds; he expects a large check to arrive in a few weeks. His most valuable posession is a gold watch chain of 23 links. To pay for a room he arranges with a landlady to give her as collateral one link a day for 23 days. Naturally, the traveler wants to damage his watch chain as little as possible. Instead of giving the landlady a separate link each day he can give her one link the first...

Source: Alok Goyal Puzzle Page ( http://alokgoyal1971.com/ ) . Alok is ex-IIT Delhi, Partner at Helion VC Problem: Part I (Easy): Using a clock, divide a pizza among 12 people Part II (Difficult): Using a clock, divide a pizza among 11 people? Solution: Highlight the part between the * symbols for the answer. * Part I (12 people): cut along the radii pointing at the 12 hour marks - they are evenly spaced at 360/12 = 30 degrees, giving 12 equal slices. Part II (11 people): use the 11 moments in 12 hours when the hour and minute hands exactly overlap (12:00, ~1:05:27, ~2:10:54, ..., ~10:54:33). The minute hand gains 330 degrees per hour on the hour hand, so successive overlaps are 12/11 hours apart, and the overlap direction advances by exactly 360/11 degrees each time. Those 11 radii are therefore equally spaced - cutting along them divides the pizza into 11 equal slices. Bonus extension from the comments: minute and second hands overlap 59 times an hour - the ...

Source: Sent to me by Sudeep Kamath Problem: Airline check-in baggage has size restriction by ​so-called ​linear dimension: length + breadth + height should not exceed 62 inches. Prove that you can't "cheat" by packing a box with higher linear dimension into a box with ​lower​ linear dimension. Solution: Posted by GoKu in comments!

Source: Mailed to me by Kushagra Singhal, Ex-IIT Kanpur, PhD Student at University of Illinois at Urbana-Champaign Problem: Prove that for any positive K and a natural number n, every (n*K)th number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence. More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K). Solution: Posted by Alex_IITD in comments!

Source: Mailed to me by JDGM ("regular commenter JDGM") Problem: The integers greater than zero are painted such that: • every number is either gold or silver. • both paints are used. • silver number + gold number = silver number • silver number * gold number = gold number Given only this information, for each of the following decide whether it is a gold number, a silver number, or could be either: 1.) gold number * gold number 2.) gold number + gold number 3.) silver number * silver number 4.) silver number + silver number Solution: Highlight the part between the * symbols for the answer. * First, the whole colouring is forced into one shape: pick any G > 1 and let gold = multiples of G, silver = everything else. Proof: 1 is silver (if 1 were gold, then silver x 1 would have to be gold by rule 2 - contradiction). Let G be the smallest gold number, so 1..G-1 are silver. Rule 1 (silver + gold = silver) then makes every non-multiple of G silver (write it as kG + r, 0 < r...

Source: AUSTMS Gazette 35 Related Problem: Pebble Placement Puzzle 1 Problem: Peggy aims to place pebbles on an n × n chessboard in the following way. She must place each pebble at the center of a square and no two pebbles can be in the same square. To keep it interesting, Peggy makes sure that no four pebbles form a non-degenerate parallelogram. What is the maximum number of pebbles Peggy can place on the chessboard? Solution: Highlight the part between the * symbols for the answer. * Answer: 2n - 1. Construction: fill the entire first row and first column - 2n - 1 pebbles. Any further pebble at (r, c) completes a rectangle (a non-degenerate parallelogram) with the pebbles at (r, 1), (1, c) and (1, 1), so nothing more can be added. Upper bound: suppose row i contains N_i pebbles in columns C_i1 < C_i2 < ... . Within row i, consider the N_i - 1 differences C_ij - C_i1 (j >= 2). Across all rows this gives N - n differences, where N is the total number of pebbles, e...

Source: AUSTMS Gazette 35 Problem: There are several pebbles placed on an n × n chessboard, such that each pebble is inside a square and no two pebbles share the same square. Perry decides to play the following game. At each turn, he moves one of the pebbles to an empty neighboring square. After a while, Perry notices that every pebble has passed through every square of the chessboard exactly once and has come back to its original position. Prove that there was a moment when no pebble was on its original position. Solution: Highlight the part between the * symbols for the answer. * Consider the moment just before the FIRST pebble (call it x) completes its tour - i.e. x has visited every square exactly once and is about to step back onto its original square. At that moment, look at any other pebble y. If y were sitting on its own original square, there are two possibilities. Either y left at some point and came back - but then y had already completed a full tour and returned...

Source: http://nrich.maths.org/ Problem: A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions: SUB JOURNEY     DISTANCE = 1000     WHILE (DISTANCE > 0.001)         MOVE DISTANCE         STOP         ROTATE(90, DEGREES, CLOCKWISE)         DISTANCE = DISTANCE / 2     END WHILE     EXPLODE END SUB Where does the robot explode? Update (23 Oct 2014): Solution:  Posted by me (Pratik Poddar) in comments!

Source: FunctionSpace.org Problem: Given the polygons P and Q as shown in the grid below, cut P into two polygons P1 and P2 such that, when pasted together differently, they form Q. Update ( 21 June 2014 ) : Solution by Varun and Adwait in comments!

Source: Asked to a friend at Goldman Sachs Quant Interview Problem: Estimate the value of pi using a dice Update: (21 June 2014) Solution posted by Tushar Makkar, 'My first amateur attempt', Satadip, Gaurav Bajaj and me (Pratik) in comments. Thanks

Source: Cute problem sent by Sudeep Kanath Problem: Prove that (2n choose n) is never a perfect power Update ( 21 June 2014 ): Solution:  Posted by Sandeep, Dinesh Krithivasan and Vishal Khatri in comments.

Source: http://thomer.com/riddles/ Problem: If you have an array with random odd and even numbers, what is the most efficient algorithm you can think of to put all even numbers on one side and all odd numbers on the other side in this array? What is the complexity of your algorithm? Update ( 21 June 2014) Solution posted by nick, Abhishek, Khalil Sawant, Sandeep, Stainless (Ameya Ranade - CSE IITB 2009 Alumnus, Google Engineer, Facebook Engineer), Piyush Sao, Sakshi, Kaushal and Pankaj Jindal in comments! Thanks. 

Source: Asked for a data scientist position at a technology startup in financial services sector in London Problem: What is the optimal algorithm to find the minimum element given a rotated sorted array of integers? A rotated sorted array of integers is the output array of a rotation operation performed on a sorted array. Eg: 3 5 6 1 2 Update (24 June 2014): Solution: Posted by Gaurav Bijay Kumar (CSE IITB 2006, Goldman Sachs Quant, Morgan Stanley Quant, Chicago Booth MBA, Credit Suisse IB, Goldman Sachs Strat), Sandeep, Khalil Sawant, Himanshu, ciddhi and gaurushh.

Source: Quantnet Problem: You have a string of bits. You scan from right to left. If you encounter a '1', you have the option to flip it to a 0 or keep it as is. If you encounter a '0', your adversary has the option to flip it to a 1 or keep it as is. Your goal is to zero all the bits once you reach the end of a scan (i.e. at the left most bit), whilst you adversary wishes to prolong the game indefinitely. We continually re-scan until we reach the aforementioned goal state. Can you prove that the game will eventually terminate? Solution: Highlight the part between the * symbols for the answer. * Yes - you can always force termination. Proof by induction on the number of bits n. Base: n = 1 is trivial (flip a 1; if it is 0, the adversary must flip it or lose, and you flip it next scan). Step: assume you can force a win on any string of n - 1 bits. For n bits, ignore the leftmost bit entirely and play your winning (n-1)-bit strategy on the rightmost n-1 ...

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at  http://puzzletweeter.com/ Problem: A group of students are sitting in a circle with the teacher in the center. They all have an even number of candies (not necessarily equal). When the teacher blows a whistle, each student passes half his candies to the student on his left. Then the students who have an odd number of candies obtain an extra candy from the teacher. Show that after a finite number of whistles, all students have the same number of candies. Update (20 May 2013): Partial Solution posted by JDGM in comments. Completed by me.

Source: Quantnet Problem: Roll a penny around another fixed penny in the center with edges in close contact. After moving half circle around the center penny, you will find the penny in motion has rotated 360 degrees. Why? Update (29/06/2013): Solution posted by Sanket Patel and Suyash Jain (IITB Mech 2008 Aumnus, Ex-Credit Suisse Analyst, Ex-Deutsche Bank Analyst) in comments!

Source:   http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml Problem: My fancy new digital alarm clock is broken! The time 'jumps' around. When I reset it, it reads 12:00:00. Then it runs as it should, but after 12:04:15 it resets back to 12:00:00. It counts up to 12:04:15 again and then it jumps to ... 12:08:32 ! Weird stuff. Do you know what's wrong with my alarm clock? Update (12/02/2013) Solution posted by Saumya Gupta, Abhimanyu Dhamija (CSE IITB 2011 Alumnus, Citibank Analyst) and Naga Vamsi Krishna in comments!

Source: Counter-intuitive Conundrums Problem: Someone hands you a deck of cards which you thoroughly shuffle. Next, you start to deal them, face-up, counting the cards as you go. “One, Two, Three …” The aim is to predict what the count will be when you encounter the second black Ace in the deck. If you had to select one position before you started to deal, what number would you select that maximizes your chance of guessing the location of the second black Ace? Solution: Posted by Sky in comments!

Source: Andrej Cherkaev's List of Puzzles Problem: A computer scientist claims that he proved somehow that the Fermat theorem is correct for the following 3 numbers: x=2233445566, y=7788990011, z=9988776655 He announces these 3 numbers and calls for a press conference where he is going to present the value of N (to show that x^N + y^N = z^N and that the guy from Princeton was wrong). As the press conference starts, a 10-years old boy raises his hand and says that the respectable scientist has made a mistake and the Fermat theorem cannot hold for those 3 numbers. The scientist checks his computer calculations and finds a bug. How did the boy figure out that the scientist was wrong? Update (06/01/2012): Solution posted by a lot of people in comments!

Source:  xkcd wiki Problem: The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants. You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza? You don't know which round number it is, but if you ask, the king will tell you. Does it matter? Disclaimer: Very easy problem! Update (31 January 2013): Title changed to "Pizza Distribution Puzzle" from "...