Główna
Math Puzzles Volume 2: More Riddles And Brain Teasers In Counting, Geometry, Probability, And Game...
Math Puzzles Volume 2: More Riddles And Brain Teasers In Counting, Geometry, Probability, And Game Theory
Presh Talwalkar
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?
What is a better fit: a square peg in a round hole, or a round peg in a square hole?Your music player seems to be playing the same songs over again. Is there something wrong with the shuffle feature, or might the songs be playing randomly?You have 100 dimes, and I have 99 pennies. At the same time, we will toss our coins in the air and let them fall on the floor. Then we meticulously count the outcomes of our tosses. You win if you show more heads than I do. What’s the probability that you will win?The YouTube channel and blog Mind Your Decisions has blog posts and original videos about math that have been viewed millions of times. The problems in this book are based on some of the best puzzles in counting, geometry, and probability and game theory.
Kategorie:
Rok:
2015
Wydawnictwo:
CreateSpace Independent Publishing Platform
Język:
english
Strony:
240 / 170
ISBN 10:
1517531624
ISBN 13:
9781517531621
Plik:
PDF, 1.94 MB
Twoje tagi:
Ściągnij (pdf, 1.94 MB)
 Otwórz w przeglądarce
 Checking other formats...
 Konwertuj na EPUB
 Konwertuj na FB2
 Konwertuj na MOBI
 Konwertuj na TXT
 Konwertuj na 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
Wybierz Tak, jeśli
Wybierz Tak, jeśli
Wybierz Tak, jeśli
Wybierz Tak, jeśli
udało ci się otworzyć plik
plik zawiera książkę (dozwolone są również komiksy)
treść książki jest akceptowalna
Tytuł, autor i język pliku odpowiadają opisowi książki. Zignoruj inne pola, ponieważ są one drugorzędne!
Wybierz Nie, jeśli
Wybierz Nie, jeśli
Wybierz Nie, jeśli
Wybierz Nie, jeśli
 plik jest uszkodzony
 plik jest chroniony DRM
 plik nie jest książką (np. xls, html, xml)
 plik jest artykułem
 plik jest fragmentem książki
 plik jest czasopismem
 plik jest formularzem testowym
 plik jest spamem
uważasz, że treść książki jest nieodpowiednia i powinna zostać zablokowana
Tytuł, autor lub język pliku nie pasuje do opisu książki. Zignoruj inne pola.
Are you sure you want to report this book? Please specify the reason below
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.
Trwa konwersja do
Konwersja do nie powiodła się
Możesz być zainteresowany Powered by Rec2Me
Najbardziej popularne frazy
puzzle^{469}
answer to puzzle^{203}
percent^{95}
bob^{87}
probability^{72}
cards^{65}
solve^{63}
sum^{59}
card^{58}
alice^{57}
coin^{56}
coins^{51}
rectangle^{50}
dice^{48}
math^{36}
triangle^{33}
apples^{32}
toss^{31}
pairs^{31}
strategy^{31}
balls^{31}
average^{31}
piles^{30}
songs^{28}
inscribed^{28}
hot sauce^{28}
percent chance^{27}
squares^{26}
puzzles^{25}
trick^{25}
chooser^{22}
guesser^{22}
infinite^{21}
cylinder^{21}
radius^{20}
cake^{20}
logic^{20}
guessing^{20}
tower^{20}
deck^{20}
flip^{20}
rolls^{20}
loses^{19}
ace^{19}
guesses^{19}
equation^{19}
formula^{19}
procedure^{19}
geometry^{18}
choices^{18}
winning^{17}
weigh^{17}
hats^{16}
stickers^{16}
yards^{16}
peg^{15}
courses^{15}
triangles^{15}
traveler^{15}
multiply^{15}
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 Volume 2: More Riddles And Brain Teasers In Counting, Geometry, Probability, And Game Theory 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 thoughtprovoking 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 volume 3 of the math puzzles series. 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. Each puzzle is immediately accompanied with its solution. I have never been a fan of how print books put all the solutions at the end—it 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. This book is organized into topics of counting, geometry, and 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. Table Of Contents Section I: Counting Puzzle 1: 3 Lamps Answer To Puzzle 1: 3 Lamps Puzzle 2: Famous Logic Puzzle Answer To Puzzle 2: Famous Logic Puzzle Puzzle 3: Lost Money To A Buyer Answer To Puzzle 3: Lost Money To A Buyer Puzzle 4: A Friend Puzzle Answer To Puzzle 4: A Friend Puzzle Puzzle 5: Family Crossing A River Answer To Puzzle 5: Family Crossing A River Puzzle 6: Losing Weight Answer To Puzzle 6: Losing Weight Puzzle 7: Writing ThankYou Notes Answer To Puzzle 7: Writing ThankYou Notes Puzzle 8: Three Runners Answer To Puzzle 8: Three Runners Puzzle 9: Splitting A Shared Ride Answer To Puzzle 9: Splitting A Shared Ride Puzzle 10: Average Speed Answer To Puzzle 10: Average Speed Puzzle 11: How Far Did I Jog? Answer To Puzzle 11: How Far Did I Jog? Puzzle 12: College Football Title Answer To Puzzle 12: College Football Title Puzzle 13: Pairs Of Cards Answer To Puzzle 13: Pairs Of Cards Puzzle 14: Ways To Eat A Chocolate Bar Answer To Puzzle 14: Ways To Eat A Chocolate Bar Puzzle 15: Flights Around The Country Answer To Puzzle 15: Flights Around The Country Puzzle 16: Order Of Eating Courses Puzzle 16: Answer To Order Of Eating Courses Puzzle 17: Hot Sauce Answer To Puzzle 17: Hot Sauce Puzzle 18: Wardrobe Choices Answer To Puzzle 18: Wardrobe Choices Puzzle 19: Wedding Seating Arrangement Answer To Puzzle 19: Wedding Seating Arrangement Puzzle 20: A Fun Baseball Inequality Answer To Puzzle 20: A Fun Baseball Inequality Puzzle 21: 12 Balls, 3 Weighings Answer To Puzzle 21: 12 Balls, 3 Weighings Puzzle 22: Guessing A “Lost” Number Mathemagic Answer To Puzzle 22: Guessing A “Lost” Number Mathemagic Puzzle 23: Piles Of Coins Answer To Puzzle 23: Piles Of Coins Puzzle 24: Piles Of Coins (Continuous Version) Answer To Puzzle 24: Piles Of Coins (Continuous Version) Puzzle 25: A Fun Math Sequence Answer To Puzzle 25: A Fun Math Sequence Section II: Geometry Puzzle 1: Make A Rectangle Answer To Puzzle 1: Make A Rectangle Puzzle 2: Clock Division Answer To Puzzle 2: Clock Division Puzzle 3: Fitting A Square Peg In A Round Hole Answer To Puzzle 3: Fitting A Square Peg In A Round Hole Puzzle 4: Inscribed Rectangle Answer To Puzzle 4: Inscribed Rectangle Puzzle 5: Infinitely Many Inscribed Circles Answer To Puzzle 5: Infinitely Many Inscribed Circles Puzzle 6: The Efficient Drink Order Answer To Puzzle 6: The Efficient Drink Order Puzzle 7: Circle Length Answer To Puzzle 7: Circle Length Puzzle 8: Length Of A Spiral Answer To Puzzle 8: Length Of A Spiral Puzzle 9: Ant Cylinder Answer To Puzzle 9: Ant Cylinder Puzzle 10: How Many Faces? Answer To Puzzle 10: How Many Faces? Puzzle 11: Circle Rotation Answer To Puzzle 11: Circle Rotation Puzzle 12: NonOverlapping Triangles Answer To Puzzle 12: NonOverlapping Triangles Puzzle 13: How Many Partners? Answer To Puzzle 13: How Many Partners? Puzzle 14: Crossed Ladders Answer To Puzzle 14: Crossed Ladders Puzzle 15: Fruit Label Stickers Answer To Puzzle 15: Fruit Label Stickers Puzzle 16: Castle Height Answer To Puzzle 16: Castle Height Puzzle 17: Bumper Cars On A Square Answer To Puzzle 17: Bumper Cars On A Square Puzzle 18: Optimize The Fence Answer To Puzzle 18: Optimize The Fence Puzzle 19: Cylinder Height Answer To Puzzle 19: Cylinder Height Puzzle 20: Connect Four Towns Answer To Puzzle 20: Connect Four Towns Section III: Probability And Game Theory Puzzle 1: Which Lane Is Better? Puzzle 1: Answer To Which Lane Is Better? Puzzle 2: Medical Conspiracies Answer To Puzzle 2: Medical Conspiracies Puzzle 3: Cards In Three Piles Answer To Puzzle 3: Cards In Three Piles Puzzle 4: Random Music Answer To Puzzle 4: Random Music Puzzle 5: Buying Fresh Fruit Answer To Puzzle 5: Buying Fresh Fruit Puzzle 6: The Pawn Chase Answer To Puzzle 6: The Pawn Chase Puzzle 7: Who Will Toss More Heads? Answer To Puzzle 7: Who Will Toss More Heads? Puzzle 8: Wrong Diagnosis? Answer To Puzzle 8: Wrong Diagnosis? Puzzle 9: A Dice And Coin Game Answer To Puzzle 9: A Dice And Coin Game Puzzle 10: A Four Dice Game Answer To Puzzle 10: A Four Dice Game Puzzle 11: Which Card Will Be Revealed? Puzzle 11: Answer To Which Card Will Be Revealed? Puzzle 12: The Three Coin Puzzle Answer To Puzzle 12: The Three Coin Puzzle Puzzle 13: Cake Cutting Answer To Puzzle 13: Cake Cutting Puzzle 14: Spreadsheet Random Numbers Answer To Puzzle 14: Spreadsheet Random Numbers Puzzle 15: Unloading Deliveries Answer To Puzzle 15: Unloading Deliveries Puzzle 16: Statistical Independence Answer To Puzzle 16: Statistical Independence Puzzle 17: Lost Child Answer To Puzzle 17: Lost Child Puzzle 18: Snowball Puzzle Answer To Puzzle 18: Snowball Puzzle Puzzle 19: Election Rule Change Answer To Puzzle 19: Election Rule Change Puzzle 20: Rolls Before Repeat Answer To Puzzle 20: Rolls Before Repeat Puzzle 21: Hat Guessing Answer To Puzzle 21: Hat Guessing Puzzle 22: Playing With A Loaded Die Answer To Puzzle 22: Playing With A Loaded Die Puzzle 23: Auctioning Off A Gift Card Answer To Puzzle 23: Auctioning Off A Gift Card Puzzle 24: Higher Or Lower Answer To Puzzle 24: Higher Or Lower Puzzle 25: What Do An Infinite Tower, A Classic Physics Problem, And Coin Flipping Have In Common? Answer To Puzzle 25: What Do An Infinite Tower, A Classic Physics Problem, And Coin Flipping Have In Common? Section I: Counting These problems are generally about the number of ways to do things, but there are a few algebra and logic problems included as well. Puzzle 1: 3 Lamps In front of you are 3 switches, each of which operates a lamp in another room not visible to you. Your job is to identify which switch operates which lamp. You are allowed to operate the switches, but you can only visit the other room once. How can you identify which switch operates which lamp? My friend was asked this problem in an interview for a consulting job. It requires logical thinking and applying a bit of common sense. Answer To Puzzle 1: 3 Lamps Turn on one of the switches for a few minutes. Then turn it off and turn on another switch. When you visit the other room, one lamp will be on. That corresponds to the last switch turned on. Then touch the other two lamps and feel which bulb is warm. That corresponds to the switch you had turned on for a while and then turned off. The last lamp corresponds to the switch you did not touch at all. Puzzle 2: Famous Logic Puzzle This problem was asked in a famous psychological experiment. Four cards are on a table and each has a number written on one side and a color on the other side. The faces of the cards showing are 3, 8, red, and brown. You are told that every card that shows an even number on one side has the color red on the other side. Which cards do you need to flip over to test this rule? Only about 10 percent of subjects got the answer correct. Can you figure it out? Answer To Puzzle 2: Famous Logic Puzzle The cards that need to be flipped over are “8” and “brown”. The rule is only broken if an evencard has another color, or a card with another color has an even number on the other side. So the only cards to check are “8” and “brown.” Here is the logic in more detail when deciding whether each card should be flipped. Flip over 3? The rule states the opposite side of even cards has red. The rule does not say what the opposite of an odd card has. We could have cards with an odd number on one side and red on the other. There is no need to flip 3. Flip over 8? If the rule is true, this card better have red on the other side so “8” should be flipped. Flip over red? The rule states the opposite side of even cards has red. It does not say what the opposite side of red cards has. So if we flip over the red card to find an odd number, that does not break the rule. No need to flip it. Flip over brown? If we flip this card over and find an even number, then that would break the rule, because it would be an even card that has brown on the other side. Hence we must flip this card over. The puzzle is not very hard, but the situation appears to make the logic hard to follow. Experiments have found rephrasing the problem in a familiar context is helpful. For instance, consider the rule that “every voter must be over 18 years old.” You are given profile cards with age on one side and whether a person voted on the other. The cards shown to you are, “16”, “voted”, “23”, and “not voted”. Which cards do you need to flip over to make sure everyone who voted was legally over 18 years old? People generally solve this problem instantly (you should check “16” and “voted”). This problem is known as the Wason Selection Task. Puzzle 3: Lost Money To A Buyer I sold a concert ticket for $20 to someone responding to a Craigslist ad. The buyer paid with a $50 bill. I didn’t have change on hand, but luckily my friend did. I gave him the $50 note for smaller bills, and I provided the buyer with $30 in change. The next day my friend tried to use the bill, but it was counterfeit and not accepted. The buyer did not respond to my emails and I realized I was probably scammed. I owned up to the mistake and repaid my friend $50. If I originally paid $20 for the concert ticket, how much money did I lose in total? Answer To Puzzle 3: Lost Money To A Buyer The answer is $50. Here is why. If the $50 bill had been legitimate, you would not have lost any money. So the only money you lost was for repaying your friend, which is $50. The longer answer is to carefully account for every transaction. You paid $20 to get the concert ticket. But you have not lost any money yet because you got the concert ticket, worth $20, in exchange. Your friend then gives you $50 dollars in exchange for the counterfeit note. So you are actually up $50 at this point. You reduce this by $30 when you give change to the buyer, so you are up by $20. This balances out with the $20 concert ticket you give up, so you are now completely even. The next day your friend tells you the note is fake. So you pay him $50, and so you are now down $50. Therefore, you have lost $50 in total. Credit: This is an updated version of an accounting puzzle I read in the book Decision Traps by J. Edward Russo, Paul J. H. Schoemaker. Puzzle 4: A Friend Puzzle This puzzle is based on an actual situation I faced recently. I wanted to have a gettogether with coworkers from a previous job. But I was unsure if the guests all got along. I decided to do a simple test on Facebook. I personally was friends with each of the 5 people I wanted to invite. But was each person also mutual friends with everyone too? I did not have to check each person’s profile, because once I saw person A was friends with person B, it must be the case that person B is friends with person A. The question is this: for a group of 5 of friends that you suspect are mutual friends, how many profiles do you have to check, at minimum, to be sure they are all mutual friends? What about the same problem for n people? Answer To Puzzle 4: A Friend Puzzle In a group of 2 people, you only have to check 1 person’s profile. If person A is friends with person B, then person B is necessarily friends with person A. (In mathematical parlance, the relation of mutual friends is “reflexive.”) Similarly, in a group of 3 people, you only need to check 2 people’s profiles. If person A is friends with B and C, and person B is friends with C as well, then person C is necessarily friends with A and B too. We can generalize: in a group of n people, one needs to check n – 1 profiles. It is necessary to check the first n – 1 people’s friends’ lists to make sure each person is friends with each other and the last person in the group. But once that is verified, the last person must necessarily be friends with everyone else. You can think about the problem graphically. Represent the group as a set of n points, and draw a line between two points if the two people are friends. If the first n – 1 points are connected to every other point by a line, then the last point must also be connected to every other point (there are n – 1 degrees of freedom). Thus, in a group of 5, one needs to check 4 people’s profiles to make sure they are all mutual friends. Puzzle 5: Family Crossing A River A family of four needs to cross a river. The father weighs 200 pounds, the mother 150, and each of two sons weighs 100. If the canoe can carry a maximum of 200 pounds at a time, how can the family get across the river? How many trips are necessary? Answer To Puzzle 5: Family Crossing A River Obviously the father and mother have to make lone trips while the sons ferry the canoe back and forth. In all, the family will need 9 trips as depicted below: Credit: this is a variation of puzzle in the Math Mole newsletter. Puzzle 6: Losing Weight A 200 pound man starts a weight loss regimen that promises a loss of 1 percent of body weight per week. How many weeks will it take to reach his goal of 150 pounds? Answer To Puzzle 6: Losing Weight The weight loss program has diminishing effectiveness each week. In the first week, he will lose 200(0.01) = 2 pounds so he will weigh in at 198 pounds. In the second, he will lose a bit less weight: only 198(0.01) = 1.98 pounds. Each successive week he will weigh in lighter and therefore lose a bit less weight. The easiest way to solve this problem is to track his weekly weight. If he loses 1 percent per week, that means each week he will weigh in at 99 percent of his previous week’s weight. For a weight W, his week k weight will be 99 percent of his week k  1 weight. In other words: W(k) = 0.99 W(k1) We know that his initial weight is 200, so the formula for weight after n weeks is: W(n) = 0.99 W(n1) = (0.99)2 W(n2) = … = (0.99)n(200) We solve this equation for the target of 150 pounds to find: 150 = (0.99)n(200) n = log(150/200)/log(0.99) = 28.62… Therefore, he will drop below 150 pounds at the 29th week. To the extent this model is realistic, few people stay on a diet for over half a year, and that’s perhaps one of the reasons weight loss is hard. Puzzle 7: Writing ThankYou Notes After a party, Alice and Bob prepare thankyou notes for the guests. Alice by herself would take 10 hours, and Bob by himself would take 5 hours to write all the thankyou notes. How long will it take if they work together? Answer To Puzzle 7: Writing ThankYou Notes Logically the job should get done quicker if Alice and Bob work together. Let’s determine a mathematical expression for them working together. We know that Alice can complete the job in 10 hours. So in t hours, she completes the fraction t/10 of the job. Similarly, in t hours, Bob can complete the fraction t/5 of the job. We wish to solve for t so their joint work is 1 whole job: that is, their fractional amounts add up to 1. This gives the following equation: t/10 + t/5 = 1 We can solve that t = 10/3, or 3 hours and 20 minutes. Let’s derive a general equation. If Alice can complete the job in a hours and Bob in b hours, then we can add up their fractional efforts of Alice’s t/a and Bob’s t/b to be 1 complete job: t/a + t/b = 1 If we multiply both sides by ab and simplify, we get the time is t = ab/(a + b). As a bit of trivia, this fraction has a special name. It is equal to half of the harmonic mean of the numbers a and b. Puzzle 8: Three Runners Alice, Bob and Charlie complete a 100 yard race. Alice finished the race 10 yards ahead of Bob. Subsequently Bob finished the race 10 yards ahead of Charlie. How far ahead was Alice over Charlie when she finished the race? Assume all three ran at constant speeds. Answer To Puzzle 8: Three Runners Since Alice finished 10 yards ahead of Bob, and Bob finished 10 yards ahead of Charlie, it is tempting to add up the distances to conclude Alice finished 20 yards ahead of Charlie. But that is not correct. The reason is we have to consider running rates. Charlie is a slower runner than Bob. In the time it takes Bob to complete the final 10 yards, Charlie would have run less than 10 yards. So at the instant Alice finished, Charlie must have been closer than 10 + 10 yards. How much closer would Charlie have been? We can solve the problem in terms of relative speeds. When Alice completes the race of 100 yards, Bob is 10 yards behind, so he has run 90 yards in the same amount of time. This means Bob runs at 90 percent the speed of Alice (B = 0.9 A). Similarly, when Bob completes the 100 yard race, Charlie is 10 yards behind, so he has run 90 yards in the same time. Hence Charlie runs at 90 percent the speed of Bob (C = 0.9 B). We can combine this equations to find that Charlie runs at 81 percent the speed of Alice (C = 0.9B = 0.9[0.9 A] = 0.81 A). So when Alice runs 100 yards to complete the race, in that time Charlie would have run 81 yards. Therefore, Charlie is 19 yards behind Alice when she finishes. Puzzle 9: Splitting A Shared Ride A businessman hires a driver to take him from point A to point C and back. The round trip costs $180. During the ride, the driver gets a request from a pair of poor college students. They would like to tag along and join for the round trip from point B to C. Point B is 2/3 of the way between A and C. The businessman doesn’t mind, and he in fact feels generous. He says to them: “If you can calculate the exact amount that each of you should fairly pay me, I’ll let you ride for free.” What would be the fair price for each student? Assume the fare is calculated on distance alone, and the riders will split a shared distance equally. Answer To Puzzle 9: Splitting A Shared Ride Since point B is 2/3 of the way to C, we can imagine BC is a distance of x and then AB would be a distance of 2x. The roundtrip from A to C is a distance of 6x and it costs $180. So to cover a distance of x the fair price is $30. What is the fair price for each student? The roundtrip from B to C is a distance of 2x, so the total cost is $60. Since there are 3 riders for this portion of the trip, the fair price should split the cost 3 ways. Thus, the fair price for each student is 1/3 of $60, or $20. Puzzle 10: Average Speed For the first half of my trip, I went at 30 miles per hour (mph). How quickly do I need to drive the rest of the way so I average 60 mph for the complete trip? Answer To Puzzle 10: Average Speed Suppose the journey is 60 miles. In order to average 60 mph, you need to complete the entire trip in (60 miles)/(60 mph) = 1 hour. If you travel half the way at 30 mph, then you have traveled 30 miles at 30 mph, which would have already taken you 1 hour. In order to average 60 mph for the entire journey, you would need to reach the destination instantly, or travel at an infinite speed! This is not possible because nothing travels faster than the finite speed of light. The result holds for a trip of general distance. If you need to average 2X mph for a trip of D miles, then you need to complete the trip in (D miles)/(2X mph) = D/(2X) hours. If you travel half the distance, D/2, at half the speed X, then you have already taken up (D/2 miles)/(X mph) = D/(2X) hours. In other words, you won’t be able to average 60 mph if you have already gone half the distance at half the speed of 30 mph. Puzzle 11: How Far Did I Jog? How fast I jog depends on the path. I can jog 3 miles per hour uphill, 4 miles per hour on flat land, and 6 miles per hour downhill. One day in San Francisco I jogged from my apartment to the Marina. It took me 50 minutes to get to the Marina, and 1 hour to return home on the reverse path. How far is my apartment from the Marina? Answer To Puzzle 11: How Far Did I Jog? This seems like one of those impossible puzzles in which there is not enough information. But if you do the math diligently you can figure it out! Let’s say the path from my apartment to the Marina involves the following distances: Apartment to Marina a miles uphill b miles of flat land c miles downhill We want to solve for the distance a + b + c. The first trick is to realize the reverse path will have the same distances, but the uphill and downhill distances will be transposed. So we have: Marina to Apartment c miles uphill b miles of flat land a miles downhill Now we can set up the equations to relate distance to jogging speed. If I jog (uphill distance) miles at 3 miles per hour, then that will take me (uphill distance)/3 hours to complete that distance. Similarly, it will take me (flat land distance)/4 hours to go on flat land and (downhill distance)/5 hours to go downhill. Using the distances defined above, we can get two equations that relate the distances to the total time it takes to jog to and from the Marina. Apartment to Marina a/3 + b/4 + c/6 = (5/6) hour Marina to Apartment c/3 + b/4 + a/6 = 1 hour Now we want to solve for the distance a + b + c. We proceed by getting rid of the fractions. We multiply both equations by 60 to get rid of the denominators and convert the time in hours into time in minutes. We get the following equations: Apartment to Marina 20a + 15b + 10c = 50 Marina to Apartment 20c + 15b + 10a = 60 Now we add these two equations together to get the following equation: 30a + 30b + 30c = 110 We divide this equation by 30 to solve for the sum of the distances. a + b + c = 3 + 2/3 miles That’s the answer! The apartment is 3 and 2/3 miles from the Marina. And if you think about it, that makes for a round trip of 7 and 1/3 miles which is quite a good jog. Puzzle 12: College Football Title Not satisfied with the current system, suppose college football programs decide to crown their own champion. Rather than organize a playoff bracket, they institute a freeforall system. Each team is allowed to challenge any other team to a game. A team that loses a game is eliminated and ineligible to play further games. The last team standing–the only team that never loses–is declared the national champion. Suppose there are 120 teams. What’s the minimum number of games needed to crown a title? What’s the maximum number? Answer To Puzzle 12: College Football Title Number the teams as 1, 2, …, 120. Consider a simple albeit unrealistic example. Imagine team 120 beats every other team one by one. There will be 119 matches played. You can experiment with other ways of scheduling the matches. But time and again, you’ll find that 119 matches need to be played! This is both the minimum (necessary) and maximum (sufficient) number of matches. Why is that? The reason is each team plays until it loses. In the end, there are 119 teams that lose and 1 team that never loses. Therefore, the tournament always has 119 games, where each game produces 1 loser. In general, for a similar singleelimination tournament with n teams, there will always be n – 1 games played. Puzzle 13: Pairs Of Cards Let’s play a game of chance. I have a standard 52 card deck that is shuffled well. I flip over the top two cards. If they are both red, then you get the pair. If they are both black, then I get the pair. If they are different colors, then the pair is discarded. I will continue flipping two cards at a time until the entire deck is dealt. At the end, you and I will have some pairs of cards. If you end up with more pairs of cards than me, then lucky you, I will pay you $10 for every extra pair you have. Otherwise, you lose the game and walk away. The game costs $1 to play. Are you willing to try your luck? Answer To Puzzle 13: Pairs Of Cards The game sounds too good to be true: if you end up with extra cards, you win a lot. If you don’t, you only lose the $1 entrance fee. So what’s the catch? This is an example of a sucker bet. The somewhat surprising answer is we will both get exactly the same number of pairs every time, no matter how the deck is arranged or shuffled. I’ll never have to pay you any money, but I’ll profit from the entrance fee. Why does this happen? Let’s prove it. To begin, note that a standard deck has 26 red cards and 26 black cards. All of the red cards end up in two piles once the game is over: either the pile of paired red cards or the pile of discarded redblack pairs. So we can write the equation: 26 = #cards in redred pairs + #red cards in redblack pairs Similarly, all the black cards end up in either the pile of paired black cards or the pile of discarded redblack pairs. So we have another equation: 26 = #cards in blackblack pairs + #black cards in redblack pairs Both equations are equal to 26, so we can equate the two expressions to get: #cards in redred pairs + #red cards in redblack pairs = #cards in blackblack pairs + #black cards in redblack pairs Now we can simplify this equation. The pile of redblack pairs has an equal number of red and black cards, so we have #red cards in redblack pile = #black cards in redblack pairs. We can cancel those terms to conclude the following: #cards in redred pairs = #cards in blackblack pairs In other words, the number of redred pairs must exactly equal the number of blackblack pairs, no matter how the cards are ordered in the deck. You will never have more red pairs than I have black pairs, so you always lose the game. Puzzle 14: Ways To Eat A Chocolate Bar I buy a chocolate bar that is divided into 10 bitesize squares in a line. If I eat 1 or 2 squares every day, how many different ways are there for me to eat the entire bar? Assume I start eating from the left side of the bar and continue eating to the right side without skipping any squares in between. For example, I could eat 1 bar every day for 10 days. Or I could eat 2 bars first, then 1 bar each for 8 days. Answer To Puzzle 14: Ways To Eat A Chocolate Bar Let’s work out smaller cases. What if the bar only had 1 square? How many ways are there to eat just 1 square? There is clearly only one way: you eat a 1 square the first day. What if the entire bar had 2 squares? You can see there are 2 different ways to eat the bar. You could either eat 1 square a day each day, or you could eat 2 squares on the first day. What about 3 squares? Now comes the neat part. We don’t have to count out the combinations. We can reason as follows. We can’t eat 3 squares at once. So the only way we could end up eating 3 squares is if we eat 1 square or 2 squares on the first day. If we eat 1 square on the first day, that leaves 2 squares to be eaten (and we already counted the number of ways to do that). If we eat 2 squares on the first day, that leaves 1 square to be eaten (and we also already counted the number of ways to do that). That means the following: we can count the number of ways to eat 3 squares by adding the number of ways for 2 squares left (2), plus the number of ways for 1 square left (1). If f(n) is the number of ways to eat a bar with n squares by 1 or 2 squares at a time, then we have reasoned f(3) = f(2) + f(1) = 3. Similarly, we can reason for n squares. In order to eat n squares in total, there are two possible ways to start. One way is to eat 1 square on the first day, leaving n – 1 squares not eaten (which can be counted as the number of ways to eat n  1 squares). The other way is to eat 2 squares on the first day, leaving n – 2 squares not eaten (which can be counted as the number of ways to eat n  2 squares). So we have the following equation: f(n) = f(n – 1) + f(n – 2) This is the familiar formula for the Fibonacci sequence. (A bit of trivia: the Indian mathematician Pingala came upon this pattern 1,200 years before Fibonacci in the study of Sanskrit poetry.) So we can use this recurrence relation to solve the puzzle: The answer is there are 89 different ways I can eat the chocolate bar. Credit: this problem is adapted from the stair puzzle in William Poundstone’s book Are you Smart Enough to Work at Google? Puzzle 15: Flights Around The Country Bob wants to visit 25 cities around the country. If he wants to fly to every city exactly once, and start and end the trip from his hometown, how many possible ways can he make the trip? Assume there exists a flight between any two cities. Bonus: Some of these itineraries will be impractical because one would want to fly to nearby cities for efficiency. So suppose Bob divides the trip into 5 geographic areas, each with 5 cities. When he visits a geographic area, he will visit all those cities together before going to another geographic area. In how many ways can Bob make this trip? Answer To Puzzle 15: Flights Around The Country There are 25 possible cities for the first stop, then 24 possible cities for the second, and so on. Thus, there are (25)(24)… (1) = 25! possible ways to make the trip. For the bonus, the correct answer is (5!)6. First we count the number of ways Bob can visit the different geographic areas. There are 5 choices for the first, then 4 for the second, then 3 and 2 and 1. So there are 5! = 120 ways to visit the different areas. In each area, Bob has to choose how to visit the 5 different cities. There are 5! ways to do this for each of the 5 areas, which gives (5!)5 possibilities. Thus, the total number of trips is: 5!(5!)5 = (5!)6 That’s still a lot of trips, but about 1/1013 smaller than the 25! number of trips from the original problem. Puzzle 16: Order Of Eating Courses I eat soup, salad, and a sandwich for lunch. Some days I like to eat one course at a time; for instance, I’ll finish my soup, then I’ll have my salad, and only then I will eat my sandwich. Other days I might like to eat all of the courses together. And finally, I might mix things up by pairing certain courses: I might eat my salad first, but then eat the soup and sandwich together. How many possible ways are there for me to eat my lunch? Assume my choices are to eat one course at a time, two courses at a time, or all three courses together, and the order of eating the courses matters. Answer To Puzzle 16: Order Of Eating Courses This problem can be solved by enumerating all the possibilities. Here’s a listing of the possible ways I can eat my lunch. Write 1 to denote eating soup, 2 salad, and 3 the sandwich. There are 6 ways I can eat my meal 1 course at a time. I will write (a, b, c) to mean I eat item a, then item b, and then item c. Here are the 6 ways: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). What if I pair 2 of the courses and eat them at once? There are 6 ways I can eat my meal in this case. I will write (ab, c) to mean I eat courses a and b together and then eat c after. I can also have (a, bc) to mean I eat a first and then b and c together. Here are the 6 ways: (1, 23), (2, 13), (3, 12), (12, 3), (13, 2), (23, 1). If I eat all 3 courses at the same time, there is just 1 possibility: (123). In all, there are 6 + 6 + 1 = 13 ways that I can eat my meal. We can also solve the problem combinatorially. The number of ways to eat 1 course at a time is the number of permutations of 3 items. There are 3! = 6 ways to eat one course at a time. The number of ways to eat when some 2 courses are paired is found slightly differently. There are 3 choices for the course not to be paired, and that item can be eaten first or second, so there are 2 orderings. This is why there are 3(2) = 6 ways to eat in when one course has 2 items. Then there is just 1 way if all the items are eaten together. This means there are 6 + 6 + 1 = 13 ways in all. Puzzle 17: Hot Sauce My friend was cooking dinner, and he found himself in a predicament. He made 6 quesadillas for dinner. On 2 of them he added hot sauce to the filling. He is the only person that enjoys the extra spice, and his wife and 2year old daughter would be displeased if they got the wrong filling. While cooking and flipping the quesadillas, he inadvertently forgot which quesadillas had the hot sauce filling. So he ended up with 6 identical quesadillas that he served at random. He went ahead and served himself 3 quesadillas, his wife 2, and his daughter 1. My friend realized he was playing out a textbook probability question, and he was curious about the following questions. Part A. What is the probability that he correctly serves the food and he ends up with both quesadillas that have hot sauce? Part B. What is the probability that he ends up with 1 having hot sauce and his wife has 1 as well? What about him getting 1 hot sauce and his daughter getting the other? Part C. What are the chances he gets none of the hot sauce quesadillas? Can you help my friend out? What are the odds? Answer To Puzzle 17: Hot Sauce Write H for a quesadilla with hot sauce and N for a quesadilla without it. There are 6 identicallooking quesadillas: H, H, N, N, N, N. Short explanation of ways to choose objects without order. This problem is about the number of ways to pick objects without regard to order. Suppose you want to pick k objects from N, and the order doesn’t matter. Your first choice has N possibilities, your second choice has N  1, your third choice has N  2, and so on, until the last choice has N  k + 1 possibilities. So in all there are N(N 1)…(N  k + 1) arrangements. However, the order of the items is not relevant. (As in, getting HN is the same as NH because in either case you have one hot sauce quesadilla.) So we divide by k! to avoid doublecounting the various arrangements. In summary, there are N(N  1)…(N  k + 1)/k! = N!/[k!(N  k!)] ways to choose the items. The topic of choosing items from a set comes up frequently. In this book I’ll abbreviate this as “N choose k” and proceed with the calculation. Part A. My friend chooses 3 quesadillas for himself out of 6, so there are 6 choose 3 = 20 total ways that my friend can pick his 3 quesadillas. In how many ways will he get both of the ones with hot sauce? There is only 1 way he gets both of them (HH), and he can pick any of the four remaining nonhot sauce ones (N) for his third quesadilla. So there are 4 ways he could get both of the quesadillas with hot sauce for a probability of 4/20 = 20 percent. This is not too bad, but there is also an 80 percent chance he messes up, so it depends on how you look at it. Part B. How many ways can my friend pick exactly 1 hot sauce for himself? There are 2 choices for the quesadilla with hot sauce. Then there are 4 choose 2 ways he can pick 2 out of the 4 quesadillas without hot sauce. So there are 2(4 choose 2) = 12 ways. Out of 20 ways in total, there are 12 where he gets exactly 1 with hot sauce, meaning there is a 60 percent chance of this case. The other quesadilla with hot sauce filling either goes to the wife or the daughter. The wife eats 2 quesadillas and the daughter 1. In other words, there are 3 places to distribute the hot sauce quesadilla, of which the wife has 2 places and the daughter has 1. So in 2/3 of the 60 percent, which is 40 percent of the time, his wife gets the other hot sauce filling. And in 1/3 of 60 percent, which is 20 percent, his daughter gets the other hot sauce filling. Part C. What’s the chance my friend gets no hot sauce filling? That means he picks 3 of the 4 regular quesadillas, which can happen in 4 choose 3 = 4 ways. This is out of a total 20 ways, so he has a 20 percent chance of getting no hot sauce. The most likely outcome is my friend will get exactly 1 quesadilla with hot sauce filling. Puzzle 18: Wardrobe Choices A finicky traveler is packing clothes for a 3day trip. The traveler can never decide what to wear in advance and would like to have choices available for each day of the trip. Each day the traveler wears a previously unworn pant and an unworn shirt. An outfit choice is a pantshirt combination. If the traveler would like to have at least 4 outfit choices each day, what is the minimum number of pants and shirts that the traveler must pack? What if the trip lasts n days? What if the person wanted k choices each day? Answer To Puzzle 18: Wardrobe Choices This problem can be solved by thinking backwards from the end of the trip. On the very last day, the traveler must have 4 outfit choices. So we need to have (pants x shirts) = 4 and we want (pants + shirts) to be minimal. The factors of 4 are either 4 and 1 (sum of 5) or 2 and 2 (sum of 4). The latter option has a smaller sum and corresponds to bringing fewer clothes. Thus, the traveler would need 2 pants and 2 shirts for the last day of the trip. For each of the days before, the traveler needs 1 extra pant and 1 extra shirt. Thus, for a 3day trip, the traveler needs 2 + (1 + 1) = 4 pants and 2 + (1 + 1) = 4 shirts. For an n day trip, the same logic applies. The traveler needs 2 pants and 2 shirts on the last day and will need 1 extra pant and 1 extra shirt for each previous day. So the traveler needs 2 + (n  1) = n + 1 pants and 2 + (n  1) = n + 1 shirts. If the traveler wants k choices each day, then on the last day the traveler needs (shirts x pants) = k for a minimal number of (shirts + pants). This is minimized by considering the prime factorization of k to determine the pair of divisors with the least sum. Call those x < k/x. Then, for each previous day the traveler needs 1 extra shirt and 1 extra pant. The total number of pants and shirts needed will be: pants: x + (n  1) = x + n – 1 shirts: k/x + (n  1) = k/x + n – 1 The traveler can also opt for k/x shirts and x pants on the last day giving similar solutions. You can solve for x by considering the integers closest to the square root of k. Why? Suppose we want factors a and b where ab = k and the sum a + b is minimal. Geometrically, this is like finding the least perimeter rectangle for a given area, which is a square. Alternately, we can use calculus to find the minimum happens in the continuous case when a = b = √k. In our problem we need whole number factors for the number of shirts/pants, so we consider the factors that are closest to √k. Puzzle 19: Wedding Seating Arrangement A group of 10 people sits down at a wedding table. Only after sitting do they realize the table had name tags for each seat, and no one was sitting in the correct seat. Prove that there is a way to rotate the table and its name tags so that at least 2 people will be in their correct seats. Answer To Arrangement Puzzle 19: Wedding Seating First note there are 10 ways to rotate the table: it can be rotated 1 to 10 seats from its current position. A rotation of 10 seats is the same as a rotation of 0 seats, which is the original position of the table. Second, for each of the 10 people, there is some rotation that can bring that person to the properly assigned seat. Label the individuals 1 to 10 and call those rotations r1, r2, …, r10. Each of these 10 rotations must be equal to one of the 10 possible rotations for the table. However, since no one was initially in the correct seat, we have to exclude the rotation where the table moves 10 seats (or is in the initial position). So each of the 10 rotations must be equal to one of the 9 possible rotations for the table. If 10 rotations have to be equal to 9 possible values, then at least 2 of them have to be equal to the same value (by the pigeonhole principle). In other words, at least two of the rotations ri, rj must be equal. That is for some ri = rj at least 2 people i and j will be in their correct seats. Puzzle 20: A Fun Baseball Inequality A player’s batting average is defined as the number of hits (H) divided by the number of atbats (AB). For example, someone who gets 2 hits in 10 tries has a batting average of 20 percent (often written to three decimal places as 0.200). We can turn the numbers around to find another useful statistic. If we divide the number of atbats by the number of hits, we get the average number of atbats before getting a hit. For someone who gets 2 hits in 10 tries, we can say the person gets a hit in roughly every 5 tries at the plate. Now here is the interesting question: what happens when you add the two numbers together? Let’s work through a couple of examples. If someone has 2 hits in 10 tries, then we have: H/AB + AB/H = 2/10 + 10/2 = 5.4 If someone has 1 hit in 3 tries, then we have: H/AB + AB/H = 1/3 + 3/1 = 3.333… Finally, if someone gets 5 hits in 5 tries, then we have: H/AB + AB/H = 5/5 + 5/5 = 2 Hmm, this looks like a pattern…it seems that the sum of the two statistics will always be greater than or equal to 2. This is actually the case. But can you figure out why? More generally, there is a stronger mathematical statement. If you pick any two numbers a and b, it will be the case that: a/b + b/a ≥ 2 Try it out with any two numbers–it will be true! Can you prove why this must be the case? Answer To Puzzle 20: A Fun Baseball Inequality A reader of my blog sent me a direct proof. Since every squared number is nonnegative, the squared difference of the numbers is nonnegative. We can use this to find the result as follows: (a  b)2 ≥ 0 a2 + b2 ≥ 2ab a/b + b/a ≥ 2 The last step involves dividing both sides by ab and then taking the absolute value so that the final quantity on each side is positive. I came upon a different proof which is longer but instructive. The trick is to use the following fact: for any two nonnegative numbers, the arithmetic mean (the simple average) is greater than or equal to the geometric mean (the square root of the product), with equality only when the two numbers are equal: (a + b)/2 ≥ √(ab) For our purposes, we will rearrange the inequality as follows: a + b ≥ 2√(ab) If we let a = H/AB and b = AB/H, the left hand side becomes the sum of the two ratios, and the right hand side becomes 2 because the product of reciprocals is 1. So we have H/AB + AB/H ≥ 2. This inequality can make for a nerdy party trick (ask someone for 2 numbers, then add up the ratio and reciprocal ratio) because it is not immediately obvious why it must be true. Credit: I read about this problem in Methods of Problem Solving, Book 2 by Tabov, JB, Taylor, PJ. Puzzle 21: 12 Balls, 3 Weighings You have 12 balls that look and feel identical. One of the balls has a slightly different weight than the others. At your disposal is a weighing scale where you can place balls on each side. How can you identify the different ball in at most 3 weighings? Answer To Puzzle 21: 12 Balls, 3 Weighings The task seems impossible at first because you don’t know which balls are the same and which one is different, or whether the different one is lighter or heavier. The key observation is this: if two groups of balls weigh the same, then all the balls must be “good.” This gives you a control group against which you can compare the remainder of the balls. Number the 12 balls from 1 to 12, and group them into sets of 4 balls {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}. Step 1: Weigh {1, 2, 3, 4} against {5, 6, 7, 8}. Either the two groups weigh the same or one side is heavier. We’ll first suppose the two groups are the same and then consider if one side is heavier a bit later. If the two sides are equal, then we know all 8 of these are good balls. So we have to figure out the different ball from the group {9, 10, 11, 12}. Step 2 (both sides equal): weigh {9, 10, 11} against the known good balls {1, 2, 3} There are 3 things that can happen. Case 1: The group {9, 10, 11} is lighter. Since {1, 2, 3} is a set of good balls, we know the lighter ball is in the group {9, 10, 11}. In the third weighing, weigh two of them against each other, say {9} against {10}. If one side is lighter, then that is the lighter ball. If the two sides are the same, then the other ball {11} is lighter. Case 2: The group {9, 10, 11} is heavier. This case is similar. Since {1, 2, 3} is a set of good balls, we know the heavier ball is in the group {9, 10, 11}. In the third weighing, weigh two of them against each other, say {9} against {10}. If one side is heavier, then that is the heavier ball. If the two sides are the same, then the other ball {11} is heavier. Case 3: If the two sides are the same, then the odd ball is the one not weighed yet, which is {12}. In the third weighing, weigh {12} against any of the other balls to find out if it is heavier or lighter. This settles matters if the two sides were equal in the first weighing. Now suppose one side was heavier and call that side {1, 2, 3, 4}. Then we know the balls not weighed {9, 10, 11, 12} are all good balls, but we don’t know which of the balls from 1 to 8 is different. Now we need to do a clever weighing. We will remove 3 of the balls from the heavy side and transfer 3 from the light side. We’ll also add 3 good balls to the lighter side. Step 2 (one side heavier): weigh {1, 6, 7, 8} against {5, 9, 10, 11} Again, there are 3 things that can happen. Case 1: If the side with {1} is still heavier, then either {1} is the heavy ball or {5} is the light ball**. We can weigh either ball against a good ball {12} and figure out which one is true. (Say we weigh {1} against {12}. If they are the same, then {1} is good so {5} is lighter. Otherwise, {1} will be heavier.) **Why must this be so? Notice we’ve moved 3 light balls to the side with {1}. So if the {1} side is heavy, that could not be a result of a light ball being on that side. So it must be that {1} is heavy. Otherwise, we know that {9, 10, 11} are good. So it could also be that {5} is light. Case 2: If the side with {1} is now lighter, then one of the balls {6, 7, 8} is the light ball**. We can weigh two of them against each other and figure out the odd ball. (Say we weigh {6} against {7}. If they are the same, then {8} is light. Otherwise, they are not the same and the light one can be identified.) **Why is this? There is only 1 odd ball. In two weighings the side with {6, 7, 8} was light, even against 3 known balls from the control group, so the light ball must be in that group. Case 3: If two sides are now the same, then we know all these balls are good, so the balls {5, 6, 7, 8} must have been good. The second weighing also says {1} is good. Thus, one of the balls in the group {2, 3, 4} must be heavy. In a third weighing, weigh any two against each other to identify which one. (Say we weigh {2} against {3}. If they are the same, then {4} is heavy. Otherwise, they are not the same and the heavy one can be identified.) Puzzle 22: Mathemagic Guessing A “Lost” Number Today we will play a little game. It will require that you do a few calculations. Ready to play? Okay, the first step is I want you to write down a 4digit number. (Just don’t include too many zeros). Next, I want you to add up the digits in the number. If you wrote 1234, then I want you to add 1 + 2 + 3 + 4 = 10. Call this number X. Now comes the fun part. You get to cross out any digit of the original number so you end up with a 3digit number. Think about which digit from 1 to 9 that you want to “lose,” and cross it out. Finally, take your threedigit number and subtract X (the sum you calculated earlier). Tell me the final number. Now I didn’t know your original number, nor did I see the number you crossed out. But if you submit me that number then I can magically tell you which digit was “lost” that you crossed out! An example of how this works Let’s say you picked the 4digit number 1234. The sum of the digits is 10 = X. You cross out the 2 so you are left with 134. Subtracting X yields 124. If all you did was tell me 124, I would know you crossed out 2, precisely the number you crossed out! This is even though I did not know your original number or see you cross anything out. Can you figure out how I do the trick? Answer To Puzzle 22: Guessing A “Lost” Number Mathemagic Let’s say you start with a number abcd whose sum of digits is a + b + c + d = X. Let’s say you cross out the digit b to be left with acd. The number you tell me is this number minus the sum of the original digits, which is acd – X. How can I obtain that b was the missing digit from the value of acd – X? Let’s step back for a moment and recall some basic number theory. The result seems mysterious when we view things as normal numbers, but it will be a lot easier if we work in modulo 9 (the remainder of a number after dividing by 9). Part 1: Powers of 10 have a remainder of 1 (mod 9) There’s a basic pattern that will help us out. A few examples will give the picture. What is 10 modulo 9? That is easy: 10 gives a remainder of 1 when divided by 9. What about 100? Well, 100 divided by 9 is 11 plus a remainder of 1. What about 1,000? Again, we will see that 1,000 modulo 9 is equal to 1 (as 1,000 is 1 more than 999). We can see a pattern here: 10n ≡ 1 (mod 9) This should make intuitive sense: any power of 10 will be 1 more than a multiple of 9 (this is the same as pointing out any number 999…999 plus 1 will be a power of 10). And let’s go one step further. Let’s multiply both sides of the equation by x. We then have: x(10n) ≡ x (mod 9) So what does this mean? We actually have a powerful result here for our trick. Part 2: the sum of digits Let’s go back to the number abcd. This number really means a(104) + b(103) + c(102) + d(10) because we are working in base 10. Now what happens when we take this number modulo 9? We can use part 1’s result to get rid of the powers of 10, which are all congruent to 1 modulo 9. So we have: a(104) + b(103) + c(102) + d(10) ≡ a + b + c + d (mod 9) So the original number and the sum of its digits are the same modulo 9. That’s the fact we will utilize for our trick. Part 3: how the trick works Okay, it’s been a lot of setup, but now we can answer why the trick works. First, we start out with a number abcd and find the sum a + b + c + d = X. Now we are told to delete some digit (say b), and subtract X, so we have acd – X. The trick is to view this number modulo 9. We will have: acd – X ≡ a + c + d – (a + b + c + d) ≡ – b (mod 9) And voila! That is why the procedure will tell us the missing number. We end up with b, and we can multiply by 1 and take that modulo 9 to obtain b. Equivalently, we can subtract the number from 9. If our result was 7, then we do 9 – 7 to find 2 was our missing number. So the trick is simple; whatever number I am told, I calculate “answer = 9 – (number you told me) mod 9” and that is the missing number! Important: don’t let them cross out 0 I originally did not realize an issue with this trick and ran into some trouble in a performance. You should make sure the other person picks a digit from 1 to 9 to “lose.” The reason is that 0 and 9 are congruent modulo 9. This means if you ended up with the final number of 9, you won’t be sure if the other person picked a 0 or a 9. Doing this trick at parties You can also perform this trick at parties using some mental math. Ask someone to pick a 4 digit number, and add up the digits. Then tell them to lose a digit from 1 to 9 and subtract the sum of the original digits (this might sound complicated, but everyone I’ve asked can do this mental math with no problem). Then ask them for the resulting number. Your job is then to: 1. Add up the digits until you get a single digit (this is known as “casting out the nines” and it’s the same as taking a number modulo 9. 2. Subtract that number from 9 and to obtain the missing digit. Credit: I read this trick first Mathematical Magic by William Simon. I have since read it in a few more books, so I’m not sure of the original source. Puzzle 23: Piles Of Coins This is a puzzle that was asked as a finance interview question. I want to give a fair warning this is a pretty hard problem, and it gave me a new level of appreciation for the intelligence of the quant guys on Wall Street. A pile of 1,000 coins is split into two piles x and y. Multiply those together to get a number xy. Subdivide each of the two piles further and get a number for each pile. (Say you divide x to get the new number x1x2, and y to get the new number y1y2). Repeat the process until there are 1,000 piles, each with 1 coin. Add all of the numbers together. What is the sum? Does the answer change depending on how you split the pile? Answer To Puzzle 23: Piles Of Coins I would be stunned if anyone came up with an answer for the 1,000 case right off the bat. In interview questions, it is almost always a good idea to start with smaller cases and see if there is a pattern. This gives you some time to work through examples, and is shows the interviewer that you can break a problem down. So let’s try some smaller cases. With 2 coins, there is only one possible division: 11. This gives a sum of 1. With 3 coins, again there is only one possible division. You split the coins into 21 (gives the number 2) and then you split the 2 pile into 11 (gives the number 1). In all, the sum of the numbers is 3 = 2 + 1. So far, it is hard to see any pattern. What about 4 coins? This is where the problem gets interesting. There is more than one way to split the coins. We can do either of the following divisions: Hmm, this is rather interesting that the sum is the same either way the coins are divided. At this point, one might conjecture the final result is the same regardless of the way the coins are split. If that’s the case, we can figure out a simple way to compute the sum and we can figure out the answer for 1,000 coins. So what I’d do in the interview is work out a simple algorithm to compute the sum, and then I’d think of some way to prove this must be true. A simple algorithm I got this idea from the second possible way to divide 4 coins. I noticed that each time we were just removing 1 coin, and the numbers we summed were 3 + 2 + 1 = 6. Could this pattern be a hint to the sum? Let’s generalize this pattern. If we have n coins, a simple division is to just take away 1 coin from the pile each time. The piles will thus be (n – 1, 1), then (n – 2, 1), (n – 3, 1), …, then (2, 1), and finally (1, 1). The sum we get will be: sum = (n  1)(1) + (n  2)(1) + … + (1)(1) sum = (n  1) + (n  2) + … + 1 sum = n(n  1)/2 Basically, when we remove 1 coin from the pile at a time, the intermediate products end up being the integers from 1 to n – 1. So our final result is the sum of the numbers from 1 to n – 1. The formula for the sum of numbers 1 to k is k(k + 1)/2, and so the sum of the numbers 1 to n  1 is n(n 1)/2. If we apply this formula to 1,000 coins, our final answer will be 1000(999)/2 = 499,500. But we are still not done. It was a conjecture that the sum will be the same for an arbitrary division. Now we will have to prove that is actually the case. Induction to the rescue! To prove this formula, we will use induction. We already worked out the cases of piles of 2, 3, and 4 coins, and one can verify the formula works on these base cases. Now, we will prove the result generally holds. We assume that for piles of coins less than n the formula is true and holds regardless of the division method. Now we need to show the formula works for n. In the very first step, we will divide the pile of n coins into piles of n – x and x. Incidentally, the degenerate case of x = 0 means we left the pile as it was. But that is okay because 1000(0) = 0 so our ultimate sum is not affected. Thus we can assume x is at least 1. The two piles will contribute the number (n – x)(x) to our final sum. And now comes the neat part. The two piles are both less than n coins. By the induction hypothesis, we can conclude the final result for each of these piles is the same regardless of the division process. Plus, we have a formula for what the final result will be for each pile. So we add up the initial number (n – x)(x) to the sums we get from the two applications of the induction hypothesis. The calculation we need to do is the following: The pile of x has a sum x(x  1)/2, the pile of n  x has a sum (n  x)(n  x  1)/2, and adding those to (n  x)x gives a total sum of n(n – 1)/2. This confirms the sum for a pile of n coins is n(n – 1)/2, which is what we sought out to prove. Therefore, the formula holds and the answer for 1,000 coins is 1000(999)/2 = 499,500. Puzzle 24: Piles Of Coins (Continuous Version) This is an extension of the previous puzzle. A line segment of length 1 is split into two lengths x and y. Multiply those together to get a number xy. Subdivide each of the two line segments further and get a number for each of those new line segments. (Say you divide x to get the number x1x2, and y to get the number y1y2). Repeat the process infinitely and add all of the numbers together. What is the sum? Generalize for a segment of length n. Answer To Puzzle 24: Piles Of Coins (Continuous Version) The answer for a length of 1 is 1/2, and for length of n it is n2/2. Here is a proof that was offered on a Reddit Math discussion to this problem. Let’s solve the problem for an interval of length L. Let’s draw out a triangle in the Cartesian plane with corners (0, 0), (L, 0), and (0, L). If the first division is x and L  x, then x(L  x) is the area of the rectangle with vertices (0, 0), (x, 0), (x, L  x), and (0, L  x). This rectangle is contained within the original triangle. There are also two smaller right triangles, and these correspond to the new intervals for (0, x) and (x, L). The process will be similar for each of those triangles: the division process will result in rectangles contained within those smaller triangles. Adding up all the subdivision products is geometrically adding up the areas of all these small rectangles. In the limit, the sum of these rectangles will be equal to the area of the original isosceles right triangle with length L. This triangle has area equal to (base)(height)/2 = (L)(L)/2 = L2/2. Note this will be the same result no matter which division method is used. So the answer is always L2/2. Puzzle 25: A Fun Math Sequence This is a wonderful little math problem that I came across. Consider the sequence S = {1, 1/2, 1/3, 1/4, …., 1/100}. Pick any two numbers x and y and replace them with a new number equal to: new term = x + y + xy For instance, the numbers 1/4 and 1/8 would be replaced by 13/32. Keep repeating the process until only one number remains. What number or numbers will result? Answer To Puzzle 25: A Fun Math Sequence The remarkable answer is the final number will be 100, and it will be the same regardless of the order in which you pick the numbers. Why is that? Let’s first prove the order does not matter, and then find a formula for the sum of the sequence. Part 1: the order does not matter Let’s define the function f by f(x,y) = x + y + xy If we think for a minute, we can see why the order of picking the pairs does not matter. The reason is the function f only depends on addition and multiplication, both of which are associative and commutative so the order does not matter. It suffices to prove the order does not matter for any three numbers we pick. Specifically, for any three numbers x, y, and z, we need to check that: f(f(x,y),z) = f(f(x,z),y) = f(f(y,z),x) We can verify all three formulations are equal to the following expression: x + y + z + xy + xz + yz + xyz The long and short is that the order in which we pick the pairs does not matter. You will always end up with the same final number. Part 2: a formula for the final number This is a problem where it helps to try a few smaller cases. For instance, let’s consider the sequence S(2) = {1, 1/2}. What final number results for this sequence? We can directly evaluate: f(1 , 1/2) = 1 + 1/2 + (1)(1/2) = 2 What happens when we add one more number for S(3) = {1, 1/2, 1/3}? Now we can use a trick to evaluate the final number. We already know that picking the pairs 1 and 1/2 will be replaced by the number 2. So we can simply jump ahead and evaluate the pair of 2 and 1/3. f(2 , 1/3) = 2 + 1/3 + (2)(1/3) = 3 This is an interesting little pattern we have. We found the final result for S(2) was 2, and the final resulting term for S(3) was 3. Could it be the case that S(n) will result in the final term of n? In fact this is the answer. We will use induction to prove this. We already checked the base cases above. So now we will assume the formula is true for all sequences less than k. What will the result be for the sequence S(k)? We know that S(k) is equal to S(k – 1) plus the additional term 1/k. And we know the resulting term of S(k – 1) will be k – 1, by the induction hypothesis. So we can evaluate the final term for S(k) as the result of the final pairs k – 1 and 1/k: f(k – 1, 1/k) = k – 1 + 1/k + (k – 1)/k = k – 1 + 1 = k This proves that the final resulting term of S(k) will be k. Extension: an interesting formula While solving the problem, I came across a connection with set theory. The concept I remembered was the power set, which is defined as the set of all subsets. For example, the power set for {x, y} is the set that includes all of the subsets {}, {x}, {y}, and {x, y}. Similarly, the power set for {x, y, z} is the set that includes all 8 of the subsets {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, and {x, y, z}. Here’s the connection with the original problem. Let’s go back to the case when you have a set of three elements x, y, and z. The final number we arrive at is equal to x + y + z + xy + xz + yz + xyz Do you notice anything special about those terms in the sum? The terms can be found by writing out the power set for {x, y, z}, taking the product of terms from each subset, and then adding them up! (I’d nominate this sum to be called the “power set product sum” for lack of a better term). The extension is we can solve for some crazy looking sums. For instance, in the power series {1, 1/2, 1/3, …, 1/n}, we have proved the final term is equal to 100. Therefore, we have proven the following is equal to 100 as well: In other words, the final term of problem 1 is equal to n, and that is also equal to an interesting sum so the two must be equal! Or to write it out slightly differently: Combinatorial proofs can be very interesting indeed! One more connection with algebra! Consider the constants a, b, and c. Now define the function: F(x) = x3 + (x + a)(x + b)(x + c) If we expand the formula out, we get the following: F(x) = x2(a + b + c) + x(ab + ac + bc) + abc Hmm, this is interesting. What if we evaluate this function at the value of 1? Then we end up with F(1) = a + b + c + ab + ac + bc + abc If we started with a set {a, b, c}, then this function evaluated at F(1) is exactly the final resulting term from our original problem! The function can be extended for larger sets. If we have a set with n elements a1, a2, …, an, then we can define the function F(x) = xn + (x + a1)(x + a2)…(x + an) The function evaluated at 1, written as F(1), will precisely be equal to the final term of our original problem, as well as the complicated “power set product sum” that was described above. A theorem based on the function Let’s add the term 1 to the harmonic set up to 100 so we have {1, 1, 1/2, 1/3, …., 1/100}. What will the final number be? If you try to do this manually, it might not be apparent. But we can use the trick: let’s think about the function! We know the function can be written as: F(x) = x101 + (x + 1)(x + 1)…(x + 1/100) Now comes the neat part. We want to evaluate the function at x = 1. But notice something: one of the terms in parenthesis is (x + 1). This term will be zero, and hence the entire product of the terms in parentheses will be 0 as well! Thus, we can conclude that: F(1) = 1101 + 0 = 1 So we have proven this: any set that contains the term 1 will necessarily result in the final number being 1. Putting it all together This simple puzzle results in some interesting math. Specifically, we have found the following three statements to be equivalent. (1) Repeatedly applying the process x + y + xy for a given set until the final term (2) Evaluating the “power set product sum” for a given set (3) Evaluating F(1) for the function described above These are some neat results that came from a seemingly simple problem. Section II: Geometry Geometry is one of the oldest branches of mathematics. See if you can figure out these puzzles that test your knowledge of distances and angles. Puzzle 1: Make A Rectangle In the following shape, make 1 continuous cut so that 2 pieces can be rearranged to form a rectangle. Answer To Puzzle 1: Make A Rectangle The solution I had in mind was a staircase style cut. When I posted about this problem, it got picked up by the blog BoingBoing and I received a number of new solutions on Twitter. Erik Smith (@ErikSmith80) suggested a simple cut of one of the tabs. DC Turner (@dcturner) thought about cutting horizontally across. And Tim Heffernan (@Tim_Heffernan) came up with another solution that involves flipping one of the pieces over. This problem was inspired by the many odd shapes I got while cutting wrapping paper. So it’s good there are many solutions as that means there are many ways to make unusual tabbed shapes back into a rectangle. Puzzle 2: Clock Division You need to divide a cake into equal pieces. The first problem is to divide it into 12 equal pieces. The second problem is to divide it into 11 pieces. You have an analog wall clock that you can use to determine angles. Answer To Puzzle 2: Clock Division Dividing into 12 pieces is easy: you can divide the cake at the 12 hours of the clock. How do you divide into 11 pieces? Here’s the trick: the hour and minute hands of an analog clock meet at exactly 11 times in a 12 hour period. Set the clock at 12:00 (which is one time the hands meet) to make the first slice. Then wind the minute hand until the hands meet next to get the next slice (this will be at about 1:05). Repeat the process to determine the rest of the angles! Here is a rough sketch of the 11 divisions. Credit: I came across this problem at Alok Goyal’s puzzles. Puzzle 3: Fitting A Square Peg In A Round Hole What is a tighter fit: a square peg in a round hole, or a round peg in a square hole? Answer To Puzzle 3: Fitting A Square Peg In A Round Hole First, let us consider a square peg in a round hole, as in the following diagram. If we let the circle have radius r, then that means the square’s diagonal measures 2r. The triangle formed by the square’s diagonal and its two sides is an isosceles right triangle. By the Pythagorean Theorem, we can solve for the square’s side, which is r√2. The square’s area is the square of the side, so it is 2r2. This is to be divided by the circle’s area, πr2. The ratio of the square’s area to the circles is: Square peg in round hole (2r2)/(πr2) = 2/π ≈ 64 percent Thus, the square peg fills about 64 percent of the circle’s area. Now we calculate the other way around: a round peg in a square hole. If we let the square have side s, then the circle’s radius is s/2. The circle has an area πs2/4. This is to be divided by the square’s area, s2. The ratio of the circle’s area to the square is: Round peg in square hole (πs2/4)/(s2)= π/4 ≈ 79 percent The circle is about 79 percent of the square’s area. This is larger than the 64 percent of the square filling the circle’s area. This means a round peg in a square hole is a better fit than the other way around. Puzzle 4: Inscribed Rectangle What is the largest area for a rectangle inscribed in a circle? That is, what percentage of the circle can the rectangle cover? Answer To Puzzle 4: Inscribed Rectangle One solution method is to use calculus. For a rectangle with height h and width w, the area is hw. The circle’s diameter (2r) is the diagonal of the rectangle. The two sides of the rectangle and its diagonal form a right triangle. So by the Pythagorean Theorem, we have h2 + w2 = 4r2. We can solve for the height: h = √(4r2  w2). The area is hw = w√(4r2  w2). We can equivalently maximize the area squared, which is w2(4r2 w2). Taking the derivative with respect to w and solving, we get w = r√2. We substitute back to find the height is also the same, h = r√2. Since the rectangle’s sides are equal, this rectangle is a square. The area is hw = 2r2. The circle has area πr2, so the rectangle takes up (2r2)/(πr2) = 2/π of the circle. This is approximately 64 percent. There is another way to solve this problem that gives a different intuition as to why the rectangle of largest area is a square. Note that the four interior angles in a rectangle are right angles. From geometry, an inscribed angle subtends an arc that measures twice as large. That is, the arc will measure 180 degrees. This means two adjacent sides of an inscribed rectangle are contained in a semicircle. Because the rectangle is symmetric about its diagonal, we can maximize the area of the entire rectangle by maximizing half the area of the rectangle, which is the area of the triangle between the two sides of the rectangle and the diameter of the circle. The question is how: which triangle has the largest area? The triangle’s area is equal to the product of the circle’s diameter times its height. The largest height will be when the triangle’s height equals the circle’s radius: The largest triangle is an isosceles right triangle, which means the rectangle has adjacent sides that are equal. In other words, the rectangle is a square. As calculated in the problem about a “square peg in a round hole,” an inscribed square has area 2r2, which is approximately 64 percent of the circle’s area. Puzzle 5: Infinitely Many Inscribed Circles Inscribe a circle in an equilateral triangle with side length 1. The inscribed circle intersects the equilateral triangle at the three midpoints of its sides. Connect these points to form another equilateral triangle. Now inscribe a circle into the smaller equilateral triangle. Repeat the process indefinitely: draw nested equilateral triangles and inscribed circles. What is the sum of the radii of the infinitely many inscribed circles? Answer To Puzzle 5: Infinitely Many Inscribed Circles We can find the radius of the first inscribed circle using textbook geometry. The radius is the leg of a 306090 right triangle whose longer leg is 1/2. The radius of the first inscribed circle is 1/(2√3). This proportion is true generally since all equilateral triangles are similar. If an equilateral triangle had a different side length, then its inscribed circle would have a radius that is 1/(2√3) of its side length. In the problem, the next equilateral triangle is found by connecting the midpoints of the original triangle. Thus, it has a side length of 0.5. By the logic above, its inscribed circle has a radius that is 1/(2√3) as big as its side length. That is, the radius is 1/(4√3). Each new equilateral triangle is also found by connecting the midpoints of the previous equilateral triangle, so each new triangle has a side length half as big as the previous one. This means each smaller inscribed circle is also half as big as the radius of the previous inscribed circle. The sum of the radii of all the inscribed circles will form an infinite geometric series where the first term is the radius of the first inscribed circle, 1/(2√3), and each new term is 1/2 the previous term. We have the infinite series: Sum of radii = (1/√3) (1/2 + 1/4 + 1/8 + … ) The series inside the parentheses sums to 1, so we can solve the problem. Sum of radii = 1/√3 = √3/3 The sum of the radii is equal to twice the radius (is equal to the diameter) of the largest inscribed circle. Puzzle 6: The Efficient Drink Order Bob wants to buy a drink for his friend. To do so, Bob must walk to the bar, get the drink, and then walk to his friend. There are a variety of paths Bob could walk, as illustrated below. What’s the shortest path he can take? Answer To Puzzle 6: The Efficient Drink Order I had trouble solving this problem, until I remembered some high school geometry. The trick is for Bob to visualize his friend on the other side of the bar. Specifically, he should reflect his friend’s position across the bar. Then, Bob should connect a line from him to this imagined position. This line will intersect the bar at a point C. Bob should walk straight to this point C and then from C to his friend. This will be the shortest path. The proposed solution is easy to follow. But why exactly is it the shortest path? Let’s carefully prove why. To do so, we take a step back and consider an idealized version. Represent Bob by point B and his friend by point A and consider the bar as a line segment. The problem is to find the point C which minimizes the distance: BC + CA How can we determine point C? The trick is to reflect point A across the line segment to its mirror image A’. Now arbitrarily choose a point C along the line segment and draw the line segments CA and CA’. The segments CA and CA’ are mirror images of each other, so they have equal length CA = CA’ So here’s the interesting part. Our original problem was to minimize the distance: BC + CA But we know CA = CA’. So we can rewrite our problem as minimizing the distance: BC + CA’ Which point C minimizes the distance from B to A’? This problem is readily solved: between any two points in a plane, the shortest path is a straight line! So we will draw a line segment between B and A’, and its intersection with the line for the bar gives us the position of C. We can reflect CA’ to get the line segment CA. Since we have minimized the distance (BC + CA’), and we know CA’ = CA, we have also minimized the distance (BC + CA). So the general procedure algorithm is: 1. Reflect point A, across the bar, to its mirror image A’. 2. Draw a line segment from the point B to A’. Denote the intersection point with the bar as C. 3. Draw the line segments BC and CA. This is the shortest path. The same geometric procedure is used to find the best shot in minigolf or in billiards. If we wish to strike a ball so that it bounces off a wall and then goes to a desired target, we can imagine the same diagram. The problem also has a physics application. If a light is bounced off a mirror, then the path it will travel is the shortest distance, which is the path Bob takes to get the drink. When the light bounces off the mirror, the angle of incidence equals the angle of reflection. This problem was described 2,000 years ago and is known as Heron’s problem. It’s quite an interesting geometry problem with many practical applications. Puzzle 7: Circle Length Rectangle ABCO is drawn in circle O as in the following diagram. What is the length of segment AC? Answer To Puzzle 7: Circle Length There are no special formulas needed to solve this puzzle. Note that diagonal OB is a radius of the circle, and the circle has a radius of 5 + 5 = 10. In a rectangle, the two diagonals have the same length. So AC has the same length as OB, and its length is equal to 10. Puzzle 8: Length Of A Spiral A tightly wrapped string makes 4 loops around a cylinder of height 12 and circumference 4. What is the length of the string? Answer To Puzzle 8: Length Of A Spiral The key is unwrapping the cylinder by flattening it out into a rectangle. Each of the spiral’s loops becomes a right triangle. The height of each triangle is the diameter of the cylinder, which is 4, and the length of each triangle is the height divided by 4, which gives 3. So each triangle is a 345 right triangle and the hypotenuse of each is 5. The total string length is four times as long as a single triangle’s hypotenuse. So the answer is 20. Puzzle 9: Ant Cylinder An ant wants to get to honey on a cylinder, as in the following diagram. What is the shortest path the ant can take, and what distance is it? Answer To Puzzle 9: Ant Cylinder There are two tricks to solve this puzzle. One is to unwrap the cylinder so it becomes a rectangle. The other trick is to reflect the position of the honey across the edge of the rectangle. The shortest distance to the position of the reflected honey is a straight line. The mirror image of the path off the edge to the reflected honey also gives the second segment of the shortest path to the honey. This was explained in more detail in the puzzle “Efficient Drink Order.” The distance to the reflected honey is the hypotenuse of a right triangle with legs 3 and 4. So the distance is 5. Puzzle 10: How Many Faces? Consider a tetrahedron and a pyramid whose edges are the same length. If the tetrahedron and the pyramid are attached on a triangular face, how many faces will the new shape have? Answer To Puzzle 10: How Many Faces? This question was asked on a PSAT Exam in 1980. American high school students take the test to qualify to become National Merit Scholars, a prestigious award that may lead to a $2,500 scholarship. The test makers originally stated the correct answer was 7. The tetrahedron has 4 faces and the pyramid has 5 faces. When combined, each loses 1 face, so there are 4 + 5  1  1 = 7 faces in the new shape. One student figured out this answer was wrong. When the two shapes are attached on a triangular face, the two adjacent faces are coplanar and line up perfectly to make one side. So the new shape loses 2 more faces. And so the resulting shape is like a ramp that only has 5 faces. The test makers admitted the mistake and agreed to make 5 an acceptable answer as well. The story is documented in the New York Times, “Youth Outwits Merit Exam, Raising 240,000 Scores.” Edward B. Fiske. March 17, 1981. Puzzle 11: Circle Rotation Circle A has 1/3 the radius of circle B. Circle A rolls around circle B until it returns to its starting position. How many revolutions of circle A are there in total? This problem appeared in the 1982 SAT examination given to American high school students who were applying to college. Here are the answer choices for the question. (a) 3/2 (b) 3 (c) 6 (d) 9/2 (e) 9 What’s the correct answer? Answer To Puzzle 11: Circle Rotation Amazingly, all five answer choices were wrong! The correct answer is 4. The test preparers thought that the small circle, which has 1/3 the radius, would revolve around the large circle 3 times. This would be true if the small circle were rolling in a straight line with length 3 times its circumference. However, the small circle in this problem was also rolling around a circle as well. That motion generates another revolution. Thus, the answer is 4. You can get an idea of this with two coins of the same size: when you roll one coin around the other, it revolves around 2 times. One of the revolutions is because the coins have the same circumference. The other revolution is because the center of the rolling coin is also orbiting the center of the stationary coin. In American currency, you can try this with a quarter coin, but the coin might slip as you try to roll it. I have found it is easier with coins that have thicker edges, like a dollar coin or a halfdollar coin. Credit: I had read about this debacle in a book, but I cannot remember the exact source. There is a nice discussion at Donald Sauter’s website, which quotes an article from the Washington Post newspaper in May 25, 1982. Puzzle 12: NonOverlapping Triangles In the following figure, draw 3 straight lines to make 9 nonoverlapping triangles. Note: this problem appears in the Simpson’s episode “Mathlete’s Feat”, the 22nd and final episode of season 26. Answer To Puzzle 12: NonOverlapping Triangles You have to experiment with drawing the lines. Here’s one solution. Puzzle 13: How Many Partners? The brieflylived CBS show Partners advertised the teaser tagline, “4 friends, 3 couples.” The billboard depicted three men and one woman, leaving the audience in the dark about who is paired. This inspired me to come up with the following math puzzle. In how many ways is it possible to have 3 couples amongst 4 friends? Assume that any two people in the group can form a couple and that people can have multiple simultaneous couplings. Examples of different ways to make 3 couples: 1. The woman could be coupled with each of the three men to make 3 couples in total. 2. Two of the men could form a couple, and one of them could also form a couple with the woman. The woman can also couple with the remaining male member of the group. There are 3 couples in total for this arrangement. Answer To Puzzle 13: How Many Partners? I found a solution using graph theory and combinatorics. We will depict each person as a node, and we can draw a line between two nodes if the two people are coupled. The question is then rephrased: how many ways can we draw 3 edges on a graph with 4 nodes? This is now a combinatorics question. Part 1: How many possible edges can we draw? An edge can connect any of the two nodes together. So we want to connect 2 of the four vertices, which can be done in: (4 choose 2) = 4!/(2! 2!) = 6 possible edges Part 2: How many ways for 3 edges? From the 6 possible edges, we want to select 3 of these lines to make the 3 couples. This means there are: (6 choose 3) = 6!/(3! 3!) = 20 possible couples This result surprised me: I did not realize there would be so many possible combinations. Puzzle 14: Crossed Ladders Two ladders are placed against walls to heights of 3 and 5. What is the height of the point where the ladders cross? What’s a general formula if the ladders are at heights a and b against the walls? Answer To Puzzle 14: Crossed Ladders Suppose the height is h and the ladders are at heights a and b. It will be useful to consider the horizontal distance from the crossing point to the left wall dl and the same distance to the right wall dr. These variables will eventually cancel out, but they will help in the calculation. The triangle formed by the left wall, the distance between the walls, and the left ladder is similar to the triangle formed by the height to crossing, the right distance, and the left ladder to the crossing. This means the ratio of the legs of these triangles is equal. So we have the following. a/(dl + dr) = h/dr h = (adr)/(dl + dr) We can find another set of similar triangles when considering the other ladder to the right wall. So we find the following ratio. b/(dl + dr) = h/dl h = (bdl)/(dl + dr) If we set the two equations for h equal to each other, it is evident that adr = bdl so that dr = (bdl)/a. We can substitute this into the first expression for h. h = (adr)/(dl + dr) h = (bdl)/(dl + bdl/a) h = b/(1 + b/a) h = (ab)/(a + b) Now we have a simple expression for h in terms of the wall heights a and b. When the ladders are against the walls at 3 and 5, then the height of crossing is (3)(5)/(3 + 5) = 15/8 = 1.875. The equation (ab)/(a + b) is half of the harmonic mean of a and b. The harmonic mean is used when adding up two rates of work. For example, if one person paints a house in a hours, and another person does it in b hours, how quickly will they do the job together? The answer is also half the harmonic mean. The crossed ladders problem seems completely unrelated to the problem of working together, and yet they both have the same solution. Quite interesting! Puzzle 15: Fruit Label Stickers Imagine a perfectly round grapefruit that is overly labeled with 5 fruit stickers. Prove that the grapefruit can be cut in two equal halves in which one of the halves has 4 of the 5 stickers. Note: A sticker along the boundary of the cut is counted as being on both halves. Answer To Puzzle 15: Fruit Label Stickers Pick any two stickers on the grapefruit. Now make your cut along the great circle that contains these two stickers (a great circle is a circle on the boundary of a sphere with the same radius as the sphere). These 2 stickers can be counted as being on both of the halves. The remaining 3 stickers have to fit into either of the two halves. The possibilities for (one half, other half) are (3, 0), (2, 1), (1, 2), (0, 3). In each possibility, there is some half that contains at least 2 of these 3 stickers. This half ends up with at least 2 of these stickers, plus the 2 stickers from the boundary cut, for a total of at least 4 of the stickers. Credit: this is adapted from a 2002 Putnam Exam question. Puzzle 16: Castle Height Your army is planning an invasion against a castle. You want to know the height of the castle to calibrate the catapult. In the past, you calculated heights using right triangle trigonometry. Using basic survey tools, you measured the distance to the base of the object, and you also measured the viewing angle from that distance to the height. The height was equal to the distance times the tangent of the angle. But this castle is surrounded by a moat, and you cannot accurately measure the distance to its base. How can you measure the height of the castle? (Assume you take angle measurements from the groundlevel.) Answer To Puzzle 16: Castle Height From one point measure the angle A to the height of the castle. Then go a distance D directly away from the castle. Measure the new angle B to the height, as in the following diagram. We want to solve for h, but we will need to solve for x as an intermediate result. From the diagram, we can deduce: x = h/tan(A) h = (D + x) tan(B) We can substitute the value for x from the first equation into the second and then solve. h = (D + h/tan(A)) tan(B) h(1  tan(B)/tan(A)) = D tan(B) h = D tan(B)/[1  tan(B)/tan(A)] h = D tan(A) tan(B)/[tan(A)  tan(B)] This provides the height of the castle in terms of the known distance D and the two known angles A and B. For example, suppose the distance was 100 and the angles were A = 35 degrees and B = 30 degrees. Then the height would be approximately 329. Puzzle 17: Bumper Cars On A Square Four bumper cars start at different corners of a square arena. Each car is programmed to target the car that starts in the corner counterclockwise to it. Each car moves directly toward its target and keeps adjusting its position so it is always headed straight towards its target. Once the cars collide they will come to a stop. Here is a rough sketch of the path that the cars will take: If one side of the square measures 25 meters, how much distance does each bumper car travel before collision? Answer To Puzzle 17: Bumper Cars On A Square This problem is more generally known as the mice problem. It can be solved using calculus. But we don’t really need to do that. The trick is to consider movement from the perspective of one car. The bumper car travels directly toward its target, which moves at a right angle to the line connecting the bumper car and its target, as pictured here: Since the bumper car is always continuously adjusting its position towards its target, the perspective will be the same as if the bumper car were moving directly towards its target along the square. Therefore, the distance until they collide is the same as the distance of one side of the square, 25 meters. In other words, the bumper cars would have moved the same distance if each was targeted to go to its adjacent corner. Credit: I read about this in a column by Barry Nalebuff, Puzzles: Slot Machines, Zomepirac, Squash, and More. published by the American Economics Association Winter 1990. Puzzle 18: Optimize The Fence You have 100 units of fencing. You want to enclose 3 sides of a rectangular area, with the 4th side of the rectangle being a river. What is the maximum area you can enclose? Answer To Puzzle 18: Optimize The Fence There are two ways to solve this problem. I’ll explain the standard method first and then go over the creative solution. Suppose the rectangle has side x parallel to the river and has two sides y perpendicular to the river. The perimeter of the rectangular shape is x + 2y = 100, which means x = 100  2y. The area enclosed is xy. We can substitute for x to get an area in terms of the single variable y. Area = (100  2y)y We can solve for the maximum area either graphically or using calculus. If we take the derivative and set it equal to zero, we can solve for the maximum area as follows. Derivative of Area = 100  4y = 0 y = 25 We can then find x = 100  2(25) = 50, and so the area is xy = (50)(25) = 1,250. This is a direct method, but there is a clever method to solving it faster! Geometric Method Reflect the 3sided rectangle across the river to make a rectangle. The big rectangle has a perimeter of 2x + 4y, which is double the perimeter of the original shape. Also, the area is also twice the area of the original shape. Therefore, if we enclose the largest area for a given perimeter of this big rectangle, we will simultaneously solve for the largest area of the 3sided shape. For a given perimeter, what’s the rectangle that encloses the most area? The answer is a square. Why? Note that a rectangle with sides a < b has the same perimeter as the square with sides a + x = b  x. That is, we remove a bit of the larger side until the two sides are equal. The square has an area of (a + x)2 = a2 + 2ax + x2. This is larger by x2 compared to the rectangle with unequal sides, which has an area ab = a(a + 2x) = a2 + 2ax. So the rectangle that encloses the largest area for a given perimeter is a square. Returning to the original problem, we can maximize the big rectangle by making it a square. This means its two sides of x and 2y must be equal. This will also optimize the enclosed area for the small rectangular shape with 3 sides. In that figure, we had 100 units of fencing, which meant x + 2y = 100. Now we know x = 2y, so we can substitute to get 2y + 2y = 100 and so y = 25. Then we have x = 50. And the area is xy = (50)(25) = 1,250. It’s the same answer and does not require calculus. Plus you can solve all related problems of maximizing a 3sided rectangle by setting the single side parallel equal to 2 times a perpendicular side. Puzzle 19: Cylinder Height Canned food comes in many different sizes and shapes. You want to produce a cylindrical can that requires the minimum material (surface area) for a given volume. What ratio should you make the can’s height to its radius? Answer To Puzzle 19: Cylinder Height Let the cylinder have a radius r and a height h. The volume of the cylinder is (base)(height) = (area of circle)(height) = πr2h. The surface area of the cylinder is (2 area base) + (area tube) = 2πr2 + 2πrh. For a given volume V = πr2h, we can solve for the height as h = V/(πr2). Now we substitute that into the equation for surface area. Surface Area = 2πr2 + 2πr(V/(πr2)) Surface Area = 2πr2 + 2V/r Now the surface area is given as a function of one variable r, and we can take the derivative to find a condition for the minimum surface area. Derivative of Surface Area = 4πr  2V/r2 = 0 Which implies V = 2πr3 Now we have the minimum surface area is when V = 2πr3. But for any cylinder, the volume is given by V = πr2h. Equating those expressions, we find the minimum surface area happens when h = 2r. In other words, the height should be twice the radius. Puzzle 20: Connect Four Towns Four towns are located on the corners of a square with side length 1. A networking company wants to connect all four towns using straight lines and the least possible wiring. Can you think of an efficient method? You need not prove the answer is optimal, but if you find a good solution, calculate the amount of wiring necessary. Answer To Puzzle 20: Connect Four Towns The problem of finding the shortest interconnect between a set of points is known as the Steiner tree problem. The interesting thing is extra points, known as Steiner points, can serve as intermediate connections that reduce the total length of connections. For example, the most obvious solution to the unit square is to connect the diagonal points. Each diagonal has a length of √2, so the total wiring is twice as long, 2√2 ≈ 2.83. Can we do any better? Surprisingly we can! There are interesting patterns in soap bubbles or bubbles while boiling rice that can illustrate how one might have discovered the following unusual path of wiring. Consider two points at a height of 1/2, each at a horizontal distance of x from a side of the square, and draw the connections as follows. Let’s solve for the value of x that minimizes the total wiring length. The one horizontal line has length 1  2x. The remaining four lines are congruent, and they are equal to the length of a hypotenuse of a right triangle with legs x and 1/2. The length of each hypotenuse is √(1/4 + x2), and we multiply that by 4 to get the total length. The total length is the following equation. Length = 1  2x + 4√(1/4 + x2) We can minimize this by taking the derivative and setting it equal to zero. Derivative of Length = 2 + (4x)/√(1/4 + x2) = 0 √(1/4 + x2) = 2x 1/4 + x2 = 4x2 3x2 = 1/4 x = 1/(2√3) [ignore negative solution] When we evaluate the length at this value of x, the result is a total interconnection length of 1 + √3 ≈ 2.73. Note this is less than the result of 2.83 when we connected the diagonal points! It turns out this unusual pattern is the shortest way to connect the four towns. You can read up on the Steiner tree problem to see how one might prove this interesting result. Section III: Probability And Game Theory These problems are about games of chance and randomness. Puzzle 1: Which Lane Is Better? You’re on a twolane highway and there are cars ahead of you in both lanes. You want to go straight ahead, but some of the cars in front of you might slow down to turn and delay you. You are in the left lane. In that lane, there are 3 cars, each with an independent 20 percent chance of stopping to turn. If any of the cars stop, you have to stop too. Over in the right lane there is only one car. But your experience indicates a 50 percent chance the car will stop to turn. Which lane are you better off in? Answer To Puzzle 1: Which Lane Is Better? In the left lane, there are 8 possible ways the 3 cars might decide to stop (S) or not (N): SSS, SNS, SNN, SSN, NSS, NNS, NSN, NNN. You have to stop if even one car stops. So you want to know the event in which no car stops. The probability a single car does not stop is 0.8, calculated as 1 minus the probability it does stop. The probability of NNN is (0.8)3 = 51.2 percent. In the right lane, the car stops with a 50 percent chance, so it will not stop with a 50 percent chance. You have a slightly better chance of not stopping in the left lane. Puzzle 2: Medical Conspiracies A 2014 study from the University of Chicago found that many American adults do not completely trust the medical profession. It found that about 1/2 of adults believed in at least 1 conspiracy out of the 6 conspiracies posed to them. Should this be surprising? Summary: “You’re Not Alone: Medical Conspiracies Believed By Many”. Andrew M. Seaman. Reuters. Accessed at Reuters.com Study: “Medical Conspiracy Theories and Health Behaviors in the United States.” J. Eric Oliver, Thomas Wood. JAMA Intern Med. 2014;174(5):817818. doi:10.1001/jamainternmed.2014.190. Accessed at Jama Network.com. Answer To Puzzle 2: Medical Conspiracies The result is less shocking than the title indicates. Suppose an adult had 90 percent confidence in published medical results. When presented with 6 conspiracies, the chance of disagreeing with all 6 is the chance of siding with 6 published medical results: (0.90)6 = 53 percent. In other words, the chance of believing at least 1 conspiracy is about 47 percent. On the other hand, if medical results were held to a 95 percent confidence level (as they meet the 5 percent significance level), then the chance of disagreeing with all 6 conspiracies should be (0.95)6 = 74 percent. But even then, there would be 26 percent–more than 1 in 4 adults–that would still agree with at least 1 medical conspiracy. Puzzle 3: Cards In Three Piles Here’s a game you can bust out at parties on your less mathematically inclined friends. Offer the other person a standard deck of cards and tell them to shuffle it in any way they like. Now tell them to divide the deck into 3 equal piles of 14 cards each, with the cards facing down (no peeking!). Separate the top card from each pile. Here’s how the payouts work. Tell them your “lucky” cards are aces, fours, and jacks. You will win $1 from your friend if any of the top cards is revealed to be a lucky card. Otherwise, you pay $1 to your friend. It seems like the odds are against you as you only win on aces, fours and jacks. If you play for a while, you will win a bit more on average, and someone might challenge that you have rigged the deck in some way. But there’s no sleight of hand required in this game. Can you figure out why the game is to your advantage? Answer To Puzzle 3: Cards In Three Piles It’s true you only win on the 12 cards that are aces, fours, and jacks. But you also get 3 tries to win, and that’s how the game works out in your favor. The way to proceed is to calculate the probability the other person will win–that none of the cards shown is an ace, a four, or a jack. The probability the first card is not an ace, a four, or a jack is 40/52: there are 40 such cards out of the entire deck. For the second card, there are now remaining 39 safe cards out of 51. So that chance is 39/51. For the final card, there are 38 out of 50 safe cards. The chance the other person wins is the product of these probabilities: Pr(other person wins) = (40/52)(39/51)(38/50) = 0.447… Remarkably the other person has less than a 50 percent chance of winning. The probability you win is the complementary probability, which is a tad over 55 percent. The game does not appear to be in your favor, but the odds are and that’s what makes it a good sucker bet. Credit: I read about this in Mathematical Magic by William Simon. Puzzle 4: Random Music People were so angry at Apple’s iPod shuffle function replaying the same songs that a conspiracy theory developed that Apple was replaying particular songs to boost their popularity. Many people have felt angry that music devices do not properly randomize their music. But maybe it’s all just a coincidence? Let’s explore the mathematics of randomness in the following problem. Bob likes to listen to soft music in the morning, so he makes a playlist of 3 songs that he plays on shuffle/random. If Bob listens to 3 songs, what is the probability he will hear all 3 different songs? Assume the shuffle function is purely random. That is, for any song that is playing, each of the songs A, B, and C has an equal chance of being played next. What if there are n songs in a playlist put on shuffle? Then what are the odds the first n songs are all n different songs? Answer To Puzzle 4: Random Music If Bob hears song A first, there are 9 equally likely possibilities for the next 2 songs played. AA, AB, AC, BA, BB, BC, CA, CB, CC Of those 9, only 2 possibilities correspond to hearing all three songs: BC and CB. The probability Bob will listen to all 3 songs is 2/9, a modest 22 percent. In other words, there is a 78 percent chance