CSE Blog - quant, math, computer science puzzles

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: Asked to me by a friend - who was asked this question in an interview at Facebook Problem: Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm? Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: the optimal line passes through at least two of the points (otherwise rotate/translate it until it does without losing collinear points). So for each point p, compute the slope from p to every other point and tally frequencies in a hash map (use exact rational slopes dy/dx reduced by gcd, plus a sentinel for vertical lines - avoid floating point). The most frequent slope from p, plus p itself, gives the best line through p. Take the maximum over all p. Complexity: n points x O(n) slope computations and hash updates = O(n^2) expected time, O(n) space per round. (Deterministic O(n^2 log n) via sorting slopes instead of hashing.) This is worst-...

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/~maclagan...

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. Solution: Highlight the part between the * symbols for the answer. * Answer: e = 2.71828... fills. Let X_i be the fraction dispensed on press i (uniform on [0,1]) and S_k = X_1 + ... + X_k. You press a (k+1)-th time exactly when S_k < 1, so the expected number of presses is 1 + su...

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...