Posts
Showing posts with the label Discrete-Mathematics
Law of Large Numbers Failed
Problem: There are two maternity hospitals in a town with 50 and 500 beds. Given full occupancy on a particular day, which of these hospitals is more likely to have equal no of boys and girls given probability of boys = probability of girls ? What would the answer intuitively be by #LawOfLargeNumbers? You would see #LawOfLargeNumbers does not seem to work here. How should the statement be positioned for #LawOfLargeNumbers to work?
(Advanced) Cheryl's Birthday Puzzle
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
Buying in Rocket Ships and Selling in Fire Sale
Source: Asked to me by Ankush Jain (CSE IITB 2011, Morgan Stanley Quant Associate). He took it from Algorithms Design book by Tardos and Kleinberg Problem: Easy case: You’re trying to buy equipments whose costs are appreciating. Item i appreciates at a rate of r_i > 1 per month, starting from 100,ドル so if you buy it t months from now you will pay 100*((r_i)^t) . If you can only buy one item per month, what is the optimal order in which to buy them? Difficult case: You’re trying to sell equipments whose costs are depreciating . Item i depreciates at a rate of r_i < 1 per month, starting from 100,ドル so if you sell it t months from now you will get 100*((r_i)^t) . If you can only sell one item per month, what is the optimal order in which to sell them?
Fibonacci Multiple Puzzle
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).
Gold Silver Numbers Puzzle
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
Mathematics of SET game
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...
Expected Number of Attempts - Broken Coffee Machine
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.
Pebble Placement Puzzle 2
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?
Pebble Placement Puzzle 1
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.
Diminishing Differences Puzzle
Source: Australian Mathematical Society Gazette Puzzle Corner 34 Problem: Begin with n integers x1, . . . , xn around a circle. At each turn, simultaneously replace all of them by the absolute differences Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2. Shameless plug: Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora . :-)
Balancing Act Puzzle
Source: Australian Mathematical Society Gazette Puzzle Corner 35 Problem: There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right. Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced?
"Flawless Harmony" Puzzle
Source: AUSTMS Puzzle Corner 35 Problem: Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair. Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd. Update (23 Oct 2014): Solution: Posted by me (Pratik Poddar) in comments!
Minimum sum of numbers in an array
Source: Asked to me on quora ( cseblog.quora.com ) Problem: Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array? Example 1: 1 2 2 3 4 Answer : 0 (-1+2-2-3+4) Example 2: 2 3 4 7 13 Answer: 1 (+2-3-4-7+13)
Caterer's Problem
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?
3D Tic Tac Toe Puzzle
Source: Shared by Alok Mittal (Cannan Partners) Problem: A 3x3 tic tac toe has 8 "winning lines" (3 horizontal, 3 vertical and 2 diagonals). How many "winning lines" does the 3x3x3 3D tictactoe have? There is a brute force solution, and then there is the aha! solution. Update (23 Oct 2014) Solution: Posted in comments by Anti, Taz, Javier, Shubham Gupta, Leela. Detailed solution and much more advanced problems in the document http://library.msri.org/books/Book42/files/golomb.pdf