CSE Blog - quant, math, computer science puzzles

Source: CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science Lecture01. Course pointed to me by Aaditya Ramdas (To be CMU Grad Student & CSE-IITB Alumnus) Problem: Fit disks of the following diameters into a circular cavity of size 12.000: 2.150 2.250 2.308 2.348 2.586 2.684 2.684 2.964 2.986 3.194 3.320 3.414 3.670 3.736 Write a program or give a general algorithm to solve a general case. Disclaimer: Did not spend a lot of time on the problem but I have not been able to solve it. Clearly sum of the squares of the smaller radii is less than the square of the larger radii suggesting that it might be possible to fit disks. I am not able to make any more comments!

Source:  Very interesting puzzle from http://forums.xkcd.com/ Problem: There are 7 people standing in a circle, and each has either a red or a blue hat. The colors of the hats are chosen uniformly at random (although the problem is much the same if they're chosen adversarially). The people can't see their own hats, but can see each others'. Everyone is given a strip of paper and a pen, and simultaneously writes "red", "blue", or "abstain". Nobody can see what the other people are writing, or convey information in any other way. They win if somebody guesses his own hat color, and nobody guesses wrong. Find a strategy (which they agree on ahead of time) that maximizes probability of winning. Obviously, it is impossible to make a strategy that wins every time, because somebody must guess and that person has no information. To make it easier, try it first with three people. Disclaimer: I posted this problem (in different words) 4 months ...

Source: http://blog.tanyakhovanova.com/ Problem: You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice? Disclaimer: It is a difficult problem Hint: (Highlight from * to * to see the hint) * Some people post wrong solutions and believe they have solved it. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the person assumes that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they’d get the same result if they had 1 and 4 on the left, for example, and 5 on the right. I propose the following sequence a(n) . Suppose we have a set of n coins of different weights weighing exactly an integer number of grams ...

Source: Asked to me by Ankush Agarwal (Sophomore, CSE, IITB) Problem: There are two kinds of coins, genuine and counterfeit.  A genuine coin weighs X grams and a counterfeit coin weighs X+delta grams, where X is a positive integer and delta is a non-zero real number strictly between -5 and +5.  You are presented with 13 piles of 4 coins each.  All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit.  You are given a precise scale (say, a digital scale capable of displaying any real number).  You are to determine three things: X, delta, and which pile contains the counterfeit coins.  But you're only allowed to use the scale twice! Prize: Treat at H8 canteen to the first person who solves it!! Solution: Highlight the part between the * symbols for the answer. * Number the piles 1 to 13 and take coins from them in the two weighings as follows (pile: coins in weighing 1, coins in weighing 2): 1:(0,4) 2:(1,2) ...

The paradox imagines that Sleeping Beauty volunteers to undergo the following experiment. On Sunday she is given a drug that sends her to sleep. A fair coin is then tossed just once in the course of the experiment to determine which experimental procedure is undertaken. If the coin comes up heads, Beauty is awakened and interviewed on Monday, and then the experiment ends. If the coin comes up tails, she is awakened and interviewed on Monday, given a second dose of the sleeping drug, and awakened and interviewed again on Tuesday. The experiment then ends on Tuesday, without flipping the coin again. The sleeping drug induces a mild amnesia, so that she cannot remember any previous awakenings during the course of the experiment (if any). During the experiment, she has no access to anything that would give a clue as to the day of the week. However, she knows all the details of the experiment. Each interview consists of one question, "What is your credence now for the pr...

Source: http://www.math.utah.edu/~cherk/puzzles.html Problem: Salt Lake City looks like a rectangle crossed with M streets going from North to South and with N streets going from East to West. The city is frequently visited by tourists who suppose to run around in the buses. The Utah governor wants to vigil all moves of the buses. He plans to put policemen at some intersections to watch all the buses moving on the streets visible from that intersections. What is the minimum number of policemen needed for the bus watch? Update (26/03/10) Solution: Posted by Ashu and Aman in comments!!

Unexpectedly Great Expectations Post here shows an awesome paradox. The paradox is called St. Petersburg paradox. I have spent hours explaining this paradox to many smart friends of mine. This is probably the best paradox I have ever seen. Just reposting the game from that article: WARNING: THESE ARE THEORETICAL GAMES. Try not to bias yourself by how much YOU value 1000$ compared to how a millionaire values 1000$ (the utility function of money is a constant for all people). Also, we assume God has infinite amount of money with him, and does not lie when he says he will pay you, so please don’t give arguments like “put the money on the table and I will play” (replace 1$ by 0.001$ or any such figure if you want to satisfy yourself practically). God offer you the option of playing a game,  exactly once , against me. This is how the game works. God will toss a fair coin until a T turns up. The sequence of coins H n T will earn you 2 n  dollars. More explicitly, a T o...