Flipping 100 Coins

You have 100 fair coins and you flip them all at the same time. Any that come up tails you set aside. The ones that come up heads you flip again. How many rounds do you expect to play before only one coin remains? What if you start with 1000 coins? Click below for the answer.

When you flip 100 coins in the first round, you should expect to see about 50 heads. When you flip those 50 coins again in the second round, you should expect about 25 heads. This (approximate) halving pattern will continue until you're left with only one coin. On average, it will take 6 or 7 rounds when starting with 100 coins because $$log_2(100) = 6.644$$
When you start with 1000 coins, the game will last about 10 rounds. (So if you want to bet someone that you can flip a coin and have it come up heads 10 times in a row, you'll greatly improve your odds if you start with 1000 coins!)

See my Probability GitHub repository for a script that shows how to model this problem in Python.

True or False?

You're taking your college entrance exam, and things are not going well. You spent too much time answering the essay questions and word problems, and now you're running out of time. You turn to the final section and are relieved to find that it consists of 100 True/False questions. The bad news is that you only have 2 minutes left to complete the entire exam!

You figure it doesn't matter if you answer all True, all False, or just guess randomly. Odds are you'll probably get half of them right either way. You begin scribbling in your answers.

How many different ways (unique sequences) are there to answer 100 True/False questions? Click below for the answer.

If you're a computer programmer, you may have recognized right away that this is just a binary counting problem in disguise. Substitute 1 for True and 0 for False, and this is the same as asking how many unique values can be represented by 100 binary bits. Since that's every value from all 0s to all 1s, the answer is $2^{100}$, or 1,267,650,600,228,229,401,496,703,205,376.

Fraction of 1000

What is 1/2 of 2/3 of 3/4 of 4/5 of 5/6 of 6/7 of 7/8 of 8/9 of 9/10 of 1000? Click below for the answer.

At first glance, this problem looks a lot harder than it is. If you work backwards starting at 9/10 of 1000, it's easier to see that the final answer is 100.

Three Water Bottles

You have three water bottles with capacities of 8 quarts, 5 quarts, and 3 quarts. The largest bottle is filled with water, and the other two are empty. If there are no graduation marks on any of the bottles, how can you split the water evenly so that two of the bottles contain exactly 4 quarts each? You can only use these three bottles. Click below for the answer.

There may be other ways to solve this problem, but here's one sequence that works.

1. Fill the 5 quart bottle, leaving 3 quarts in the 8 quart bottle.
2. Pour 3 quarts from the 5 quart bottle into the 3 quart bottle, leaving 2 quarts in the 5 quart bottle.
3. Empty the 3 quart bottle into the 8 quart bottle , leaving 6 quarts in the 8 quart bottle.
4. Pour the 2 quarts from the 5 quart bottle into the 3 quart bottle.
5. Fill the 5 quart bottle from the 8 quart bottle , leaving 1 quart in the 8 quart bottle.
6. Pour 1 quart from the 5 quart bottle into the 3 quart bottle (filling it), leaving 4 quarts in the 5 quart bottle.
7. Pour the 3 quarts from the 3 quart bottle into the 8 quart bottle, leaving 4 quarts in the 8 quart bottle.

That's a lot to follow, so here are the steps in tabular form.

8 qt.	5 qt.	3 qt.
8	0	0
3	5	0
3	2	3
6	2	0
6	0	2
1	5	2
1	4	3
4	4	0

The Compulsive Gambler

You are approached by a compulsive gambler with the following proposal. You are to flip a fair coin four times. If heads and tails both appear twice each, he will pay you $11. If any other combination of heads and tails appears, you have to pay him only $10. Do you take the wager? Click below for the answer.

This is not a good gamble. Below are all the possible outcomes for four successive coin flips.

Notice that exactly two heads and two tails only appear six out of sixteen times, so you can only expect to win this game about 37.5% of the time. At the offered stakes ($11 for a win, $10 for a loss) you'd be losing an average of around $2.12 every time you play.

This problem appeared as an exercise in Introductory Graph Theory by Gary Chartrand.
See my Probability GitHub repository for a script that shows how to model this problem in Python.

The Lily Pad

A lily pad starts out very small, but doubles in size every day. After 60 days it has completely covered a pond. After how many days had it covered one-quarter the area of the pond? Click below for the answer.

The instinctive answer might seem to be 15 days, but that would only be correct if the lily pad was growing linearly. Remember, the lily pad doubles in size every day, which is exponential. To solve this puzzle, just work backwards. If the lily pad completely covers the pond on day 60, then half the pond was covered on day 59, and one-quarter of the pond was covered on day 58.

Three Coin Flips

The following game has a $10 entry fee. You are to flip a fair coin three times. The first time it comes up heads you are paid $5. The second time it comes up heads you're paid an additional $7. The third time it comes up heads you're paid $9 more, for a possible maximum prize of $21. Would you pay the $10 entry fee to play?

If not, what would be a fair price for this game? Click below for the answer.

It's not a good idea to play this game at the offered entry fee. Here are the eight possible outcomes when flipping a coin three times, along with how much you would win after each flip.

When you subtract out the $10 entry fee, you only win "big" ($11) one out of eight times. Three times you win only $2, three times you lose $5, and one out of the eight times you lose your entire $10 entry fee. If you average these, you can expect to lose $1 every time you play. So, if you lower the entry fee to $9 this would be a fair game.

This problem appeared as an exercise in Introductory Graph Theory by Gary Chartrand.
See my Probability GitHub repository for a script that shows how to model this problem in Python.

One equals 0.999...

The following is a mathematical proof that 1 is equal to 0.999.... What's wrong with it? Click below for the answer.

$x = 0.999...$
$10x = 9.999...$
$10x = 9 + 0.999...$
$10x = 9 + x$
$9x = 9$
$x = 1$

There's nothing wrong with it. 1 really is equal to 0.999...

Two equals one?

The following is a mathematical proof that two equals one. What's wrong with it? Click below for the answer.

$a = b$
$aa = ab$
$aa - bb = ab - bb$
$(a + b)(a - b) = b(a - b)$
$a + b = b$
$a + a = a$
$2a = a$
$2 = 1$

The problem is in the fourth step, where both sides of the equation are divided by $(a - b)$. Since $a = b$ is given at the start, $a - b$ is 0, and you can't divide by 0.

Draw Two

Two numbers are drawn at random from the integers 1 through 10. What is the expected value of their sum? Does it change if the second draw is done with or without replacement? Click below for the answers.

This puzzle is from Patrick Honner. It's easy to calculate the expected value with replacement. It's just two times the expected value of a random draw from 1...10, so 2 * 5.5, or 11. The interesting part is that when you draw two numbers without replacement the expected sum doesn't change. Why is that?

To find out, take a look at what happens to the expected value of the second draw for each value of the first draw. (Expected value is just the average of the remaining numbers.)

1st draw	E(2nd draw)
$1$	$6$
$2$	$5\frac{8}{9}$
$3$	$5\frac{7}{9}$
$4$	$5\frac{2}{3}$
$5$	$5\frac{5}{9}$
$6$	$5\frac{4}{9}$
$7$	$5\frac{1}{3}$
$8$	$5\frac{2}{9}$
$9$	$5\frac{1}{9}$
$10$	$5$

As the value of the first draw increases, the expected value of the second draw decreases. If you take the sum of each column you get 55. Divide by 10 to get the average and you get 5.5, so when you add them together you arrive back at the solution of 11.

See my Probability GitHub repository for a script that shows how to model this problem in Python.

Counting Chickens

If one-and-a-half chickens lay one-and-a-half eggs in one-and-a-half days, how many eggs does one chicken lay in one day? Click below for the answer.

For many people, the intuitive answer is one egg, but it pays double-check your math on this kind of problem. The daily rate of eggs per chicken per day is given by the formula

daily rate = eggs / (chickens x days)

Plugging in the numbers from the first part of the problem, we get

daily rate = 1.5 / (1.5 x 1.5)
daily rate = 1.5 / 2.25
daily rate = 2/3

So, one chicken lays two-thirds of an egg in one day.

Number Sense

How good is your "number sense"? How many of the following can you answer without using a calculator or looking up a conversion factor?

1. Are there more inches in a mile, or Sundays in 1000 years?
2. Are there more seconds in a week, or feet in 100 miles?
3. Are there more millimeters in a mile, or seconds in a month?
4. Which is larger, multiplying all the numbers from 1 to 10, or multiplying just the even numbers from 1 to 16?
5. Which is longer, 666 days or 95 weeks?
6. Which is longer, 666 inches or 55 feet?
7. Which is longer, 666 hours or 28 days?
8. Are there more ounces in a ton or inches in a kilometer?
9. Which is hotter, $0^{\circ}C$ or $0^{\circ}F$?
10. Which is larger, $e^\pi$ or $\pi^e$?

Click below for the answers.

1. Inches in a mile. (63,360. There can be up to 52,178 Sundays in 1000 years.)
2. Seconds in a week. (604,800, compared to 528,000 feet in 100 miles.)
3. Seconds in a month. (Even if the month only has 28 days, that's 2,419,200 seconds, compared to only 1,609,340 millimeters in a mile.)
4. Just the even numbers from 1 to 16. (Multiplying all the numbers from 1 to 10 gives you 3,628,800. Multiplying the even numbers from 1 to 16 give you 10,321,920.)
5. 666 days. (95 weeks is only 665 days.)
6. 666 inches. (55 feet is 660 inches.)
7. 28 days (which is 672 hours).
8. Inches in a kilometer. (39,370.1, compared to 35,840 ounces in a long ton, which is the heaviest ton.)
9. $0^{\circ}C$ is "hotter" since it is equal to $32^{\circ}F$
10. $e^\pi$ (23.14) is larger than $\pi^e$ (22.46).

Replacing Marbles

We place 15 black marbles and 15 white marbles in an urn. We have 30 additional black marbles in a bag. Then we follow these rules.

1. Remove two marbles from the urn.
2. If they are different colors, put the white marble back in the urn and the black marble in the bag.
3. If they are the same color, put both marbles in the bag, then put one black marble from the bag into the urn.

Continue following these rules until only one marble is left in the urn. What color is that marble? Click below for the answer.

When I first heard this puzzle, I immediately thought of writing a Python script, since that's my favorite method for dealing with problems in probability. This is a logic problem in disguise, though. I realized that as I tried to figure out the best way to set up the problem in code. If you pay close attention to the rules for adding and removing marbles from the urn, and the initial conditions, you'll notice a couple of things.

1. You start with an odd number of both black and white marbles in the urn.
2. The rules force you to always keep an odd number of white marbles in the urn (they can only be removed two at a time), but allow for both odd and even numbers of black marbles.

From those observations it's easy to see that when you get down to one marble, it must be a white marble.

Factor Sums

Not counting itself, the number 6 has the factors 1, 2, and 3, which add to 6. The number 28 has the same property (its factors are 1, 2, 4, 7, and 14). Can you come up with a three-digit number that has this property? What about a four-digit number? Click below for the answers.

If you knew that a number that is the sum of its own proper divisors is called a Perfect number, this puzzle was pretty easy. You could just search for that name and find the solutions are 496 and 8,128. Perfect numbers have been known at least as far back as Euclid (323–283 BCE), who included a formulation for then in his book of Elements.

The formulations states that $q(q + 1) / 2$ is a perfect number whenever $q$ is a prime of the form $2^p - 1$ for prime $p$ (now known as a Mersenne prime). So, if we know the first few Mersenne primes, we can calculate the first few perfect numbers.

$3(3 + 1) / 2 = 6$
$7(7 + 1) / 2 = 28$
$31(31 + 1) / 2 = 496$
$127(127 + 1) / 2 = 8,128$
$8,191(8,191 + 1) / 2 = 33,550,336$

The ancient Greek mathematicians would not have known that 8,191 was a prime, so Euclid would only have known the first four Perfect numbers. Now you can say you know something that Euclid didn't!

Minimum Percentage

75% of men from a certain group are tall, 75% have brown hair, and 75% have brown eyes. What is the minimum percentage that are tall, have brown hair, and have brown eyes? Click below to see the answer.

Instead of thinking in percentages to solve this problem, it's helpful to think back to the Pigeonhole Principle. Think of a group of 100 men, then 75 are tall, 75 have brown hair, and 75 have brown eyes. That's 225 individual attributes to assign to 100 men, so at least 25 of them (or 25%) must have each of the three attributes.

A Two-Digit Number

Find a two-digit number that's equal to two times the result of multiplying its digits. Click below to see the answer.

My first attempt at solving this puzzle was to set it up as an equation and try to solve it algebraically. Let's say the two digits are $x$ and $y$. Then the equation would be:

$10x + y = 2xy$

The left-hand side is the two-digit number ($x$ in the tens place, $y$ in the ones place) and the right-hand side is two times the result of multiplying its digits. If you try to isolate either $x$ or $y$, you'll see that it's not very easy to come up with a clean solution. That's because the equation above describes a hyperbola.

That's not exactly a dead end, but it isn't the kind of easy-to-understand (once you see it) solution I like in a logic puzzle. Luckily, there's an easier way. There aren't that many possibilities (we're only dealing with two digits), and we can eliminate a lot of them.

For example, we know that neither digit is 0. Also, we know that $2xy$ is an even number, so $y$ must be even (because the result of adding it to an even number is even). We also know that the product of the digits must be less than 50, otherwise $2xy$ would have three digits. That gets us down to only 32 possibilities to test.

Any other shortcuts that I can think of would only eliminate a few possibilities, but it's easy to just test the remaining ones (I went through them manually, but you could write a short script or use a spreadsheet), and find that the solution is

$36 = 2 * 3 * 6$

50 factorial

50! = 30414093201713378043612608166064768844377641568960512071337804000

Without doing the full computation, can you tell whether the above statement is true or false? Click below for the answer.

You can probably guess that the statement is false, otherwise it wouldn't be much of a puzzle. The reasoning, though, is that the factorial for 50 must include the factors 10, 20, 30, 40, and 50, so it must end in at least five zeroes. The value above ends in only three zeroes, so it cannot be correct. (The correct value is 30414093201713378043612608166064768844377641568960512000000000000.)

Bags of Marbles

You have three identical bags, each containing two marbles. Bag A contains two white marbles, Bag B contains two black marbles, and Bag C contains one white and one black marble. You pick a bag at random and draw out one marble. If the marble is white, what is the probability that the other marble in the same bag is also white? Click below to see the answer.

Many people will instinctively answer 50%, or 1/2, since the marble has two possible colors, but the probability is actually 2/3 (66.67%). Why? If the first marble is white, then you know you didn't randomly select Bag B. That means that the first marble you selected has three (not two) possibilities:

1. The first marble in Bag A.
2. The second marble in Bag A.
3. The white marble in Bag C.

Only in the third case will the other marble be black, so there's a 2/3 probability that when the first marble is white, the second marble will also be white.

If you want to see how you would model this problem in Python, you can look at my solution on GitHub.

The Pigeonhole Principle

The pigeonhole principle states that if a group of pigeons flies into a set of pigeonholes, and there are more pigeons than pigeonholes, then there must be at least one pigeonhole with two pigeons in it. More generally, if k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects. Despite its seeming simplicity (perhaps obviousness), it can be used to solve a surprising range of problems in probability, number theory, and computer science, just to name a few. See if you can use it to solve the following three problems.

1. (Warm up) A drawer contains a dozen blue socks and a dozen black socks, all unmatched. If the room is dark, how many socks do you have to take out to be sure you have a matching pair?
2. Prove that there are at least two people in Tokyo with exactly the same number of hairs on their heads.
3. Prove that if five distinct integers are selected from the numbers 1 through 8, there must be at least one pair with a sum equal to 9.

Click below to see the answers.

1. (Warm up) If you've only heard one problem involving the pigeonhole principle, it was probably the classic sock drawer problem. You only need to pick three socks to make sure you have one matching pair. When you pick two socks, you might already have a matching pair, or you might have one of each color sock. Selecting one more sock ensures that you have at least two socks of one color or the other.
2. The Tokyo hairs problem sounds like something you might be asked as a "brain teaser" interview question. If you're stuck in an interview, then the first step is to show off your estimating skills. Since we're not in that situation, we can just use Google to find out that there are about 100,000 hairs on the average human head, and that Tokyo is home to about 13.6 million people. That's more than enough people for our proof. For the sake of simplicity, let's say that 200,000 is the maximum number of hairs a person can have on their head. Then, if you select 200,001 people who happen to each have a distinct number of hairs on their heads (zero is a valid number of hairs to have on your head), you only need one more to ensure that two people have the same number of hairs. (Note: This puzzle will work with any city larger than 200,001 residents.)
3. To see how the pigeonhole principle applies to this problem, you just need to group the numbers 1 through 8 in pairs that sum to 9. {1,8}, {2,7}, {3,6}, {4,5}. Now, if I select four distinct numbers from that range, I might select one number from each of the four pairs. If I select a fifth number, then I must complete one of the pairs that sums to 9.

Coffee with Cream

Suppose you have two cups in front of you, one with precisely 8 fluid ounces of coffee, and the other with precisely 8 fluid ounces of cream. You take precisely one teaspoon of the cream and add it to your coffee. You stir it in so that it's thoroughly mixed. Then you take precisely one teaspoon of that coffee/cream mixture and put it back into the cup of cream. Does the cup of coffee have more cream in it, or does the cup of cream contain more coffee? Click below for the answer.

This question is a bit tricky. It's tempting to think that the cup of coffee contains more cream, because the teaspoon of cream added to the coffee was 100% pure, while the teaspoon of coffee added to the cream was diluted. However, it's important to remember that the total volume of each vessel changed by one teaspoon after the first transfer of fluid. The coffee/cream mixture was greater by two teaspoons than the pure cream. Before I reveal the answer, let's re-frame the question in discrete units.

Suppose that instead of liquids, our two cups contained 20 black marbles and 20 white marbles. You take 5 white marbles and thoroughly mix then in with the black marbles. Then you randomly select 5 marbles from the black/white marble mixture and place them back in the cup of white marbles. Are there more white marbles in the black cup or more black marbles in the white cup?

If you're like me, you may be tempted to treat this as a probability problem, but it isn't one. When I think about randomly drawing marbles, I want to immediately start writing a quick simulation in Python, but as you'll see, that isn't necessary. We can easily enumerate all possible outcomes in this scenario to find the answer to the question. When we draw 5 marbles from the cup with a mixture of 20 black and 5 white marbles, then place them in the cup with the other 15 white marbles, there are only 6 possible outcomes:

black	white	black/white mix	white/black mix
5	0	15/5	15/5
4	1	16/4	16/4
3	2	17/3	17/3
2	3	18/2	18/2
1	4	19/1	19/1
0	5	20/0	20/0

So the black/white ratio of the 5 marbles in the second transfer doesn't really matter. The end result is that there are always the same number of white marbles in the black cup as there are black marbles in the white cup.

The same is true of the original coffee/cream problem. The ratio of the two liquids in the teaspoon that is transferred to the cup of cream is such that you will end up with precisely the same volume of coffee in your cream as there is cream in your coffee. So the answer to the trick question posed at the beginning is "neither, they are the same."