Główna
Math Puzzles, Volume 1: Classic Riddles and Brain Teasers in Counting, Geometry, Probability, and...
Math Puzzles, Volume 1: Classic Riddles and Brain Teasers in Counting, Geometry, Probability, and Game Theory
Presh Talwalkar
5.0 /
0
Jak bardzo podobała Ci się ta książka?
Jaka jest jakość pobranego pliku?
Pobierz książkę, aby ocenić jej jakość
Jaka jest jakość pobranych plików?
You want to cut a tortilla into 8 pieces. What's the minimum number of cuts you need to make?
Is it statistically harder to guess an iPhone password that uses 3digits or one that uses 4 unique digits?
Two friends agree to meet up in a bar between midnight and 1 am. Each arrives at a random time and will wait 10 minutes for the other to show before leaving. What is the probability the two will meet at the bar? What if they are playing strategically?
The YouTube channel and blog Mind Your Decisions has millions of views for math videos and posts. This ebook is a compilation of 70 of the best puzzles, divided into 25 classic puzzles in counting and geometry, 25 probability puzzles, and 20 game theory puzzles.
Is it statistically harder to guess an iPhone password that uses 3digits or one that uses 4 unique digits?
Two friends agree to meet up in a bar between midnight and 1 am. Each arrives at a random time and will wait 10 minutes for the other to show before leaving. What is the probability the two will meet at the bar? What if they are playing strategically?
The YouTube channel and blog Mind Your Decisions has millions of views for math videos and posts. This ebook is a compilation of 70 of the best puzzles, divided into 25 classic puzzles in counting and geometry, 25 probability puzzles, and 20 game theory puzzles.
Kategorie:
Tom:
1
Rok:
2015
Wydawnictwo:
CreateSpace
Język:
english
Strony:
274 / 270
ISBN 10:
1517421624
ISBN 13:
9781517421625
Plik:
PDF, 1.75 MB
Twoje tagi:
Ściągnij (pdf, 1.75 MB)
 Otwórz w przeglądarce
 Checking other formats...
 Konwertować w EPUB
 Konwertować w FB2
 Konwertować w MOBI
 Konwertować w TXT
 Konwertować w RTF
 Przekonwertowany plik może różnić się od oryginału. Jeśli to możliwe, lepiej pobierz plik w oryginalnym formacie.
Zgłoś problem
This book has a different problem? Report it to us
Check Yes if
Check Yes if
Check Yes if
Check Yes if
you were able to open the file
the file contains a book (comics are also acceptable)
the content of the book is acceptable
Title, Author and Language of the file match the book description. Ignore other fields as they are secondary!
Check No if
Check No if
Check No if
Check No if
 the file is damaged
 the file is DRM protected
 the file is not a book (e.g. executable, xls, html, xml)
 the file is an article
 the file is a book excerpt
 the file is a magazine
 the file is a test blank
 the file is a spam
you believe the content of the book is unacceptable and should be blocked
Title, Author or Language of the file do not match the book description. Ignore other fields.
Are you sure the file is of bad quality? Report about it
Change your answer
Thanks for your participation!
Together we will make our library even better
Together we will make our library even better
Plik zostanie dostarczony na Twój email w ciągu 15 minut.
Plik zostanie dostarczony do Twojego Kindle w ciągu 15 minut.
Uwaga: musisz zweryfikować każdą książkę, którą chcesz wysłać na swój Kindle. Sprawdź swoją skrzynkę pocztową pod kątem emaila weryfikacyjnego z Amazon Kindle Support.
Uwaga: musisz zweryfikować każdą książkę, którą chcesz wysłać na swój Kindle. Sprawdź swoją skrzynkę pocztową pod kątem emaila weryfikacyjnego z Amazon Kindle Support.
Conversion to is in progress
Conversion to is failed
Możesz być zainteresowany Powered by Rec2Me
Najbardziej popularne frazy
puzzle^{399}
probability^{184}
answer to puzzle^{159}
player^{137}
bob^{108}
alice^{103}
winning^{79}
average^{75}
strategy^{73}
percent^{68}
coin^{61}
players^{58}
math^{54}
sum^{47}
one mile^{42}
wins^{41}
infinite^{39}
cards^{39}
games^{39}
permutations^{36}
bananas^{35}
ace^{35}
solve^{33}
pirate^{33}
card^{31}
profit^{30}
units^{30}
cents^{29}
ants^{29}
sell^{28}
outcomes^{28}
logic^{27}
tails^{27}
puzzles^{27}
counting^{27}
trick^{27}
distribution^{26}
credit^{25}
formula^{25}
toss^{25}
solved^{25}
dollars^{25}
follows^{24}
deck^{24}
camel^{24}
calculate^{24}
odds^{24}
string^{23}
flip^{23}
divide^{23}
bottle^{23}
bidders^{23}
cannibal^{22}
shoot^{22}
polynomial^{21}
picks^{21}
grid^{20}
ratio^{20}
rectangular^{20}
first ace^{20}
Powiązane listy książek
0 comments
Możesz zostawić recenzję książki i podzielić się swoimi doświadczeniami. Inni czytelnicy będą zainteresowani Twoją opinią na temat przeczytanych książek. Niezależnie od tego, czy książka ci się podoba, czy nie, jeśli powiesz im szczerze i szczegółowo, ludzie będą mogli znaleźć dla siebie nowe książki, które ich zainteresują.
1

2

Math Puzzles: Classic Riddles And Brain Teasers In Counting, Geometry, Probability, And Game Theory Presh Talwalkar Acknowledgements I want to thank readers of Mind Your Decisions for their continued support. I always loved math puzzles and I'm fortunate for the community of readers that have suggested puzzles to me and offered ingenious solutions. These puzzles are a collection of problems that I have read over the years in books, math competitions, websites, and emails. I have credited original sources when aware, but if there are any omissions please let me know at presh@mindyourdecisions.com About The Author Presh Talwalkar studied Economics and Mathematics at Stanford University. His site Mind Your Decisions has blog posts and original videos about math that have been viewed millions of times. Books By Presh Talwalkar The Joy of Game Theory: An Introduction to Strategic Thinking. Game Theory is the study of interactive decisionmaking, situations where the choice of each person influences the outcome for the group. This book is an innovative approach to game theory that explains strategic games and shows how you can make better decisions by changing the game. Math Puzzles Volume 1: Classic Riddles And Brain Teasers In Counting, Geometry, Probability, And Game Theory. This book contains 70 interesting brainteasers. Math Puzzles Volume 2: More Riddles And Brain Teasers In Counting, Geometry, Probability, And Game Theory. This is a followup puzzle book with more delightful problems. Math Puzzles Volume 3: Even More Riddles And Brain Teasers In Geometry, Logic, Number Theory, And Probability. This is the third in the series with 70 more problems. But I only got the soup! This fun book discusses the mathematics of splitting the bill fairly. 40 Paradoxes in Logic, Probability, and Game Theory. Is it ever logically correct to ask “May I disturb you?” How can a football team be ranked 6th or worse in several polls, but end up as 5th overall when the polls are averaged? These are a few of the thoughtprovok; ing paradoxes covered in the book. Multiply By Lines. It is possible to multiply large numbers simply by drawing lines and counting intersections. Some people call it “how the Japanese multiply” or “Chinese stick multiplication.” This book is a reference guide for how to do the method and why it works. The Best Mental Math Tricks. Can you multiply 97 by 96 in your head? Or can you figure out the day of the week when you are given a date? This book is a collection of methods that will help you solve math problems in your head and make you look like a genius. Why Math Puzzles? I am adding this introductory note in 2015 after completing two sequels to this book. What is the point of all of these math problems? From a practical perspective, math puzzles can help you get a job. They have been asked during interviews at Google, Goldman Sachs, as well as other tech companies, investment banks, and consulting firms. Math puzzles also serve a role in education. Because puzzles illustrate unexpected solutions and can be solved using different methods, they help students develop problem solving skills and demonstrate how geometry, probability, algebra, and other topics are intimately related. Math puzzles are also great for practice once you are out of school. But mostly, math puzzles are worthwhile because they are just fun. I like to share these problems during parties and holidays. Even people who do not like math admit to enjoying them. So with that, I hope you will enjoy working through this collection of puzzles as much as I have enjoyed preparing the puzzles and their solutions. This book is organized into topics of counting and geometry, probability, and game theory. In each section, the puzzles are roughly organized with increasing difficulty. It is never easy to organize puzzles by difficulty: some of the hard puzzles may be easy for you to solve and vice versa. But as a whole, the harder puzzles tend to involve higherlevel mathematics, like knowledge of probability distributions or calculus. Each puzzle is immediately accompanied with its solution. I have never been a fan of how print books put all the solutions at the endit is too easy to peek at the solution for another problem's solution by mistake. In any case, while you are working on a problem, avoid reading the following section which contains the solution. Table Of Contents Section 1: Counting And Geometry Problems Puzzle 1: Ants On A Triangle Answer To Puzzle 1: Ants On A Triangle Puzzle 2: Three Brick Problem Answer To Puzzle 2: Three Brick Problem Puzzle 3: World's Best Tortilla Problem Answer To Puzzle 3: World's Best Tortilla Problem Puzzle 4: Slicing Up A Pie Answer To Puzzle 4: Slicing Up A Pie Puzzle 5: Measuring Ball Bearings Answer To Puzzle 5: Measuring Ball Bearings Puzzle 6: Paying An Employee In Gold Answer To Puzzle 6: Paying An Employee In Gold Puzzle 7: Leaving Work Quickly Answer To Puzzle 7: Leaving Work Quickly Puzzle 8: Science Experiment Answer To Puzzle 8: Science Experiment Puzzle 9: Elevator Malfunctioning Answer To Puzzle 9: Elevator Malfunctioning Puzzle 10: Ants And Honey Answer To Puzzle 10: Ants And Honey Puzzle 11: Camel And Bananas Answer To Puzzle 11: Camel And Bananas Puzzle 12: Coin Tossing Carnival Game Answer To Puzzle 12: Coin Tossing Carnival Game Puzzle 13: Rope Around Earth Puzzle Answer To Puzzle 13: Rope Around Earth Puzzle Puzzle 14: Dividing A Rectangular Piece Of Land Answer To Puzzle 14: Dividing A Rectangular Piece Of Land Puzzle 15: Dividing Land Between Four Sons Answer To Puzzle 15: Dividing Land Between Four Sons Puzzle 16: Moat Crossing Problem Answer To Puzzle 16: Moat Crossing Problem Puzzle 17: Mischievous Child Answer To Puzzle 17: Mischievous Child Puzzle 18: Table Seating Order Answer To Puzzle 18: Table Seating Order Puzzle 19: Dart Game Answer To Puzzle 19: Dart Game Puzzle 20: Train Fly Problem Answer To Puzzle 20: Train Fly Problem Puzzle 21: Train Station Pickup Answer To Puzzle 21: Train Station Pickup Puzzle 22: Random Size Confetti Answer To Puzzle 22: Random Size Confetti Puzzle 23: Hands On A Clock Answer To Puzzle 23: Hands On A Clock Puzzle 24: String Cutting Problem Answer To Puzzle 24: String Cutting Problem Puzzle 25: One Mile South, One Mile East, One Mile North Answer To Puzzle 25: One Mile South, One Mile East, One Mile North Section 2: Probability Problems Puzzle 1: Making A Fair Coin Toss Answer To Puzzle 1: Making A Fair Coin Toss Puzzle 2: iPhone Passwords Answer To Puzzle 2: iPhone Passwords Puzzle 3: Lady Tasting Tea Answer To Puzzle 3: Lady Tasting Tea Puzzle 4: Decision By Committee Answer To Puzzle 4: Decision By Committee Puzzle 5: Sums On Dice Answer To Puzzle 5: Sums On Dice Puzzle 6: St. Petersburg Paradox Answer To Puzzle 6: St. Petersburg Paradox Puzzle 7: Odds Of A Comeback Victory Answer To Puzzle 7: Odds Of A Comeback Victory Puzzle 8: Free Throw Game Answer To Puzzle 8: Free Throw Game Puzzle 9: Video Roulette Answer To Puzzle 9: Video Roulette Puzzle 10: How Often Does It Rain? Answer To Puzzle 10: How Often Does It Rain? Puzzle 11: Ping Pong Probability Answer To Puzzle 11: Ping Pong Probability Puzzle 12: How Long To Heaven? Answer To Puzzle 12: How Long To Heaven? Puzzle 13: Odds Of A Bad Password Answer To Puzzle 13: Odds Of A Bad Password Puzzle 14: Russian Roulette Answer To Puzzle 14: Russian Roulette Puzzle 15: Cards In The Dark Answer To Puzzle 15: Cards In The Dark Puzzle 16: Birthday Line Probability Answer To Puzzle 16: Birthday Line Probability Puzzle 17: Dealing To The First Ace In Poker Answer To Puzzle 17: Dealing To The First Ace In Poker Puzzle 18: Dice Brain Teaser Answer To Puzzle 18: Dice Brain Teaser Puzzle 19: Secret Santa Math Answer To Puzzle 19: Secret Santa Math Puzzle 20: Coin Flipping Game Answer To Puzzle 20: Coin Flipping Game Puzzle 21: Flip Until Heads Answer To Puzzle 21: Flip Until Heads Puzzle 22: Broken Sticks Puzzle Answer To Puzzle 22: Broken Sticks Puzzle Puzzle 23: Finding True Love Answer To Puzzle 23: Finding True Love Puzzle 24: Shoestring Problem Answer To Puzzle 24: Shoestring Problem Puzzle 25: Christmas Trinkets Answer To Puzzle 25: Christmas Trinkets Section 3: Strategy And Game Theory Problems Puzzle 1: Bar Coaster Game Answer To Puzzle 1: Bar Coaster Game Puzzle 2: Bob Is Trapped Answer To Puzzle 2: Bob Is Trapped Puzzle 3: Winning At Chess Answer To Puzzle 3: Winning At Chess Puzzle 4: Math Dodgeball Answer To Puzzle 4: Math Dodgeball Puzzle 5: Determinant Game Answer To Puzzle 5: Determinant Game Puzzle 6: Average Salary Answer To Puzzle 6: Average Salary Puzzle 7: Pirate Game Answer To Puzzle 7: Pirate Game Puzzle 8: Race To 1 Million Answer To Puzzle 8: Race To 1 Million Puzzle 9: Shoot Your Mate Answer To Puzzle 9: Shoot Your Mate Puzzle 10: When To Fire In A Duel Answer To Puzzle 10: When To Fire In A Duel Puzzle 11: Cannibal Game Theory Answer To Puzzle 11: Cannibal Game Theory Puzzle 12: Dollar Auction Game Answer To Puzzle 12: Dollar Auction Game Puzzle 13: Bottle Imp Paradox Answer To Puzzle 13: Bottle Imp Paradox Puzzle 14: Guess The Number Answer To Puzzle 14: Guess The Number Puzzle 15: Guess 2/3 Of The Average Answer To Puzzle 15: Guess 2/3 Of The Average Puzzle 16: Number Elimination Game Answer To Puzzle 16: Number Elimination Game Puzzle 17: Hat Puzzle Answer To Puzzle 17: Hat Puzzle Puzzle 18: Polynomial Guessing Game Answer To Puzzle 18: Polynomial Guessing Game Puzzle 19: Chances Of Meeting A Friend Answer To Puzzle 19: Chances Of Meeting A Friend Puzzle 20: Finding The Right Number Of Bidders Answer To Puzzle 20: Finding The Right Number Of Bidders Section 1: Counting And Geometry Problems The following 25 puzzles deal with classic riddles about counting and geometry. Puzzle 1: Ants On A Triangle Three ants are positioned on separate corners of a triangle. If each ant moves along an edge toward a randomly chosen corner, what is the chance that none of the ants collide? How would the problem generalize if there were n ants positioned on the vertices of a regular ngon, again each moving along an edge to a random adjacent vertex? Answer To Puzzle 1: Ants On A Triangle In order that none of the ants collide, they must all move in the same direction. That is, all of the ants must move in either clockwise or counterclockwise towards a new corner. This can be seen by inductive reasoning: whichever orientation ant 1 picks, ant 2 must pick the same orientation to avoid a collision, and then ant 3 must do the same thing as well. Therefore there are 2 different ways that the ants can avoid running into each other. As each ant can travel in to 2 different directions, there are 23 = 8 total possible ways the ants can move. The probability the ants do not collide is 2/8 = 25%. Extension to general ngon An interesting extension is to ask is: what would happen to 4 ants on the vertices of a quadrilateral? Or more generally, if there are n ants on an ngon? The general problem can be solved by the same logic. Again, the ants can only avoid collision if they all move in the same orientationeither clockwise or counterclockwise. So again there are only 2 safe routes the ants as a group can take. The total number of routes the ants can take is also easy to count. Each ant can choose between 2 adjacent vertices, so there are 2n possibilities. The probability that none of the ants will collide is 2/2n= 1/2n  1 For example, on an 8sided octagon, the probability that none of the ants will collide is a mere 1/128 = 0.0078125, which is less than one percent. For larger polygons it will be rare that the ants do not collide but not impossible. Puzzle 2: Three Brick Problem How can you measure the diagonal of a brick without using any formula, if you have three bricks and a ruler? Answer To Puzzle 2: Three Brick Problem There is a remarkably easy way to find the diagonal. Stack two bricks, one on top of each other, and then place the third brick next to the bottom brick. There is an "empty space" where a fourth brick could be placed. Here is a diagram to illustrate: Now you can measure the length of the diagonal by measuring the length of the empty space using a ruler. No Pythagorean Theorem or geometry formulas are required! Puzzle 3: World's Best Tortilla Problem You start out with a round tortilla. Your job is to divide the tortilla into eight equal pieces, using only cuts made in a straight line. What is the minimum number of cuts you need to make? Answer To Puzzle 3: World's Best Tortilla Problem You only need one cut! If you fold the tortilla in half three times and then make one cut in the middle, you will create 8 equal pieces. In the following diagram, fold along the dotted lines, and then cut along the dark line. I came across this problem when I was making homemade baked tortilla chips. Most instructional cooking videos show people inefficiently making 4 cuts which I found somewhat annoying. Credit: this problem and its title are adapted from The World's Best Puzzles by Charles Townsend. Puzzle 4: Slicing Up A Pie Alice and Bob are preparing for a holiday party, and each has a pie to slice up into pieces. They decide to have a little contest to make things fun. Each person is allowed to make 3 cuts of the pie with a knife, and whoever ends up with more pieces is the winner. They agree stacking is not allowed, but that “center” pieces without the edge crust are permissible. How many pieces can be made using 3 cuts? What about 4 cuts, or more generally n cuts? Answer To Puzzle 4: Slicing Up A Pie With 1 cut, you can create 2 halves. With 2 cuts, you can slice through each half again to make 4 pieces. With 3 cuts, the problem is a bit trickier. Make a cut that intersects with the 2 previous cuts but avoid the point where the previous 2 cuts intersect. Every time you intersect a previous cut you create another section (piece) of the pie, as in the following diagram. So with 3 cuts, you can make 7 pieces in all. We can now generalize. With 1 cut, you can make 2 pieces. After that, the next cut n adds on n new pieces to the pie. Thus, we know that on cut n the total number of pieces can be calculated by the formula: f(n) = 2 + 2 + 3 + 4 + ... + n = 1 + (1 + 2 + 3 + ...) = 1 +n(n + 1)/2 The sequence is 1 more than the sum of numbers from 1 to n, and it is known as the lazy caterer's sequence. Puzzle 5: Measuring Ball Bearings This is a classic puzzle about weighing. You are given a container that contains thousands of ball bearings, amassing to exactly 24 ounces. You have a balance but no weights for the scale. You want to measure exactly 9 ounces. How can you do it? Answer To Puzzle 5: Measuring Ball Bearings If you could count the number of ball bearings, you could get a unit weight for 1 bearing and proceed by counting. But the ball bearings are too numerous, and you can figure it out quicker by using several weighings. Here is one way to do it in five steps. 1. Divide the balls into two equal piles using the balance (12 ounces on each side). 2. Remove the ball bearings from the scale. Divide one of the 12 ounce piles into two equal piles using the scale (6 ounces on each side). 3. Set aside one of the 6 ounce piles. 4. Divide the other 6 ounce pile into two piles (3 ounces on each side). 5. Combine a 3 ounce pile with a 6 ounce pile to get to 9 ounces. Puzzle 6: Paying An Employee In Gold You have a solid gold bar, marked into 7 equal divisions as follows: ––––––– You need to pay an employee each day for one week. He asks to be paid exactly 1 piece of the gold bar per day. The problem is you don't trust him enough to prepay him, and he would prefer not to be paid late. If you can only make 2 cuts in the bar, can you figure out a way to make the cuts so your worker gets paid exactly one gold piece every day? Answer To Puzzle 6: Paying An Employee In Gold You can pay the employee if you cut the pieces in the correct spots. If the gold bar is labeled as follows: 1234567 Then you want to make the cuts between pieces 1 and 2, and between pieces 3 and 4. So now you have pieces: 1 234567 Now you have a 1block piece, a 2block piece, and a 4block piece. Here is how you can pay the employee one piece of gold for each day during the week. Day 1: Give him the 1block piece. Day 2: Trade him the 2block piece for the 1block piece. Day 3: Give him back the 1block piece. Day 4: Trade him the 4block piece for the 1 and 2block pieces. Day 5: Give him the 1block piece. Day 6: Trade him the 2block piece for the 1block piece. Day 7: Give him the 1block piece back. As you can see, the worker will be paid 1 block each day. (Advanced mathematical point: the solution utilizes that 1, 2, and 4 are powers of 2. The payment each day corresponds to day's number encoded into binary. So you can generalize the procedure: you can pay an employee 1 block each day up to 15 days if you had blocks of 1, 2, 4, and 8, and you can pay an employee 1 block each day up to 2n  1 days by breaking a 2n  1 piece solid gold bar into blocks of sizes 1, 2, 4, 8, ..., 2n  1). Puzzle 7: Leaving Work Quickly Alice and Bob were ready to leave the office when their mean boss assigned them the following boring tasks. 1. Manually copy pages from bound books. 2. Audit numbers in a spreadsheet. 3. Fax documents to another office. Each task takes 40 minutes to complete, and only one person can work on a task at a time (the office only has one copy machine, one fax machine, and auditing cannot be done simultaneously). How quickly can they complete their work and go home? Answer To Puzzle 7: Leaving Work Quickly At first thought it seems like the tasks will require 80 minutes: in the first 40 minutes, each does one task, and in the last 40 minutes someone finishes the last task. But let us diagram the chores using something called a Gantt chart which shows what is being done in each interval of time: You will notice in the second 40 minutes that only one person is working while the other is doing nothing. This chart should give us an idea of how to work more efficiently: both people need to be working simultaneously the entire time. So imagine they split up the tasks into 20 minute intervals, and divide the tasks as follows: Very curiously by splitting up one of the tasks (in this case, faxing), they are able to finish all of the work in 60 minutes! In fact this really this should not be too big of a surprise: there are 3 chores that take 40 minutes for a total of 120 minutes. With two people working it should take no more than 60 minutes. This type of problem is based on an old math puzzle about cooking three hamburgers on two grills: see details on page 133 and 134 of this pdf. I never liked this problem as much because you can’t split up the task of grilling a burger: if you start cooking something and let it rest, it will keep cooking even if it is not on the flame. Nevertheless, the mathematical principle is useful for other problems. Puzzle 8: Science Experiment A chemistry teacher offers his class an experiment for extra credit. To complete the lab, students are to keep bacteria in a special chamber for exactly 9 minutes. The sadistic part is the teacher only gives the students 4minute and a 7minute hourglasses with which to measure time. There are no other timemeasuring instruments, as wristwatches and cell phones are confiscated. To complete the lab, the bacteria can be stored in small intervals of time, but the total time that it should be in the chamber must be 9 minutes. Extra credit will only be awarded to the student or students that complete the lab first. What is the shortest time the experiment can be completed? A) 9 minutes B) 12 minutes C) 18 minutes D) 21 minutes Answer To Experiment Puzzle 8: Science The multiple choice setup is a distractor. The experiment can be done in 9 minutes as the hourglasses can be used to measure this amount of time. Here are the steps. Time 0: Turn over both hourglasses. Time 4: Turn over 4 min hourglass when it finishes. Time 7: Turn over 7 min hourglass when it finishes. Time 8: As the 4 min hourglass finishes, turn over 7 min hourglass again (it will have measured 1 minute). Time 9: Take out the sample when the 7 min hourglass finishes. Puzzle 9: Elevator Malfunctioning An elevator in my office building of 65 floors is malfunctioning. Whenever someone wants to go up, the elevator moves up by 8 floors if it can. If the elevator cannot move up by 8 floors, it stays in the same spot (if you are on floor 63 and press up, the elevator stays on floor 63). And whenever someone wants to go down, the elevator moves down by 11 floors if it can. If it cannot, then the elevator stays in the same spot. (if you press down from floor 9, the elevator stays on floor 9). The elevator starts on floor 1. Is it possible to reach every floor in the building? How many times would you have to stop to reach the 60th floor, if you started on floor 1? Answer To Puzzle 9: Elevator Malfunctioning It is possible to reach every floor in the building. In the table below, every floor can be reached by a combination of moving up by 8 floors and moving down by 11 floors. (For simplicity, imagine the elevator only has an “UP” button and a “DOWN” button). The horizontal rows show an elevator moving up by 8 floors at a time, and the vertical columns are when the elevator moves down by 11 floors at a time. You can see that every floor is attainable. The harder part is to see why this actually works. The reason has to do with number theory. We are essentially looking for integers solutions to the following equation: 8x– 11y = floor number These types of equations are known as linear Diophantine equations. For a general equation, ax+by = c, solutions exist if and only if c is a multiple of the greatest common divisor of a and b. In our case, 8 and 11 are relatively prime and have a greatest common divisor of 1, thus there are solutions to the equation. The tricky part is verifying that every floor can be reached without going above floor 65 or going below floor 1, which is what the table above demonstrates. How many times would you have to stop to reach the 60th floor, if you started on floor 1? I got the idea for this question when I noticed floor 60 is the farthest away from floor 1 in the table. I calculated the quickest route to get to floor 60 is to take 24 stops along the way: go across the first row, then move down in a step ladder fashion until you reach the bottom row of the table, and then move across the last row. The floor sequence is: 1, 9, 17, 25, 33, 41, 49, 57, 65, 54, 43, 32, 21, 10, 18, 7, 15, 4, 12, 20, 28, 36, 44, 52, and finally 60. That’s a long way to ride to get to your floor–that floor better hope someone fixes the elevator quickly! Credit: this puzzle is adapted from an Augsburg College math newsletter, volume 17, number 9, February 4, 2004. Puzzle 10: Ants And Honey The shortest distance between two points on a plane is a straight line. But finding the shortest distance on other surfaces is a more interesting problem. Here is a puzzle that is harder than it sounds. In a rectangular box, with length 30 inches and height and width 12 inches, an ant is located on the middle of one side 1 inch from the bottom of the box. There is a drop of honey at the opposite side of the box, on the middle of one side, 1 inch from the top. Here is a picture that illustrates the position of the ant and the honey. Let's say the ant is hungry and wants food quickly. What is the shortest distance the ant would need to crawl to get the honey? Answer To Puzzle 10: Ants And Honey If the ant crawls 1 inch down, then 30 inches across the bottom, then 11 inches up, it will travel 42 inches. But this is not the shortest distance. The solution is found by unfolding the box and then finding the shortest path between the ant and the honey. There are actually several ways to unfold the box depending on how you place the sides. You will find that one of them corresponds to the shortest distance as follows: Now the ant is traveling along the hypotenuse of a right triangle, and its distance can be found using the Pythagorean Theorem. For a triangle with legs 32 and 24, the hypotenuse is 40 inches, and that is the shortest distance for the ant to travel. The problem is concocted because the ant is probably not thinking geometrically. However, experiments have found that ant colonies do optimize their routes when foraging for food. The basic mechanism is ants leave chemical pheromone trails, and shorter paths get reinforced until the colony as a whole finds the shortest path. So this problem is not as strange as it seems! Puzzle 11: Camel And Bananas You want to transport 3,000 bananas across 1,000 kilometers. You have a camel that can carry 1,000 bananas at most. However, the camel must eat 1 banana for each kilometer that it walks. What is the largest number of bananas that can be transported? Answer To Puzzle 11: Camel And Bananas The camel cannot make a single trip with 1,000 bananas as it would eat all of them during the trip. Therefore, the bananas must be transported in shifts. With 3,000 bananas, the camel will need to double back at least two times to carry the three different heaps of 1,000 bananas. To carry the initial heap by 1 kilometer, the camel will need to make 5 trips and eat 5 bananas as follows: Carry 1,000 bananas for 1 kilometer and leave them there (eats 1 banana). Return 1 kilometer to the beginning (eats 1 banana). Carry the next 1,000 bananas for 1 kilometer and leave them there (eats 1 banana). Return again 1 kilometer to the beginning (eats 1 banana). Carry the remaining bananas for 1 kilometer (eats 1 banana). Notice that after moving 1 kilometer, the camel has eaten 5 of the bananas. This process can be repeated and the camel will slowly transport and eat the bananas at the rate of 5 bananas per kilometer. But after 200 kilometers, something important happens. At this point, the camel will have eaten 200 x 5 = 1,000 bananas, leaving just 2,000 remaining. Because the camel can carry 1,000 bananas at a time, the camel will only need to double back once. To carry the remaining bananas by 1 kilometer, the camel will only need to eat 3 bananas as follows: Carry 1,000 bananas by 1 kilometer and leave them there (eats 1 banana). Return 1 kilometer to the beginning (eats 1 banana). Carry the remaining bananas by 1 kilometer (eats 1 banana). The second leg therefore requires just 3 bananas per kilometer. How long will this be necessary? Notice that after 333 1/3 kilometers, the camel has devoured another 1,000 bananas. At this point, there are just 1,000 bananas left: the camel can make the remaining journey without doubling back. This means the camel can carry all the remaining 1,000 bananas and complete the trip. How much of the trip remains? The camel went 200 kilometers and then 333 1/3 kilometers, so there are 466 2/3 kilometers remaining. Thus, the camel will devour 466 2/3 bananas to complete the journey, meaning 533 1/3 bananas can survive and be transported. Here is a visual representation of the journey: On the one hand, the camel only ends up transporting about 17.8 percent of the original 3,000 bananas. On the other hand, it's impressive that some bananas can be transported at all given the camel needs 1 banana per kilometer and can only carry 1,000 bananas at a time. Puzzle 12: Coin Tossing Carnival Game In a carnival game, you are to toss a coin on a table top marked with a grid of squares. You win if the coin lands without touching any lines–that is, the coin lands entirely inside one of the squares, as pictured below. If the squares measure 1.5 inches per side, and the coin has a diameter of 1 inch, what is the chance you will win? Assume you can always get the coin to land somewhere on the table. Extension: find a formula if the squares measure S inches per side and the coin measures D inches in diameter. Answer To Puzzle 12: Tossing Carnival Game Coin The correct answer for this game is 1/9. Let us solve the general case to see why. For the coin not to intersect any part of the grid, it must be the case that the circle's center is located sufficiently far enough away from the grid lines. These are all winnable points. We can find the area of the winnable points and divide that by the total area of a square from the grid to calculate the probability of winning. Here is a diagram that can help. The winning points are the square with side S – D. This is found because the circle's center must be more than D/2 distance from each side of the edge of a gridline. In order to be D/2 from two opposite sides, the circle's center must lie in a square with side S  2 (D/2) = S – D. The area of the square for winning points is (S – D)2. The area of a square for a gridline is S2. The probability of winning is the ratio of these areas, which is [(S D)/S]2. For a square of 1.5 inches, and a circle of diameter 1 inch, we find the probability of winning is ((0.5)/1.5)2 = 1/9. Puzzle 13: Rope Around Earth Puzzle This is a fun problem that first appeared in a 1702 book written by the philosopher William Whiston. This problem is about two really, really long ropes A and B. Rope A is long enough that it could wrap around the Earth’s equator and fit snugly, like a belt (let’s say 25,000 miles). Rope B is just a bit longer than rope A. Rope B could wrap around the Earth equator from 1 foot off the ground. How much longer is rope B than A? (Assume the earth is a perfect sphere.) Extension: let’s say that rope C can wrap around an equatorial line for a sphere that’s as big as the planet Jupiter (about 273,000 miles). Rope D is just a bit longer, and it can do the same thing from 1 foot off the ground. How much longer is rope D than C? Answer To Puzzle Around Earth Puzzle 13: Rope The surprising part is that both questions have the same answer! To see why, suppose that r is the radius of the Earth. Then, according to the setup, the larger rope B would have a radius of r + 1. We can calculate how much longer rope B is by subtracting the circumferences of the two circles. The larger rope has circumference 2π(r + 1) and the smaller rope has a circumference of 2πr. 2π(r + 1) – 2πr = 2π = about 6.28 feet Therefore, rope B is longer by 6.28 feet. But notice the remarkable thing: the answer does not depend on the radius of the circle! This means we have solved the problem for any size sphere (or one might say for every planet or spherically shaped object). Hence, for Jupiter, rope D is also longer than C by about 6.28 feet. Puzzle 14: Dividing A Rectangular Piece Of Land A father is splitting up land between his two sons. How can he divide the land fairly? One approach is to split the land evenly. But even this method can get complicated if we add some realistic assumptions. This puzzle illustrates why splitting land can be a mindboggling exercise. Suppose your father owns a rectangular piece of land, but the city has bought a small rectangular patch of it for public use. You and your brother are to split up the land equally using only a single straight line to divide the area. How can this be done? As a bit of history, this puzzle was sometimes used as an interview brain teaser or technical question at Microsoft. It is sometimes stated in the following terms: how can you split in half a rectangular piece of cake, with a small rectangular piece removed, using a single cut from a knife? Answer To Puzzle 14: Dividing A Rectangular Piece Of Land The elegant mathematical solution requires knowing some geometry. The trick is that any line passing through the center of a rectangle bisects its area. This is because a line through the center of a rectangle either creates two equal trianglesif it is a diagonalor it creates two equal trapezoids or rectangles. The original rectangular plot of land has infinitely many lines passing through the center that bisect its area. But once you remove a small rectangular plot, there is only one line that bisects the areanamely, the line that passes through the centers of both rectangles. This line bisects both the original plot and the removed rectangular plot, and consequently splits the land evenly. Another creative solution method was thought up by one of the Mind Your Decisions readers. Joe explained how he solved the puzzle on the spot. "I was asked this question during a recent job interview. My way of coming up with a solution was to rephrase the original puzzle by replacing rectangles with circles  i.e., a circle within a circle. When looking at the puzzle in this way, it's more intuitive to see a line connecting the two centers being the best answer, and then you can extend the analogy to the rectangles." Now that's employing some out of the box thinking. Puzzle 15: Dividing Land Between Four Sons This is one of my alltime favorite puzzles. Give it an honest effort before reading the answer. A father dies and wants to divide his land evenly amongst four sons. The plot of land has the following unusual shape: How can you divide the land into four equal parts, using only straight lines? Answer To Puzzle 15: Dividing Land Between Four Sons I came across this puzzle when it was presented to gifted math students. Several of the high school students then were able to come up with the following solution. I feel like this is the type of solution one might come up with–it is symmetric and somehow “makes sense.” One of the students had shown a lot of creativity in his work. He came up with the above solution, but he also submitted a second answer that definitely took me by surprise. Here's the solution that he came up with: It is amazing to see how the shape can be divided into four parts using scaled down versions of itself! Well done if you came up with this answer on your own. I had wondered what it would be like if the process was repeated: that is, if you continue to divide the subdivisions into 4 small versions of itself. One reader of Mind Your Decisions, V Paul Smith, took up the challenge and did a manual tessellation that is beautiful. Visit the following page to see the tessellation: http://dl.dropbox.com/u/3990649/Tesselation 01.jpg Puzzle 16: Moat Crossing Problem A rectangular castle is surrounded by a rectangular moat that measures 20 feet in width: see image below. You have two planks of 19 feet each, but no way to nail them together. How can you cross the moat if you start from the outside of the moat and want to reach the castle? Extension: what’s the largest rectangular moat you can cross from the outside with two planks of length L? Answer To Puzzle Crossing Problem 16: Moat You can cross the moat by arranging one plank along the corner of the moat, and putting the other on top, as follows: As you can check, the planks will cover a distance of 28.5 feet across the diagonal, which measures just a tad less at 28.3 feet. Thus, you have just enough plank to cross. Using geometry, we can figure out the largest rectangular moat that can be traversed with two planks of length L. Consider the planks in optimal position with one plank across a corner and the other plank in its center, as in the following diagram. We want to solve for the largest vertical distance that this configuration can cover. The plank at the top covers a diagonal distance of L, which is at most a vertical distance of L/√2 if the plank is the hypotenuse of an isosceles right triangle. The other plank also covers a maximal vertical distance if it is the hypotenuse of an isosceles right triangle. The vertical distance in this triangle is (L/2)/ √2. The longest total vertical distance is the sum, which is: L/√2 + (L/2)/√2. Puzzle 17: Mischievous Child At a dinner party, there are two large bowls filled with juice. One bowl holds exactly 1 gallon of apple juice and another has 1 gallon of fruit punch. A mischievous child notices the bowls and decides to have a little fun. The child fills up a ladle of apple juice and mixes it into the bowl with fruit punch. Not content to stop here, he decides to do the reverse. He fills up a ladle of the fruit punch/apple juice mixture and returns it to the apple juice bowl. The child would proceed further, but his mother notices what he is doing and makes him stop. The child apologizes to the hosts, who decide to shrug off the matter as little harm was done. But an interesting question does arise about the two mixtures of juice. In the end, each bowl of juice ended up with some of the other juice. The question is: which bowl has more of the other juice? That is, does the fruit punch bowl have more apple juice or does the apple juice bowl have more fruit punch? Assume the ladle holds a volume of 1 cup and the juices were mixed thoroughly when the child transferred the juices. Answer To Puzzle 17: Mischievous Child The hard way to solve this problem is by considering the concentration of juices in each bowl. You can calculate that both juice bowls end up with an equal concentration of the other juice, and thus the transferred volumes must be equal. The easier way is to think logically. Notice that both bowls begin and end up with exactly 1 gallon of liquid. This means that whatever apple juice ended up in the fruit punch bowl must have been replaced by the same volume of fruit punch that went into the apple juice bowl. Therefore, the two volumes must be equal! The problem is known as the wine/water puzzle. Here is a nice detailed explanation online at Donald Sauter's website: wine/water problem solution. Puzzle 18: Table Seating Order A table seat choice can be the difference between a boring, wasted night and a fun, profitable one. I can recall two examples where seat choice made a big difference. The first was a studentfaculty dinner at Stanford where I had invited a math professor. The etiquette was to accompany a professor while getting food and walk to a table. The natural instinct, therefore, was to sit directly next to the invited professor. But this was a bad choice, as it was difficult to make eye contact and direct conversation. It also led to awkward moments where students spilled food and drinks on their professor. Lesson learned: always sit across the table! The second came in a friendly poker game. After playing a few times, we quickly learned the importance of seating order, particularly when betting in nolimit Texas Hold’em. We have since paid careful attention to rotate seats for fairness. The games led to a natural question: exactly how many different betting orders are possible? That is, how many ways can people sit around a table, if only their relative position matters? Answer To Puzzle Seating Order 18: Table There are a handful of ways to determine the answer. Here are a few that I like. Method 1: Converting permutations linear permutations into circular The case of two people is trivial: there is only one way. How many ways can three people sit around a table? One way is to count permutations. The easiest type of permutation to count is a “linear” list. Say the people around the table are sitting as person A, then person B, and finally person C. We can represent this order in a linear list as ABC. Using this notation, we can count the number of possible lists. We note there are: 3 possible choices for the first spot (A, B, or C) 2 choices for the second 1 choice for the last spot This means there are 3 x 2 x 1 = 6 = 3! ways to write the list. Specifically the list can be written as: ABC ACB BAC BCA CAB CBA But this list is not our answer. At least some of these permutations represent the same seating order on a circular table. We can see this graphically: The image above shows that the list orders ABC and CAB are the same arrangement on a circular table. So we ask: what’s the relation between linear permutations and the circular ones we wish to count? The relationship can be illustrated as follows: Evidently, each circular permutation for a threeperson group can be written in 3 different ways. This makes sense: for each circular permutation, there are 3 different choices for the first letter of the linear permutation representation. Thus, we can convert the number of circular permutations into linear ones by multiplying by 3. Or working in reverse, we can convert the number of linear permutations into circular ones by dividing by 3. Combining all of this, we can deduce there are 3! / 3 = 2 ways to seat three people on a table. (The orderings are ABC and ACB.) We can expand this logic to more people. We first count the number of linear permutations and then convert to circular ones. For four people, the number of linear permutations can be counted. There will be 4 choices for the first spot, 3 choices for the second, 2 choices for the third, and 1 choice for the last. Therefore there will be 4 x 3 x 2 x 1 = 4! linear permutations. We can then convert this into the number of circular permutations. As there are 4 people in the group, there will be 4 ways that each circular permutation can be written as a linear permutation–any of the four people can be written first in the list. So now to convert linear into circular we divide by 4 (again the number of people in the group). Thus there will be a total of 4! / 4 = 6 ways to seat this group. To generalize even further, we can see a pattern for n people. We can write the linear permutation in n! ways, but we have to divide by n to convert the linear permutations into circular ones. In the end, the formula simplifies as: Seating orders = n!/n = (n  1)! And viola, we have our answer. Method 2: induction An alternate way of solving this problem is mathematical induction. Listing out a few cases of two, three, and four suggests the general formula (n – 1)! Now we can prove it. Consider a group of n – 1 people who sit around a table in a restaurant. Let’s say at the very last minute one extra person comes. How many ways can the group be seated? By the induction hypothesis, we know there are (n – 2)! ways for the initial group to sit. Where can the additional person sit? For any of these (n – 2)! arrangements, he can obviously sit between the first and second person, or between the second and third, or so on until the last position of being between the n – 1 person and the first person. There are a total of n – 1 spots he can sit for any of those (n – 2)! arrangements. Multiplying the possibilities gives the total number of arrangements as follows: Seating orders = (n  2)!(n  1) = (n  1)! And like mathemagic, induction proves the formula. Method 3: seatchanging permutations A final way I like to visualize the answer is a partygame type approach. Consider for a moment that n people have sat at a circular table. How many ways can they switch seats and have at least one person sitting with different neighbors on left and right sides? This is another way of asking the number of circular permutations, so the answer to this question will answer our original question. Some ways people switch will obviously not change the seating order. If everyone moves one seat to the right, then each person has the same neighbors and so the seating arrangement is the same. Such rotations do not change the order of seating. And this demonstrates a principle: motion is always relative to a reference point. To count the number of distinct seat trades, we must have a fixed reference point. Without loss of generality, we can choose any one person to be a reference point. With one person firmly seated, every unique linear ordering of the remaining people change seats will be a unique circular permutation. In other words, we want to know the number of linear permutations for n  1 people. The answer is (n – 1)! and we’ve arrived at the answer again. Puzzle 19: Dart Game Alice and Bob play the following game with their friend Charlie. Charlie begins the game by secretly picking a spot on the dartboard. The spot can be anywhere on the board, but once picked it does not change. Then Alice and Bob each get to throw one dart at the board. At this point, Charlie reveals the position he initially picked. The winner of the game is the person whose dart is closest to the spot Charlie picked. For example, if Charlie picked the spot marked with an “x”, and Alice and Bob shot as follows, then Alice would win the game: Put yourself in the shoes of Alice or Bob. What strategy is best for playing this game? Answer To Puzzle 19: Dart Game The best strategy is fairly intuitive: Alice and Bob should each shoot for the center of the dartboard. One way to think about this is probabilistically. Because Charlie is essentially picking a random position anywhere on the board, the best spot to pick would be the average position, which is the center of the dartboard. Another way to think about this is geometrically. Suppose Alice hits the center of the dartboard and Bob hits somewhere else. We can ask: what is the set of all points that are closer to Alice’s dart than to Bob’s? The answer can be found by remembering a fact from geometry. The set of all points that are equidistant from Alice’ and Bob’s darts is defined by the perpendicular bisector between the two points (the line that goes through the midpoint of the segment joining the two points and intersects perpendicularly). The perpendicular bisector separates all the points that are closer to the different darts. All the points to one side of the perpendicular bisector are closer to Alice’s dart, and all the points on the other side are closer to Bob’s. If Alice hits the center, and Bob hits anywhere else, then the perpendicular bisector will always be some chord of the circle not going through the center. Geometrically, there will be more points closer to Alice’s dart than to Bob’s dart. Therefore Alice’s dart "covers more ground" and she will have a higher chance of winning the game. In the following diagram, all points to the left of the perpendicular bisector are closer to Alice’s dart, and that covers more than half the board. Locational games like this can prove useful in military or business settings when two competing parties need to position themselves closer to an unknown target (consider two hostile nations, one trying to capture and another trying to protect a terrorist hiding out in an unknown location). This dart game is also a twodimensional version of Hotelling’s game, in which two hot dog vendors compete to locate closer to customers on a beach. In that game too it is the best strategy for each vendor to locate centrally. I explain more about this game in my book The Joy of Game Theory: An Introduction To Strategic Thinking. Puzzle 20: Train Fly Problem This is another classic math puzzle. Two trains that are 60 miles apart are headed towards each other. Each train is moving at 30 miles per hour. A speedy fly travels at 60 miles per hour and leaves from the front of one train directly towards the other train. When it gets to the front of the other train, it instantly turns back towards the original train. This continues until the moment the two trains pass each other, at which point the fly stops. The question is, how far did the fly travel? Answer To Puzzle 20: Train Fly Problem The story goes this puzzle was asked to polymath John von Neumann at a party. He quickly gave the right answer. When asked if he knew the trick, he replied, "What trick? I just summed up the infinite series." The trick is to think about the problem in terms of speed and time. The distance the fly travels can then be obtained by multiplying those two quantities. We know the fly travels at 60 miles per hour, so we have its speed. Let’s figure out the time. The two trains are 60 miles apart, and they are traveling towards each other at 30 miles per hour each, to make for a combined speed of 60 miles per hour. Therefore, the trains will meet in 1 hour (both trains will have traveled 30 miles to the center). Since the fly was moving for 1 hour at 60 miles per hour, that means the fly must have traveled 60 miles in all! That's the answer! Note this calculation ignores the actual flight path of the fly, which is precisely the trick. Solving the problem using infinite series is much harder. Consider the first time the fly meets a train coming the other way. The fly and train together move at 90 miles per hour. They will cover 60 miles in 2/3 of an hour. This means the fly has covered 40 miles while each train has covered 20 miles. Now the fly turns around. When will it meet the other train? The problem is exactly the same as before, except the trains are at a distance of 20 miles, which is 1/3 of the original distance. Since all the speeds are the same, the time and distance will be 1/3 of the quantities of the previous round. So the fly travels 1/3 of 40, which is 16 2/3. By extension, the third round will be the same as the second round except the initial distance is shrunk by 1/3. So the fly will travel 1/3 the distance of the previous round. Similarly, in every subsequent round, the fly will also travel 1/3 the distance of the previous. So the fly travels an infinite series with a starting term of 40 and a common ratio of 1/3. The total distance is: 40(1 + 1/3 + 1/9 + 1/27 + ...) = 40(3/2) = 60 miles. This is the same answer as before, but clearly the calculation was much harder! I don’t know anyone who could have done the infinite series using mental math–heck, it’s hard enough on paper. But von Neumann’s calculating abilities were so impressive that it was actually plausible. Puzzle 21: Train Station Pickup Mr. Smith is normally picked up at the train station at 5 o'clock. His driver starts from home appropriately so he arrives exactly on time. One day Mr. Smith arrived to the train station early at 4 o'clock. Instead of waiting around, he decided to walk home and meet the driver along the way (the driver keeps the same schedule). Mr. Smith arrived home 20 minutes earlier than he normally would. On another day, Mr. Smith arrived early at 4:30 and again decided to walk home and meet the driver along the way. How much earlier than normal did he arrive at home? Answer To Puzzle 21: Train Station Pickup The first time I solved the problem I wrote out several equations and solved for everything algebraically. When I figured out the answer, I realized the puzzle can be solved much easier! When Mr. Smith arrived at the train station 1 hour early, and started walking home, he was able to save 20 minutes of commute. This is due to two reasons: the driver met him closer to home (by 10 minutes), and the drive home was shorter (by 10 minutes). So if Mr. Smith arrives 30 minutes early, or half of 1 hour, we can deduce he only traverses half the distance as before. Thus, the time savings are halved: he meets the driver closer to home by 10/2 = 5 minutes, and he drive home is shorter by 10/2 = 5 minutes. Therefore, Mr. Smith arrives home 10 minutes ahead of schedule. Credit: puzzle from Laura Taalman's problem of the week. Puzzle 22: Random Size Confetti Professor X teaches a probability class. He assigns a holidaythemed project to his students. Each student is to create 500 rectangularshaped confetti pieces, with length and width to be random numbers between 0 and 1 inch. Alice goes home and gets started. She interprets the assignment as follows. Alice generates two random numbers from the uniform distribution, and then she uses the first number as the length and the second as the width of the rectangle. Bob interprets the assignment differently. He instead generates one random number from the uniform distribution, and he uses that number for both the length and width, meaning he creates squares of confetti. Clearly Alice and Bob will cut out different shapes of confetti. But how will the average size of the confetti compare? That is, will the average area of the shapes that Alice and Bob cut out be the same? If not, whose confetti will have a larger average area? Answer To Puzzle 22: Random Size Confetti Let X be a random variable with a uniform distribution. Bob takes one realization of X, so the area he cuts out will be distributed as X2, and the expected area is E(X2). Alice instead takes two realization of X. The area she cuts out will be E(X)E(X), or [E(X)]2. The difference between Bob's expected area and Alice's is: E(X2)  [E(X)]2 = Var(X) ≥ 0 The difference between Bob's expected areas and Alice's is equal to the variance of X, which is always a nonnegative number. Notice this formula holds for random variables of other distributions too, like normal distributions or discrete distributions. In the case of the uniform distribution from 0 to 1, the variance is 1/12. So Bob's areas will tend to be at least as large as or larger than Alice's. So Bob may need a little bit more paper than Alice when cutting his confetti. Puzzle 23: Hands On A Clock The long minute hand of a very accurate timepiece points exactly at a full minute, while the short hour hand is exactly two minutes away. What times of day could it be? Answer To Puzzle 23: Hands On A Clock The trick is realizing there are limited times that the hour hand lands exactly on one of the minute markings. Since the hour hand moves from one hour number marking to the next (5 minute markings) in a span of 60 minutes, that means the hour hand is only on minute markings every 12 minutes of the hour, corresponding to the minute times 00, 12, 24, 36, and 48. From here it is just an exercise in trial an error to figure out the right times. If the minute hand is at 00, the hour has to be near 11, 12, or 1 to solve the puzzle. But in these times the two hands are separated by either 5 or 0 markings. For the minute hand at 12, the candidate time would have the hour nearby at the number 2. But at 2:12, the hour hand has moved one marking, and the minute hand is two markings past the number 2. The two hands are separated by just one minute marking. We can proceed to figure out the minute hand at 24 will work. If the minute hand is at 24, the candidate hour hand would be nearby at 4. We can check 4:24 exactly works: the hour hand is 2 markings past the clock "4", and the minute hand is 4 markings past the clock "4". You can also check the next candidate time of 7:36 is also a solution. Finally, you can check that the minute hand at 48 does not work. So the two times are 4:24 and 7:36, either am or pm. Puzzle 24: String Cutting Problem An interviewer gives you a string that measures 4 meters in length. The string is to be cut into two pieces. One piece is made into the shape of a square, and the other into a circle. See the picture below. Your job is to make the total enclosed area as large as possible. The interviewer hands you a piece of paper and a pencil so you can do the math (you only get one chance to cut the string so you want to be sure your first attempt is correct). 1. How should you cut the string to maximize the area? If you are able to figure out the answer, the interviewer has a couple followup questions to test your skills. 2. How should you cut the string if you want to minimize the enclosed area? 3. Imagine the string is cut randomly. What is the average value of the enclosed area? (When you cut the string, there is one piece to the left of the cut and another to the right. Suppose the left piece is always made into a circle and the right into a square) Answer To Puzzle Cutting Problem 24: String 1. How should you cut the string to maximize the area? This is something of a trick question. For a given length, the circle is the shape that encloses the largest area. So you want to make the whole string be the circle. (This is known as the isoperimetric inequality and it is not a trivial thing to prove!) As you must cut it into two pieces, you should try to cut as close to one end as possible to make the rectangle small. 2. How should you cut the string if you want to minimize the enclosed area? This can be solved using calculus. Let x be the string made into a circle and so 4  x is the string made into the square. The string length is the circumference/perimeter of the shapes. A circle with circumference x has a radius of x/(2π), which means its area is x2/(4π). Similarly, a square with perimeter 4  x has a side length of 1  x/4, so its area is the square of that. So here is an expression for the area of the circle plus the square. Area(x) = x2/(4π) + (1  x/4)2 We can find the minimum by taking the derivative: Derivative of Area(x) = x/(2π)  (1  x/4)/2 = 0 The above equation is solved when x = (4π)/(4 + π). 3. Imagine the string is cut randomly. What is the average value of the enclosed area? As stated in step 2, the area function is described by the equation: f(x) = x2/(4 π) + (1  x/4)2 We can take the average value by calculating an integral: you integrate the function from 0 to 4 (which gives the area under the curve) and then you divide by the length of the interval (4) to arrive at the average value: Average value = 0.25 integral (f(x), x, 0, 4) Therefore, the average value is about 0.758. Puzzle 25: One Mile South, One Mile East, One Mile North This is a very classic puzzle, a fitting end to the first section. I first read about this in the fun puzzle book How Would You Move Mount Fuji? by William Poundstone. Years ago, Microsoft used to ask this puzzle as an interview question, and this was also a favorite of Elon Musk, a cofounder to PayPal and Tesla Motors. Here is the problem: how many points are there on the earth where you could travel one mile south, then one mile east, then one mile north and end up in the same spot you started? Answer To Puzzle 25: One Mile South, One Mile East, One Mile North This puzzle is much harder than it seems at first. The easy but wrong answer The place that comes to mind is the North Pole. This is, in fact, one of the correct spots. You can trace out the path on a globe. From the north pole, you can move your finger south one mile. From there, you will go east one mile and move along a line of latitude that is exactly one mile away from the north pole. You finally travel one mile north, and you will exactly end up in the north pole. The route you travel will look like a triangle or a piece of pie, as seen in this rough sketch I made: This is one correct answer. But it is not the only one. The harder spots The other spots on the earth all involve traveling near the South Pole. The trick to these solutions is that you end up in the same spot after traveling one mile east. How can that be? One way this is possible is if you are on a line of latitude so close to the South Pole that the entire circle of latitude is exactly one mile around. We will label this circle C(1) for convenience. With this circle in mind, it is possible to figure out a solution. Let us begin the journey from a point exactly one mile north of C(1). Let’s trace out the path of going one mile south, one mile east, and one mile north again. To begin, we travel one mile south to point on the circle C(1). Then, we travel east along the circle C(1), and by its construction, we end up exactly where we began. Now we travel one mile north, and we reach the starting point of the journey, exactly as we wanted. The trip will look something like this rough sketch I made: This demonstrates there is a solution involving a circle near the South Pole. In fact, the circle C(1) is associated with a family of solutions. Any point one mile north of C(1) will be a possible solution. This means the entire circle of latitude one mile north of C(1) is a solution, and so there are an infinite number of solutions associated with the circle C(1)! That alone seems remarkable. But what is more interesting is that there are even more solutions. The circle C(1) was special because we traversed it exactly once, and ended up where we started after walking one mile east. There are other circles with the same property. Consider the circle C(1/2), a similarly defined circle of exactly 1/2 mile in circumference. Notice that traveling one mile east along this circle will also send us back to the starting point. The only difference is that we will have traversed the circle two times! Thus we can construct solutions using the circle C(1/2). We start one mile north from C(1/2) and every point along this line of latitude is a solution. There is an infinite number of solutions associated with the circle C(1/2). Naturally, we can extend this process to more circles. Consider the circle C(1/3), similarly defined with exactly 1/3 mile in circumference. It would be traversed three times if we travel one mile east along it, and we would end in the same spot we started from. This circle too will have an infinite set of solutions–namely the line of latitude one mile north of it. To generalize, we can construct an infinite number of such circles. We know the circles C(1), C(1/2), C(1/3), C(1/4), … C(1/n), … will be traversed exactly n times if we travel one mile east along them. And there are corresponding starting points on the lines of latitudes one mile north of each of these respective circles. In summary, there are an infinite number of circles of latitudes, and each circle of latitude contains an infinite number of starting points. The correct answer, therefore, is one point at the North Pole, plus two infinite sets of points of circles near the South Pole. (To be precise in the language of set theory, the set of circles C(1), C(2), etc. is countably infinite, while the number of points on each circle is uncountably infinite.) Section 2: Probability Problems Life is often said to be a game of chance. The following 25 puzzles deal with probability. Puzzle 1: Making A Fair Coin Toss Alice and Bob play a game as follows. Alice spins a coin on a table and waits for it to land on one side. If the result is heads, Alice wins $1 from Bob; if tails, Alice pays $1 to Bob. While the game sounds fair, Bob suspects the coin may be biased to land on heads more. The problem is he cannot prove it. Being diplomatic, Bob does not accuse Alice of trickery. Instead, Bob introduces a small change in the rules to make the game fair to both players. What rule could Bob have come up with? Answer To Puzzle 1: Making A Fair Coin Toss Bob worries the coin may be biased to land on heads more often than tails. The trick Bob comes up with is a way to turn a biased coin into one that produces having fair tosses. John von Neumann, the mathematician who solved the trainfly problem in his head, suggested the following procedure: 1. Spin the coin twice. 2. If the two results are different, use the first spin (HT becomes “heads”, and TH becomes “tails”). 3. If the two results are the same (HH or TT), then discard the trial and go back to step one. In other words, Bob has redefined the payout rule to ensure the odds are fair to both parties. Why does the von Neumann procedure work? The reason is HT and TH are symmetrical outcomes and occur with equal probability. To see this, suppose the outcome heads occurs with probability 0.6 and tails with probability 0.4. Then we can directly calculate the probability of the pairs as: –HT occurs (0.6)(0.4) = 0.24 –TH occurs (0.4)(0.6) = 0.24 These events are equally likely, and hence both players have an even chance of winning the game. The von Neumann procedure takes advantage that each coin flip is an independent event, and so both mixed pairs of tosses will have equal chances. Appendix: spinning vs tossing Observant readers may have noticed the game is about coin spinning rather than coin tossing. Why the distinction? It’s a small bit of trivia that coin tossing is not easily biased. When the coin is in the air, the law of conservation of angular momentum suggests the coin would spin at nearly a constant rate and spend equal amounts of time facing heads up and heads down, meaning heads and tails are equally likely. (See Teacher’s Corner: You Can Load a Die, But You Can’t Bias a Coin). The theory is only slightly modified in reallife. In practice, there is still a small bias in coin flips. A famous academic paper, Dynamical Bias In The Coin Toss, by Stanford Professors Persi Diaconis and Susan Holmes and UC Santa Cruz Professor Richard Montgomery, points out coin flipping is almost always slightly biased. A few of the results are: A coin that is tossed and caught has about a 51% chance of landing on the same face as when it was launched. (If it starts out as heads, there’s a 51% chance it will end as heads). A coin that is spun can have a large bias, up to 80 percent, for landing towards the heavier side down. A coin lands on its edge around 1 in 6000 throws, creating a flipistic singularity. The lesson is that coin flips are better than coins being spun. But a coin flip can still exhibit some bias, so to be fair, it may be best to use the von Neumann procedure or another choice mechanism (like a computer random number generator). Puzzle 2: iPhone Passwords Originally iPhones asked for 4 digits in a passcode. My friend wondered about the combinatorics of a good password. Presh, reallife question for you: What is the safest way to lock my iphone? Let me explain. A friend unlocked his phone once and I grabbed it and said "so, 9,6,0, and 1, huh?" because the bulk of "tap prints" were on those numbers and, I rightly presumed, correlated to his password. He freaked out because were I a thief, I could unlock his phone pretty easily as I'd know all four numbers and that they are only used once each within the fourdigit code. Not terribly safe, is it? So when setting my password, I opted to repeat a number (e.g. 1231). That way, someone would look at my phone and even if they could figure the three numbers I use, they would either have to guess at the fourth number (which doesn’t exist) or, should they rightly figure out that I only use three independent numbers, they would have to try all possible permutations of those three different numbers within a fourdigit code. Here's the puzzle: is it harder to guess a password that uses only 3digits or one that uses a 4 distinct digits? Would it be harder to guess if one only used a passcode containing 2digits? Answer To Passwords Puzzle 2: iPhone It is harder to guess a passcode that uses 3 digits with 1 repeated digit than one that has either 4 unique digits or one that uses only 2 unique digits. Let's get into the math to see why. We need a way of counting possible passwords. The easiest case is when someone uses 4 unique numbers for the 4digit passcode. Each number is used exactly once in the passcode, and hence the problem reduces to counting the number of ways to rearrange 4 objects. This is solved by counting the number of permutations. For a password using 4 digits, there are exactly 4! = 4 x 3 x 2 x 1 = 24 ways to have this kind of password. But what happens when you have a password like 1231? That is, how can you count passwords in which one or more numbers are used multiple times? You have to count the number of combinations. The way to solve this is by using an extension of permutations known as the multinomial coefficient. The multinomial coefficient is calculated as the total number of permutations divided by terms that account for nondistinct or repeated elements. This is a methodical way to avoid doublecounting identical elements. If an element appears k times (i.e. has a multiplicity of k), then they can be rearranged in k! ways, which means we will divide by k! to account for the multiplicity. A simple example can illustrate the method. Let’s say we want to figure out the number of distinct ways to rearrange the letters in the word MISSISSIPPI. There are 11 letters but some of the letters are repeated. There are 1 Ms, 4 Is, 4 Ss, and 2 Ps. The number of distinct rearrangements of the letters is the number of permutations (11!) divided by the factors for the elements accounting for their multiplicity (1! x 4! x 4! x 2!). The multinomial coefficient is thus 11!/(1! x 4! x 4! x 2!) = 34,650. Am I helping myself by using three numbers in a fourdigit code? There are 4! = 24 possible ways a password can be formed from four distinct and known numbers. Will using only 3 numbers increase the number of possibilities? The surprising answer is that yes, it does. It seems counterintuitive at first so let’s go through an example. Suppose you see an iPhone where the “tap prints” are on the numbers 1, 2, and 3. How many possibilities are there for the fourdigit password to unlock the phone? There’s a simple observation needed to go on. In order that three numbers are all used in a fourdigit password, it must be the case that some digit is used twice. Perhaps the number 1 appears twice, or the number 2, or the number 3. Suppose the number 1 is used twice. How many passwords are possible? We can use the multinomial coefficient to figure it out. We know the total number of permutations is 4! and we must divide by 2! to account for the number 1 being used twice. Thus, there are 4! / 2! = 24 / 2 = 12 different passwords. We can list these out: 1123 1132 1213 1312 1231 1321 2113 2131 2311 3112 3121 3211 But we are not done yet. We must similarly count for the cases in which the number 2 is used twice, or the number 3 is used twice. By symmetry it should be evident that each of those cases yields an additional 12 passwords. To summarize, there are 12 passwords when a given number is repeated, and there are three possible numbers that could be repeated. In all, there are 12 x 3 = 36 passwords. This is more than the 24 passwords when using four distinct numbers. This trick of using three numbers does in fact increase the set of possible passwords. While each case of three digits only gives 12 passwords, the gain to this method is that the other person doesn’t know which number is repeated. And so they have to consider all 36 possibilities. Would it be even safer if I only mixed two independent numbers? If 3 is better than 4, then is 2 better than 3? Unfortunately it is not. There is just not enough variety when using 2 numbers. The gain in ambiguity of multiplicity is simply not enough to counteract the lack of passwords. With two distinct numbers, there are only 14 possible passwords. This is found since the 2 numbers either have multiplicities as (1, 3), or (2, 2) or (3, 1). We can add up the multinomial coefficients to get 4! / (1! x 3!) + 4! / (2! x 2!) + 4! / (3! x 1!) = 4 + 6 + 4 = 14. We can also list them out: 1112 1121 1211 2111 1222 2122 2212 2221 1122 1221 2211 1212 2121 2112 In conclusion, using 2 numbers ends up reducing the possible number of passwords. Additional ways to help If that weren’t enough, my friend actually brainstormed a couple of other ways to improve the password. "Actually now I can think of all kinds of brilliant maneuvers… like using three digits but tapping a phantom fourth number once the code is entered…. so there are four “tap prints” but only three which are relevant! Or, by the same measure, you could use four independent numbers and then tap a fifth time to have five options for four spaces." I think these are interesting possibilities too, but they hit me as a little less practical since you’d have to diligently tap those extra numbers to make the smudge marks. I’ll leave it to you to figure out how many passwords those methods will yield. Perhaps an equally valuable suggestion is to clean the touchscreen intermittently to erase the finger print marks. Puzzle 3: Lady Tasting Tea The problem is based on an incident at a 1920s tea party in Cambridge. The story goes a lady claimed the ability to distinguish between a cup of tea made by pouring tea into a cup of milk versus a cup of tea made by pouring milk into a cup of tea. Not surprisingly many were skeptical, and one person decided test it out. He created an experiment with 8 tea cups, consisting of 4 cups of each preparation. The lady was remarkably able to identify all 8 cups, raising the issue of whether she just got lucky. What are the odds that the lady identified all 8 cups by chance? The problem is known as the Lady Tasting Tea, and it brought about the more modern analysis of testing random experimental data. Answer To Puzzle 3: Lady Tasting Tea This is a classic question of combinations. We know there are 8 items, of which 4 are of one type and 4 of another. Therefore there are "8 choose 4" = 8!/(4!4!) or 70 possible combinations. The probability of identifying all of the cups by random chance is a mere 1/70 (around 1.4 percent). So it seems the lady likely had a refined palette and actually did have this skill. Puzzle 4: Decision By Committee Imagine you face a very difficult decision and there is a low probability of making the right choice. (Assume the probability of success is p < 0.50.) What would you rather do: ask a single person to decide or instead send it to a threeperson group where the majority choice wins? Assume each person in the threeperson committee is independently voting, with each having the same chance of determining the correct decision. Answer To Puzzle 4: Decision By Committee You are better off letting a single person decide. The situation can be modeled using probability. We can each person has an independent probability p of making choice. Since the problem is difficult, we will say p < 0.5. each person is equally likely to choose among three possible alternatives). say that the right (Imagine or more What’s the success of the individual versus the group? The individual is easy: the probability of making the right decision is p. The threeperson group is a little harder. The group will find the right answer whenever two or more of the people vote for the right option. Since each person can vote “right” or “wrong,” there are 8 possible ways to vote: RRR RRW RWR RWW WRR WRW WWR WWW The first, second, third, and fifth items listed are the 4 ways the group can come to the right decision. Adding the probabilities for these events gives the chance the group will come to the correct decision. When all three are right, RRR, that is p3. When two are right, say RRW, that is p2(1p) and there are three such events like this. The probability that a majority finds the right decision is the sum of these events, which is p3+3p2(1p) = 3p2 – 2p3 Since p < 0.5, we can see this final expression is less than p. In the following chart, the dotted line shows the probability the committee comes to the right decision is less than the probability an individual finds the right decision. The moral: committees may not be the best for making tough choices! That’s not to say committees are useless. They can help to diffuse risk and are useful for the purpose of brainstorming (which may increase the odds of success over an individual). But this does show committees are illsuited for the type of hard problem they are meant to address. Puzzle 5: Sums On Dice With two dice, you can roll a 10 in two different ways: you can either roll 5 and 5, or you can roll 6 and 4. Similarly, you can roll a sum of 5 in two different ways: as the rolls and 1 and 4, or as 2 and 3. But the two events "roll a 10" and "roll a 5" will not occur with equal frequency. Why not? Answer To Puzzle 5: Sums On Dice The trick is all about the wording of the puzzle which creates a mystery where there is none. The sum 10 can be obtained in three ways by dice roll: namely (5,5), (4,6), and (6,4). The sum 5 can be obtained in four ways: (1,4), (4,1), (2,3) and (3,2). So the sum 10 is obtained with probability 3/36 versus the sum 5 with probability 4/36. Pictorially: The puzzle demonstrates that it’s always important to consider the events in probability. Sly wording can easily confuse. Credit: I read this in the book Luck, Logic, and White Lies. Puzzle 6: St. Petersburg Paradox You are offered an unusual gamble. A fair coin is tossed until the first heads appears, which ends the game. The payoff to you depends on the number of tosses. The payoff starts at 2 dollars and doubles on each successive toss. That means you get 2 dollars if the first toss is a head, 4 dollars if the first toss is a tails and the second is a heads, 8 dollars if the first two tosses are tails and the third is a head, and so on. In other words, you get paid 2k where k is the number of tosses for the first heads. The question to you is how much should you be willing to pay to play this game? In other words, what is a fair price for this game? Answer To Puzzle Petersburg Paradox 6: St. The typical way to answer this question is to compute the expectation (or the “average”) of the payouts. This is done by multiplying the various payouts by their probability of occurrence and adding it up. To say it another way, the payouts are weighted by their likelihood. The respective probabilities are easy to compute. The chance the first toss is a heads is 1/2, the chance the first toss is a tails and the second is a heads is (1/2)(1/2), and the third toss being the first heads is (1/2)(1/2)(1/2), so the pattern is clear that the game ending on the k toss is (1/2)k. So with probability 1/2 you win 2 dollars, with probability 1/4 you win 4 dollars, with probability 1/8 you win 8 dollars and thus the expectation is: The surprising result is the expectation is infinity. This means this game–if played exactly as described–offers an infinite payout. With an astronomical payout, a rational player should logically be willing to pay an astronomical amount to play this game, like paying a million dollars, a trillion dollars, and so on until infinity. The fair price of infinity is paradoxical because the game does not seem like it is worth much at first. Few would be willing to pay more than 10 dollars to play this game, let alone 100 dollars or 1,000 dollars. But expectation theory seemingly says that any amount of money is justifiable. Banks should be willing to offer loans so people could play this game; venture capital firms should offer more money than they do to startups; individuals should be willing to mortgage their house, take a cash advance on their credit card, and take a payday loan. What’s going on here? Why is the expectation theory fair price so different from common sense? It turns out there are a variety of explanations. Resolution 1: Payouts should be realistic Imagine you are playing this game with a friend. You hit a lucky streak. The first nine tosses have been tails and you’re still going. If the tenth toss is a heads, then you get 1,024 dollars as a payout. If it’s a tails, you have a chance to win 2,048 dollars, and even more. At this point your friend realizes he’s made a mistake. He thought he’d cash out with your 10 dollar entry fee, but he now sees he cannot afford to risk any more. He pleads with you to stop. He’ll gladly pay you the 512 dollars you’ve earned–so long as you keep this whole bet a secret from his wife. What would you do in this situation? Most of us would take the cash and show some mercy here. There is no joy in winning if it means crippling a friend financially. And this concocted scenario leads to one of the unrealistic assumptions of the St. Petersburg paradox. In the hypothetical coin game, you’re supposed to believe the other side can pay out infinitely large sums of money. It doesn’t happen often, but if you get to 20 coin tosses, you fully expect to be paid 1,048,576 dollars. This is unrealistic if you’re playing with a friend or even a really, really rich friend. It might be possible with a casino, but even a casino may have a limited bankroll. The truth is that payouts cannot be infinite. If such a game were to exist in our reality, there must be a maximum, finite payout. This means the expectation is not an infinite sum but rather a finite sum of several terms. Depending on the size of the bankroll, the St Petersburg gamble has a finite payout. I will spare you the details, but here are a few examples of the expectation when using a maximum payout using numbers from a Wikipedia table for illustration: (small note: these calculations are based on payouts of 1, 2, 4, etc. so it's slightly different than the game I set up of 2, 4, 8, etc.) As you can see, expectation theory now implies the fair price of the game is something like 25 dollars or less. With a more realistic model of the game, the expectation result matches common sense. This should settle matters for anyone concerned with reality and practice, but there are people who don’t accept this explanation. Such philosophers think an infinite payout is possible and so the paradox still exists. So for these people, I will offer the following alternate resolution that does not rely on limiting the bankroll. Resolution 2: diminishing marginal utility A quantity like 1,000 dollars has meaning to most people. If you were to ask a friend for such a loan, they would ask how you can pay it back, what you would use it for, and so on. But there are times when 1,000 dollars seems to lose its value. I like to think about the show Deal or No Deal where contestants play a multistage lottery to win 1,000,000 dollars. At various points in the game the contestants can either keep pursuing the big prizes or they can accept smaller consolation prizes. As the prospect of a big prize increases, the contestants start to care less and less about smaller prizes like 1,000 dollars. This is an example of the famous concept of diminishing marginal utility–the idea that at larger levels of consumption, incremental units are worth less. The concept is applicable for wealth decisions because at some point incremental earnings mean less to a person. What this means for the St. Petersburg Paradox is that the payouts should be altered. The payouts should not be measured in dollars but rather as the utility that wealth will provide. One way to model this is to use a logarithm function. Instead of saying the payout for the first toss is 2 dollars, we will say it is log(2) units of utility, and accordingly for the other payouts. Using a log utility function, the St Petersburg game now has a finite payout. First we derive an expression for the expected utility. E = (1/2)log(2) + (1/4)log(4) + (1/8)log(8) + ... E = (1/2)log(2) + (1/4)log(22) + (1/8)log(23) + ... E = (1/2)log(2) + (2/4)log(2) + (3/8)log(2) + ... Now we let u = log(2). We will subtract half of the expectation from itself. E = (1/2)u + (2/4)u + (3/8)u + ... (1/2) E = (1/4)u  (2/8)u  ... So (1/2) E = (1/2)u + (1/4)u + (1/8)u + ... Now we complete the derivation. (1/2) E = u[(1/2) + (1/4) + (1/8) + ...] (1/2) E = u E = 2u = 2 log 2 < ∞ This is a small payout but the actual quantity does not matter: it is just that the payout is less than infinity, showing again, that there is no real paradox here. Puzzle 7: Odds Of A Comeback Victory Consider two teams A and B that are completely evenly matched. Given that a team is behind in score at halftime, what is the probability that the team will overcome the deficit and win the game? Assume there are no ties, and the result of the first half does not affect how players perform in the second half (that is, the first and second half are taken to be independent events). Answer To Puzzle 7: Odds Of A Comeback Victory Because the teams are evenly matched, you might mistakenly think the answer is 50 percent. But that is the probability the team would win overall. If a team is down at halftime, the chances of winning will be less. So let us try to calculate the odds. We have to think about how a team could have a comeback victory if it is down at halftime. Let us first write down the possible outcomes of the game, broken down by halves. Since the two teams are evenly matched, there are four different possibilities for who is leading during each half (ignore the case of a tie): (first half, second half): AA AB BA BB Because the teams are evenly matched, these events are all equally likely so each occurs with probability 1/4 = 25 percent. In two of the cases, one team scores more points in both halves of the game, and there is no come from behind victory: AA and BB. This means 50 percent of the games the team that lags behind at half ends up losing the game. The other two possibilities are times when a team could have a comeback victory. In these cases, one team leads at the half, but gets outscored by the other in the second half: AB and BA. In order for a team to get a comeback victory, it must overcome the deficit from the first half. How often does that happen? The answer can be calculated by the following logic: since the two teams are evenly matched, it is equally likely that the team will score enough points to overcome the deficit or that it will not score enough points. (For instance, the event of falling behind 6 points in one half happens with the same probability of gaining 6 points in a half). Therefore, in the event AB, it will be equally likely that B scores enough to eventually win, or that it would not score enough and it loses. Therefore, B ends up winning in half of the cases, or 12.5 percent of the time (take 1/2 of 25 percent). The same logic applies for the event BA: there is a 12.5 percent chance that team A ends up winning. Putting this all together, we have: Probability(team having comeback victory) = P(AB)Pr(B wins) + Pr(BA)Pr(A wins) = 12.5 + 12.5 = 25 percent So under these assumptions, a team will have a 1 in 4 chance of making a comeback victory. Now you may point out this is not realistic as the model does not take into account quality of teams and things like home field advantage. Nor does it take into account psychology: a recent study shows that teams with a slight deficit at halftime end up winning more often than teams with a slight edge at halftime. The study is called Can Losing Leads to Winning? by Jonah A. Berger and Devin G. Pope. The result is based on 18,000 professional basketball games and 45,000 college games. However, even though the assumptions are a bit off, the overall league statistics seem to mirror the probability model. In the National Football League, a small sample of games in 2005 showed this trend that teams behind at halftime had about a 23 percent chance of winning. A similar pattern was found in the National Basketball League in 1992 where the comeback probability was about 25. This is either a pure coincidence or there is something to be said about the simple probability model. It's fascinating to me either way. Credit: this puzzle is based on a problem appearing on page 11, “Probability: the Language of Randomness,” by Jeffry S. Simonoff. Puzzle 8: Free Throw Game Alice and Bob agree to settle a dispute by shooting free throws. The game is simple: they take turns shooting, and the first one to make a shot wins. Alice makes a shot with probability 0.4 while Bob makes his shots with 0.6. To compensate for the skill difference, Alice gets to shoot first. Is this a fair game? Extension: if Alice makes a shot with probability p and Bob with probability q, for what values of p and q would the game be fair? Solve if q = 1 – p. Answer To Puzzle 8: Free Throw Game There are many methods to solving the probabilities of winning. The one I like is a technique of backwards induction. The free throw game seems hard to figure out because a round could end with no one making a shot, and then the game would continue. Solving for the winning probability seems like you'd need to use an infinite series. But that's not the case. The trick is seeing that each round is really an independent subgame. The fact that the previous round ended without a winner does not affect the winner of the current round or any future round. This means we can safely ignore outcomes without winners. The probability of winning depends only on the features of a single round. This simplifies the problem to a more tractable one. So now, assume that one of the players did win in a round, and then calculate the relative winning percentages. We can use a little trick to visualize the problem. Because Alice makes a shot with probability 0.4, and Bob with 0.6, we can imagine the two are not shooting free throws but instead rolling a 5 sided die. Let's say that Alice makes her shot for rolling the numbers 1 and 2, and Bob makes his shot for the other three numbers 3, 4, and 5. So Alice wins if she rolls one of her winning numbers. If she does not, then Bob gets a chance to roll and he wins the game for rolling his numbers. All other combinations of the rolls mean they both miss their shots, so the round is a draw and they go again. Here is a diagram illustrating the outcomes of a round, illustrating the events for which Alice will win: To calculate the winning percentage, we can simply count out the number of ways that Alice wins. In the grid, there are 10 squares that she wins, and only 9 that Bob wins. Therefore, Alice wins with probability 10/19 = 53 percent and Bob with probability 9/19 = 47 percent. Although Bob is a better shooter, Alice has a slight edge in the game because she gets to shoot first. Answer to extension: generalizing the probabilities The numbers we used made it convenient to convert the game into rolling a 5sided die. But we can generalize the process. Notice that Alice won on 0.4 percent of the squares, which is the same as her shooting percentage. The percentage of squares for when either person won the game was 0.76, which is equal to the chances Alice makes her shot (0.4) or she misses her shot (1  0.4) and Bob makes his (0.6). The sum of this is 0.4 + (1  0.4)0.6. Thus the probability Alice wins a game is: (SP for shooting percentage) (Alice's SP) / (Alice's SP + (1  Alice's SP)(Bob's SP)) If we say that Alice's SP is p and Bob's is q, then this becomes: p / (p + (1  p)q) The game is fair if this term equals 0.5. Skipping some of the algebra, this simplifies to: (p  q)  pq = 0 We can plot out all values for which this equation is true, remembering that p and q are probabilities so they are between 0 and 1. The dotted line corresponds to setting the condition q = 1  p. If we give the additional restriction that q = 1  p, then we can uniquely solve that p is about 0.382, which is plotted above. So Alice at 0.4 shooting percentage is just a tad higher than the fair shooting percentage of 0.382. Puzzle 9: Video Roulette Bob loves the TV show Law & Order. Each day he picks an episode at random and watches it. Given there are 456 episodes of the show, how many days will it take Bob to watch the entire series on average? Extension: Figure out a formula for a show that has n episodes. Answer To Roulette Puzzle 9: Video Consider smaller cases to get an idea. If a series has just 1 episode, it will take 1 day to watch the entire series. What about 2 episodes? On the first day, Bob will watch one of the episodes. How long will it take him to watch the remaining episode on average? We can solve for the number of days N as a sum of two conditional events. If he picks the episode he has not seen (with probability 0.5), then the conditional expectation is 1 day. If he instead picks the episode he has seen, then he essentially loses a day, and he is back to the starting point–so the expectation is N + 1. In other words, N = (1)Pr(picks episode he has not seen) + (N + 1)Pr(picks episode he has seen) N = (1)0.5 + (N + 1)(0.5) = 0.5 N + 1 N=2 Note that it takes Bob 2 days on average to watch the unique episode that he picks with probability 1/2. In other words, if an event occurs with probability p, it takes a time of 1/p to observe the event. Thus, it takes Bob an average of 3 days (1 day for the first episode, 2 days for the second) to watch a series with 2 episodes. Solution We can think about the problem in terms of rolling a die. Each day Bob picks a new episode randomly is essentially like Bob rolling a die where each face represents an episode number. The question is: how many times on average must a 6sided die be rolled until all sides appear at least once? The first roll can be any of the faces. On the second roll, there are 5 remaining unique faces out of 6. Using the logic above, we can conclude it will take an average of 1 / (5/6) = 6/5 rolls until one sees a different face. We continue the logic to calculate the number of rolls until a new face. As there are 4 remaining out of 6, this will take 6/4 rolls on average. Continuing the logic, we can conclude the total number of rolls it will take on average to reveal every face at least once is: 1 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 147/10 = 14.7 In other words, for a series with 6 episodes, it will take Bob about 15 days to watch every episode. For a series with n episodes, the similar series is: For n = 456, this sum is roughly 3,056. For very large n, the series sum is roughly (n) times ln(n)–though this approximation for 456 yields 2,792 so it is a very rough approximation. Puzzle 10: How Often Does It Rain? In Mathland, the weather is described either as sunny or rainy, nothing in between. On a sunny day, there is an equal chance it will rain on the following day or be sunny. On a rainy day, however, there is a 70 percent chance it will rain on the following day versus a 30 percent chance it will be sunny. How often does it rain in Mathland, on average? Answer To Puzzle 10: How Often Does It Rain? The answer is it rains about 62.5 percent of the time. We can solve it by considering the expected weather after each state. Let R denote the average proportion of rainy days and S of sunny days. Using the law of total probability, we know that: R = E(rains tomorrow  sunny today)Pr(sunny today) + E(rains tomorrow  rainy today)Pr(rainy today) We can now use a clever trick. On average, the probability it is sunny or rainy on a particular day is S and R, respectively. And we also know a day is either sunny or rainy, so S = (1R). Hence we get the following: R = E(rains tomorrow  sunny today)(1R) + E(rains tomorrow  rainy today)R We can simplify this because we know the rules of weather. The first conditional expectation is 50 percent and the second is 70 percent. R = 0.5(1R) + 0.7(R) This can be solved to find out R = 0.625. Puzzle 11: Ping Pong Probability Suppose A and B are equally strong ping pong players. Is it more likely that A will beat B in 3 out of 4 games, or in 5 out of 8 games? Answer To Puzzle 11: Ping Pong Probability It is surprisingly more likely that A will beat B in 3 out of 4 games than in 5 games out of 8. This can be verified by considering the binomial probability distribution. The equation for A winning exactly r games out of n is "n choose r" times 0.5n. We can calculate the chance of A beating B in exactly 3 games out of 4 is 25% and the odds of A winning exactly 5 games out of 8 is 7/32, or roughly 21.8%. Why is this the case? The counterintuitive part is the wording of the question. If we instead consider A to win at least 3 out of 4 games, or at least 5 out of 8 games we have a different situation. In that case, we find that the probability of winning 3 or more games out of 4 increases to 31.25%. All we need to do is add the probability of winning exactly 3 games out of 4, which equals 25%, to the probability of winning all 4 games, which is (.5)4 = .0625, or 6.25%. The probability of winning 5 or more games out of 8 is equal to 0.21875 + 0.1094 + 0.0312 + 0.0039 = 0.3632, or 36.32%. So in this problem it's important that we want to know A is winning exactly a certain number of games, rather than winning at least some number of games. Credit: this is a problem in Challenging Mathematical Problems with Elementary Solutions, Volume 1 by A.M. Yaglom and I.M. Yaglom. Puzzle 12: How Long To Heaven? A person dies and arrives at the gates to heaven. There are three identical doors: one of them leads to heaven, another leads to a 1day stay in limbo, and then back to the gate, and the other leads to a 2day stay in limbo, and then back to the gate. Every time the person is back at the gate, the three doors are reshuffled. How long, on the average, will it take the person to reach heaven? Answer To Puzzle 12: How Long To Heaven? Let N denote the average number of days it takes to get to heaven. The trick to solve for N is to rewrite the average using symmetry of the game. N is equal to the average number of days regardless of which door you enter first. This splits up into three cases: Case 1: Onethird of the time you go directly to heaven, and that’s 0 days. Case 2: Onethird of the time you pick the door that adds 1 day. In this case, you end up in heaven in N + 1 days. Case 3: The remaining onethird you pick the door that adds 2 days. In this case, you end up in heaven in N + 2 days. These observations lead to the following equation and answer: N = Pr(door 1)(time door 1) + Pr(door 2)(time door 2) + Pr(door 3) (time door 3) N = (1/3)0 + (1/3)(N + 1) + (1/3)(N + 2) N = (1/3)N + 1/3 + (1/3)N + 2/3 N = (2/3)N + 1 (1/3)N = 1 N=3 The average amount of time is 3 days. Puzzle 13: Password Odds Of A Bad This is a problem that I was asked by a reader of my blog. A system has 100 accounts, two of which have bad passwords (let’s call these bad accounts). If someone could only test 20 accounts, what are the chances that one will net at least a bad account? Extensions: 1. What is the probability of netting both bad accounts in the sample of 20? What about exactly one bad account? 2. What is the probability of netting a bad account if you have k bad accounts, there are N total accounts, and you can sample n accounts at one time? 3. Go back to the problem with 100 accounts, and 2 bad accounts. Suppose you can vary how many accounts you can sample. If you want a 50 percent chance of netting a bad account, what’s the minimum sample size needed? (use a numerical method to estimate) Answer To Puzzle 13: Odds Of A Bad Password The sampling of accounts is done without replacement, so this is an example of the hypergeometric distribution. The same problem can be restated as follows: if you are drawing 20 balls from an urn of 98 white balls and 2 black balls, what are the chances of drawing at least 1 black ball? We will solve for the chance of drawing only white balls. Then the complement event gives the chance of drawing at least 1 black ball. If you choose all 20 white balls from 100, then there are 98 choose 20 ways to choose only white balls, 2 choose 0 ways to choose no black balls. And this is out of a total 100 choose 20 ways to choose all of the balls. (2 choose 0)(98 choose 20)/(100 choose 20) ≈ 64 percent. The complement event gives the chance of choosing at least 1 black ball. 1  (2 choose 0)(98 choose 20)/(100 choose 20) ≈ 36 percent. 1. What is the probability of netting both bad accounts in the sample of 20? What about exactly one bad account? We continue to use the same counting technique to solve the rest of the problems. If we want to get both bad accounts, then there are 2 choose 2 ways to draw the 2 black balls, 98 choose 18 ways to choose the remaining white balls, and this is again out of 100 choose 20 ways to choose the balls. (2 choose 2)(98 choose 18)/(100 choose 20) = 19/495 or about 4 percent Similarly, here is the probability for getting exactly one bad account. (2 choose 1)(98 choose 19)/(100 choose 20) = 32/99 or about 32 percent 2. What is the probability of netting a bad account if you have k bad accounts, there are N total accounts, and you can sample n accounts at one time? We can generalize the counting procedure. We compute the chance of getting no bad accounts and then take the complement. This is: 1  (k choose 0)([N  k] choose n)/(N choose n) 3. Go back to the problem with 100 accounts, and 2 bad accounts. Suppose you can vary how many accounts you can sample. If you want a 50 percent chance of netting a bad account, what’s the minimum sample size needed? I used a numerical method to vary the sample size and found out the answer is 30. It's interesting that you only need to sample about a third of the population to have a better than even chance of finding both bad accounts. Puzzle 14: Russian Roulette Can probability theory save your life? Perhaps not in usual circumstances, but it sure would help if you found yourself playing an unusual game. Let’s play a game of Russian roulette. I am holding a gun with six empty chambers that I load with a single bullet. I close the cylinder and spin it. I point the gun to your head and, click, it turns out to be empty. Now I’m going to pull the trigger one more time and see if you are really lucky. Which would you prefer, that I spin the cylinder first, or that I just pull the trigger? Answer To Puzzle 14: Russian Roulette The problem can be solved by calculating the probability of survival for the choices. First, consider the odds of survival if the cylinder is spun. The cylinder is equally likely to stop at any of the six chambers. One of the chambers contains the bullet and is unsafe. The other five chambers are empty and you would survive. Consequently, the probability of survival is 5/6, or about 83 percent. Next, consider the odds if the cylinder is not spun. As the trigger was already pulled, there are five possible chambers remaining. Additionally, one of these chambers contains the bullet. That leaves four empty or safe chambers out of five. Thus the probability of survival is 4/5, or 80 percent. Comparing the two options it is evident that you are slightly better off if the cylinder is spun. Credit: I’m not sure of the original source of this puzzle, but it appears in William Poundstone’s book How Would You Move Mount Fuji? Puzzle 15: Cards In The Dark You are given a pack of cards that has 52 cards in a completely dark room. Inside the deck there are 42 cards facing down, 10 cards facing up. Your task is to reorganize the deck into two piles so that each pile contains an equal number of cards that face up. Remember, you are in the darkness and can’t see. How can you do it? Answer To Puzzle 15: Cards In The Dark Take any ten cards from the original deck. Create a new deck by flipping over each card one by one. T