Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Apr 25, 2010

Oleg Kryzhanovsky’s Problem - Coin Sequence

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 from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky’s problem asks to prove that a(6)=2. It is easy to see that a(1)=0, a(2)=1, a(3)=2. Its fun proving that a(4) = a(5) =2.
*

Apr 14, 2010

Weighing Piles of Coins

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

Apr 2, 2010

Sleeping Beauty Paradox

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 proposition that our coin landed heads?"

This problem is considered paradoxical because the answer is often given as either 1/3 or 1/2.

Think!! :)

Detailed analysis in the wikipedia article : http://en.wikipedia.org/wiki/Sleeping_Beauty_problem