Główna Math Puzzles Volume 3: Even More Riddles And Brain Teasers In Geometry, Logic, Number Theory, And...
Zgłoś problemThis 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.
Change your answer
Możesz być zainteresowany Powered by Rec2Me
Najbardziej popularne frazy
Copyright Presh Talwalkar 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 decision-making, 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 brain-teasers. Math Puzzles Volume 2: More Riddles And Brain Teasers In Counting, Geometry, Probability, And Game Theory. This is a follow-up 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 thought-provoking 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 You Should Study Math Puzzles This is the third book I am publishing about mathematical brain teasers and riddles. What is the point of all of these math problems? From a practical perspective, math puzzles can help you get a job. They have been asked during interviews at Google, Goldman Sachs, as well as other tech companies, investment banks, and consulting firms. Math puzzles also serve a role in education. Because puzzles illustrate unexpected solutions and can be solved using different methods, they help students develop problem solving skills and demonstrate how geometry, probability, algebra, and other topics are intimately related. Math puzzles are also great for practice once you are out of school. But mostly, math puzzles are worthwhile because they are just fun. I like to share these problems during parties and holidays. Even people who do not like math admit to enjoying them. So with that, I hope you will enjoy working through this collection of puzzles as much as I have enjoyed preparing the puzzles and their solutions. This book is organized into easy, medium, and hard puzzles. 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 higher-level mathematics, like knowledge of probability distributions or calculus. Each puzzle is immediately accompanied with its solution, as I have done in the other two math puzzle ebooks. 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. Table of Contents Part I: Easy Puzzles Puzzle 1: Triangle Ratios Answer To Puzzle 1: Triangle Ratios Puzzle 2: Nine Dots Answer To Puzzle 2: Nine Dots Puzzle 3: Six Boxes Answer To Puzzle 3: Six Boxes Puzzle 4: Divide Into 4 Answer To Puzzle 4: Divide Into 4 Puzzle 5: Circles In Triangles Answer To Puzzle 5: Circles In Triangles Puzzle 6: Area Of Triangle Answer To Puzzle 6: Area Of Triangle Puzzle 7: Covering A Chessboard Answer To Puzzle 7: Covering A Chessboard Puzzle 8: A Matchstick Problem Answer To Puzzle 8: A Matchstick Problem Puzzle 9: Medicine Answer To Puzzle 9: Medicine Puzzle 10: Rope Burning Answer To Puzzle 10: Rope Burning Puzzle 11: Cheryl's Birthday Answer To Puzzle 11: Cheryl's Birthday Puzzle 12: Cheryl's Hat Color Answer To Puzzle 12: Cheryl's Hat Color Puzzle 13: Four Hats Answer To Puzzle 13: Four Hats Puzzle 14: Water Jug Answer To Puzzle 14: Water Jug Puzzle 15: Dehydrated Food Answer To Puzzle 15: Dehydrated Food Puzzle 16: Crossing Trains Answer To Puzzle 16: Crossing Trains Puzzle 17: Monks Crossing Answer To Puzzle 17: Monks Crossing Puzzle 18: Crossing Trucks Answer To Puzzle 18: Crossing Trucks Puzzle 19: Slicing Vegetables Answer To Puzzle 19: Slicing Vegetables Puzzle 20: Moving Walkway Answer To Puzzle 20: Moving Walkway Puzzle 21: Wind Speed Answer To Puzzle 21: Wind Speed Puzzle 22: Michelson-Morley Answer To Puzzle 22: Michelson-Morley Puzzle 23: Smartphone Battery Answer To Puzzle 23: Smartphone Battery Puzzle 24: Vietnam Problem Answer To Puzzle 24: Vietnam Problem Part II: Medium Puzzles Puzzle 1: Paths Home Answer To Puzzle 1: Paths Home Puzzle 2: Two Sequences Answer To Puzzle 2: Two Sequences Puzzle 3: 100 Lamps Answer To Puzzle 3: 100 Lamps Puzzle 4: Trailing Zeroes Answer To Puzzle 4: Trailing Zeroes Puzzle 5: Number Of Digits Answer To Puzzle 5: Number Of Digits Puzzle 6: Odd Even Sequence Answer To Puzzle 6: Odd Even Sequence Puzzle 7: Divisible By 3 Answer To Puzzle 7: Divisible By 3 Puzzle 8: Two Be Or Not Two Be Answer To Puzzle 8: Two Be Or Not Two Be Puzzle 9: Infinite Fraction Answer To Puzzle 9: Infinite Fraction Puzzle 10: Nested Radical Answer To Puzzle 10: Nested Radical Puzzle 11: Infinite Exponents Answer To Puzzle 11: Infinite Exponents Puzzle 12: Guess My Polynomial Answer To Puzzle 12: Guess My Polynomial Puzzle 13: Find The Missing Number Answer To Puzzle 13: Find The Missing Number Puzzle 14: Poisoned Beer Answer To Puzzle 14: Poisoned Beer Puzzle 15: 100 Passengers Answer To Puzzle 15: 100 Passengers Puzzle 16: 100 Floors Answer To Puzzle 16: 100 Floors Puzzle 17: 3 Locks Answer To Puzzle 17: 3 Locks Puzzle 18: Which Foul? Answer To Puzzle 18: Which Foul? Puzzle 19: Choosing With A Coin Answer To Puzzle 19: Choosing With A Coin Puzzle 20: Sex Ratio Answer To Puzzle 20: Sex Ratio Puzzle 21: Unfound Errors Answer To Puzzle 21: Unfound Errors Puzzle 22: Random Penalty Kicks Answer To Puzzle 22: Random Penalty Kicks Puzzle 23: Highest Number Almost Always Wins Answer To Puzzle 23: Highest Number Almost Always Wins Puzzle 24: Race To 15 Answer To Puzzle 24: Race To 15 Part III: Hard Puzzles Puzzle 1: Probability Of Forming A Triangle Answer To Puzzle 1: Probability Of Forming A Triangle Puzzle 2: Three Napkins Answer To Puzzle 2: Three Napkins Puzzle 3: Hidden Treasure Answer To Puzzle 3: Hidden Treasure Puzzle 4: Buffon's Needle Answer To Puzzle 4: Buffon's Needle Puzzle 5: 52 Cards From 52 Decks Answer To Puzzle 5: 52 Cards From 52 Decks Puzzle 6: Random Holidays Answer To Puzzle 6: Random Holidays Puzzle 7: Matching Cards Answer To Puzzle 7: Matching Cards Puzzle 8: Avoid A Red Card Answer To Puzzle 8: Avoid A Red Card Puzzle 9: Broken Coffee Machine Answer To Puzzle 9: Broken Coffee Machine Puzzle 10: Straw That Broke The Camel's Back Answer To Puzzle 10: Straw That Broke The Camel's Back Puzzle 11: Random Numbers Ratio Answer To Puzzle 11: Random Numbers Ratio Puzzle 12: πe or eπ? Answer To Puzzle 12: πe or eπ? Puzzle 13: Guess The 1,000th Number Answer To Puzzle 13: Guess The 1,000th Number Puzzle 14: How Many Primes? Answer To Puzzle 14: How Many Primes? Puzzle 15: Powers Of 2 Answer To Puzzle 15: Powers Of 2 Puzzle 16: Smaller Envelope Answer To Puzzle 16: Smaller Envelope Puzzle 17: Russian Roulette Option Answer To Puzzle 17: Russian Roulette Option Puzzle 18: Group Testing Answer To Puzzle 18: Group Testing Puzzle 19: Basketball Knockout Answer To Puzzle 19: Basketball Knockout Puzzle 20: Cards On A Square Answer To Puzzle 20: Cards On A Square Puzzle 21: Even Betting Puzzle 21: Answer To Even Betting Puzzle 22: Rolling A 100-Sided Die Answer To Puzzle 22: Rolling A 100-Sided Die Part I: Easy Puzzles Puzzle 1: Triangle Ratios A circle is inscribed in an equilateral triangle. Then an equilateral triangle is drawn inside the circle, as pictured below. What is the ratio of the area of the smaller equilateral triangle to the larger equilateral triangle? Answer To Puzzle 1: Triangle Ratios There's no need to do complicated calculations. The easiest way is to rotate the triangle inside the circle to get the following figure. Now the answer is obvious! The large equilateral triangle is divided into 4 small equilateral triangles: three of them are facing "up" while the shaded one is facing "down." Since 4 small equilateral triangles make up the 1 large equilateral triangle, the shaded triangle is 1/4 the area of the larger equilateral triangle. Puzzle 2: Nine Dots Connect the all the dots without lifting your pen, using at most 4 straight lines, and without retracing any of the lines. Answer To Puzzle 2: Nine Dots Here is one way you can solve the puzzle. The trick is to think "outside the box." Puzzle 3: Six Boxes Connect boxes of the same letter with lines. The lines cannot intersect and they have to stay inside of the boundary of the bordering box. Answer To Puzzle 3: Six Boxes Here is one way to solve the puzzle. To connect the two boxes with the letter B, wrap the line around the boxes for the letters A and C. Then there will be enough room to connect the remaining boxes without having to cross the path of any existing line. Puzzle 4: Divide Into 4 Divide the following shape into 4 equal parts, where each part is the same shape and size. The dimensions are not listed because the figure is drawn to scale. Answer To Puzzle 4: Divide Into 4 There's a neat trick to solve the puzzle: you can break the shape into 4 smaller copies of itself. Puzzle 5: Circles In Triangles Infinitely many circles are inscribed into an isosceles triangle with sides of 10, 13, and 13, as shown in the following diagram. What is the sum of the circumferences of all the circles? Answer To Puzzle 5: Circles In Triangles You could solve for the circumference of each circle. An inscribed circle in a triangle has a radius equal to the area of the triangle divided by its semi-perimeter. In this problem, the largest circle has a radius of 60/18 = 10/3. By similar triangles, one could find out the ratio of each smaller circle. Skipping the details, each subsequent circle can be found to be 4/9 of the previous circle. The largest circumference is 2r π = (20/3) π and each subsequent circumference is 4/9 of that. So we could solve the problem by summing the infinite geometric series starting with (20/3) π and having a common ratio of 4/9. (20/3) π(1 + 4/9 + (4/9)2 + ... ) (20/3) π[1/(1-4/9)] (20/3) π[9/5] 12 π But there is a much easier way to solve this problem! Draw the altitude of the triangle, which divides the base of 10 into two equal segments of 5. The isosceles triangle is now divided into two right-triangles with a hypotenuse of 13 and a leg of 5. Therefore this must be a 5-12-13 right triangle, meaning the altitude of the isosceles triangle is 12. Furthermore, the length of the altitude is exactly equal to the sum of the diameters of all of the circles. The sum of the circumferences is π (sum of the diameters) = π (length of altitude) = 12 π. Credit: I read about this problem in Aha! Solutions by Martin Erickson. Puzzle 6: Area Of A Triangle Pictured below are four right triangles, each with a hypotenuse of 3. The larger leg is 1 unit longer than the shorter leg. What's the area of a single triangle? Answer To Puzzle 6: Area Of A Triangle The answer is 2. Just like the last puzzle, there is a hard way and an easy way to arrive at the answer. The hard way is to use algebra. If you label the longer leg as a and the shorter leg as b, then we are given a = b + 1. We can use the Pythagorean Theorem to arrive at the equation a2 + b2 = 32. Substituting for a, we get (b + 1)2 + b2 = 2b2 + 2b + 1 = 9. Now we simplify to get 2b2 + 2b = 8, and then we divide by 2 to get b2 + b = 4. The good part is we do not have to solve this equation. We ultimately want to find the area of the triangle, which is ab/2 = (b + 1)b/2 = (b2 +b)/2. Since we derived that b2 + b = 4, we can divide the equation by 2 to find (b2 +b)/2 = 2. Thus, the area of a single triangle is 2. There is a much more elegant way to solve this puzzle. Rearrange the four triangles to make a big square with a small square removed, as shown in the following diagram. The area of the outer square with dimensions 3x3 is equal to the area of the 4 triangles plus the area of the internal square with dimensions 1x1. Therefore, 3x3 = (area 4 triangles) + 1x1. In other words, 3x3 – 1x1 = (area 4 triangles). This simplifies to 8 = (area 4 triangles). We divide this equation by 4 and conclude the area of a single triangle is 2! Incidentally, this rearrangement of four right triangles into the shape of a square with a smaller square inside is one method to prove the Pythagorean Theorem, credited to the Indian mathematician Bhaskara. Behold! For a general right triangle with legs a and b, and a hypotenuse c, you can construct a square with side c composed of the four of the right triangles and a small square with side a - b. One way to compute the area of the square is by squaring its side, so the area is c2. The other way to compute the area of the square is to add up the areas of the 4 triangles and the small inside square. The area of the 4 triangles is 2ab and the area of the small square is (a - b)2 = a2 + b2 - 2ab. The sum of the areas of the triangles and the square is a2 + b2, and this equals the area of the entire square, c2. Therefore we have proved the Pythagorean Theorem a2 + b2 = c2. I credit this puzzle to a reader of the Mind Your Decisions blog, Danny, who was inspired by the geometry of the UK flag. Puzzle 7: Covering A Chessboard A standard chessboard is a grid of 8 by 8 squares. You have dominoes that cover 2 squares at a time (that is, they measure 2 by 1). If two opposite corners of the chessboard are removed, can you cover the remaining 62 squares with 31 dominoes? Answer To Puzzle 7: Covering A Chessboard It is actually impossible to cover the board. The easiest proof involves coloring alternate squares of the board. A chessboard alternates between black and white squares. Because each row has 8 squares and each column has 8 squares, there is a pattern in the coloring of the squares. In any given row, the first and last squares always have opposite colors. Similarly, in any given column, the first and last squares always have opposite colors. Putting these two facts together, we can reason that two diagonally opposite corners must have the same color. When two diagonally opposite corners are removed, that means two squares of the same color are removed. Hence, the board contains 30 squares of one color and 32 squares of the other. Each domino covers two adjacent squares, one white and one black. This means any arrangement of dominos must also cover an equal number of black and white squares. It is therefore impossible to cover a board with 30 squares of one color and 32 of the other using 2 by 1 dominos! Puzzle 8: A Matchstick Problem This puzzle is short but challenging. Using 6 matches, create 4 triangles of the same size. Answer To Puzzle 8: A Matchstick Problem The trick is to think in 3 dimensions. The 6 matches can be arranged into a tetrahedron whose 4 faces are triangles of equal size. Puzzle 9: Medicine To stay alive, you have to take 1 pill of medicine A and 1 pill of medicine B daily. You take out 1 pill of medicine A and hold it. Then you lift the bottle for medicine B and tap out a pill into your hand. The only problem is 2 pills come out instead of just 1. Then you realize something scary: all three pills look indistinguishable to you, as they were foolishly manufactured to be the same size, shape, and color. Now you're in a bit of a jam. You need to take 1 pill each of medicine A and medicine B, but you don't know which pill is of what medicine. How can you do this, without throwing any of the pills away? Answer To Puzzle 9: Medicine Take out 1 more pill of medicine A and add it to the 3 pills. Carefully split each pill in half, placing one half into a Left pile and the other half into a Right pile. Now the Left and Right piles each contain 4 pill halves that came from 2 pills of medicine A and 2 pills of medicine B. Therefore, each pile contains the equivalent of 1 pill of medicine A and 1 pill of medicine B. Consume one pile today and the other pile the next day. Of course, there are some medicines that cannot be split into half. But many medicines can, and devices like pill splitters exist. Technically the problem should specify the pills can be split in half, but emphasizing that detail essentially spoils the fun of the puzzle. Puzzle 10: Rope Burning You have a lighter and two ropes. Each rope burns up in 1 hour from end to end, but the ropes do not burn evenly. How can you measure 45 minutes by burning the ropes? Challenge: how would you measure 50 minutes? Answer To Puzzle 10: Rope Burning First arrange the two ropes so you are holding all four of the rope ends. At the start, light both ends of rope A and one end of rope B. Exactly when rope A burns up, light the other end of rope B. The time from the start to when rope B burns up is exactly 45 minutes. To see why, first note that it takes rope A exactly 30 minutes to burn up. Intuitively this makes sense. If rope A burns in 60 minutes with one flame, then it would burn in 30 minutes = 60/2 with two flames. (*more precise proof below) After 30 minutes, some amount of rope B is left. By similar logic, it will take 15 minutes to burn what remains of rope B with two flames. Therefore, the total time to burn both ropes is 30 + 15 = 45 minutes. How would you measure 50 minutes? We can measure 30 minutes by burning one rope at both ends, so we can solve this if we can measure 20 minutes using the other rope. Since a rope burns in 30 minutes = 60/2 with two flames, the idea is a rope will burn 20 minutes = 60/3 if we can keep 3 flames going. How do we do that? Light the rope at one end and somewhere in the middle. Now the rope will burn with 3 flames. At some point, the two flames headed towards each other might meet and cancel each other out. At exactly that instant, light the remaining rope somewhere in the middle to keep 3 flames going. Repeating this process as many times as needed (infinitely), the rope will always burn with 3 flames and so it will burn in 20 minutes. *More precise proofs Proof A: Think about rope A as the interval [0, 1]. We can burn the interval from either endpoint. In 30 minutes, we would burn either [0, x] or [y, 1]. In the next 30 minutes, we would burn [x, 1] or [0, y] as the entire rope burns in 60 minutes. Both the intervals [0, x] or [0, y] burn in 30 minutes time. This implies x = y. Hence, burning from both ends we burn [0, x] and [x, 1]--that is, the entire rope--in a matter of 30 minutes. Similarly, think about rope B as the interval [0, 1]. After 30 minutes some portion remains, call it [0, z]. We can burn this starting from either end, and we can show the intervals [0, w] and [w, z] would burn in 15 minutes each. So if we burn from both ends, the remaining rope would burn up in 15 minutes. Proof B: For the 3 flames case, we will keep track of the distances burned by whichever flame is the single flame as a sequence s1, s2, ..., sn and the distances burned by the pair of flames going towards each other as p1, p2, ..., pn, corresponding to the time periods t1, t2, ..., tn. From Proof A above, the pair of flames burns distances in half the time a single flame would take. So the distances p1, p2, ..., pn are burned in half the time the single flame would take. Since these distances are burned in time periods of t1, t2, ..., tn, that means it would have taken the single flame 2t1, 2t2, ..., 2tn to burn the same distances. For the single flame to burn the entire rope, it needs to burn distances of s1, s2, ..., sn, p1, p2, ..., pn. The total time it would take is equal to t1 + t2 + ... + tn + 2t1 + 2t2 + ... 2tn = 3t1 + 3t2 + ... 3tn. We can equate this to 60 because a single flame burns the entire rope in 60 minutes. So we have 3t1 + 3t2 + ... 3tn = 60. Dividing by 3, we get t1 + t2 + ... tn = 20. In other words, a rope with 3 flames simultaneously burns in 20 minutes. Puzzle 11: Cheryl's Birthday A version of this problem appeared as a Math Olympiad question for high school students in Singapore. In April 2015, it was posted to Facebook, and the problem soon went viral generating debate about the correct answer. Here is the setup. Albert and Bernard have just become friends with Cheryl, and they want to know when her birthday is. Cheryl gives them a list of 10 possible dates. May 15, May 16, May 19 June 17, June 18 July 14, July 16 August 14, August 15, August 17 Cheryl tells Albert only the month and Bernard only the day. Albert says, “I don't know when Cheryl's birthday is, but I know for sure that Bernard cannot know either.” Bernard then says, “At first I didn't know when Cheryl's birthday is, but now I do know.” Albert concludes, “Now I know when Cheryl's birthday is too.” So when is Cheryl's birthday? It seems impossible, but you can figure it out from the information given! Answer To Puzzle 11: Cheryl's Birthday The answer is July 16. What is more interesting is why this is the correct answer. Start by looking at the dates again. May 15, May 16, May 19 June 17, June 18 July 14, July 16 August 14, August 15, August 17 Albert is told one of the months May, June, July, or August. And Bernard is told one of the days 14, 15, 16, 17, 18, or 19. Albert first says, “I don't know when Cheryl's birthday is, but I know that Bernard cannot know either.” The first part of the sentence is obvious because of course Albert doesn't know the day. But the second part is a clue. Albert is sure that Bernard cannot know the date. If Bernard was told 19, he would know the birthday was May 19 because that day is unique to one date. Similarly, if Bernard was told 18, he would know the birthday was June 18. How is Albert sure that Bernard didn't hear 18 or 19? It must be because Albert knows the birthday is not in May or June. In other words, Albert was told either July or August. So the first sentence reduces our list to 5 dates. July 14, July 16 August 14, August 15, August 17 Bernard then says, “At first I didn't know when Cheryl's birthday is, but now I do know.” Upon hearing Albert's statement, Bernard figured out the month must be July or August. He then also said now he could figure out the birthday. If he had been told 14, the month would still be ambiguous. So he must have been told 15, 16, or 17. So Albert is left with 3 possible dates. July 16 August 15, August 17 Albert finally explains, “Now I know when Cheryl's birthday is too.” If Albert was told August, he still would not be sure. So he must have been told July. Therefore, Cheryl said July to Albert and 16 to Bernard. Cheryl's birthday is July 16. Puzzle 12: Cheryl's Hat Color Albert, Bernard and Cheryl have to solve a logic puzzle for math class. The teacher lines them up with Cheryl in front, Bernard in the middle, and Albert in the back. The teacher blindfolds them and puts either a white or black hat on each person. The hats, the teacher announces, are chosen from a group of 3 black and 2 white hats. The teacher removes the blindfolds and asks, “Does anyone know the color of hat I put on them? If anyone can figure it out, you all pass this test.” Albert, who can see both Bernard's and Cheryl's hat colors, goes first. He disappointingly says, “I don't know.” Bernard, who can see Cheryl's hat color, goes next. He also says, “I don't know.” At this point the situation looks bad for the group. Cheryl is in the front of the line and cannot see anyone's hat color. But suddenly Cheryl exclaims, “I know!” Cheryl explained her answer and it was correct. What was Cheryl's hat color, and how did she know? Answer To Puzzle 12: Cheryl's Hat Color Cheryl must have been wearing a black hat. If Albert saw two white hats, he would know he has a black hat. So when Albert says “I don't know,” that means he saw at most one white hat. If Bernard then saw a white hat he would know he must have a black hat. So when Bernard says “I don't know,” that means he saw Cheryl had a black hat. Upon hearing Albert and Bernard say “I don't know,” Cheryl could figure out for sure that she had a black hat. Here is a longer explanation. Imagine Cheryl was wearing a white hat. Then either Bernard has a white hat, Albert has a white hat, or both Albert and Bernard have black hats. We can write the cases where B means black, W means white, and we write the hat colors in order of Albert, Bernard and Cheryl. BWW WBW BBW Let's consider BWW. This hat coloring means Albert saw two white hats. But if Albert saw two white hats, he would know he is wearing a black hat, as there are only two white hats in total. When Albert says, “I don't know,” Cheryl can exclude BWW. Similarly, let's consider WBW and BBW. After Albert says “I don't know,” Bernard can be sure Albert is not seeing two white hats. So if Bernard sees a white hat on Cheryl, he can be sure his own hat color must be black. When Bernard says, “I don't know,” Cheryl can exclude WBW and BBW as possibilities. In summary, if Cheryl was wearing a white hat then either Albert or Bernard would have deduced their hat color. After Albert and Bernard say “I don't know,” Cheryl can figure out she was wearing a black hat. Surprisingly Cheryl, who cannot see anyone's hat, can figure out her own hat color while the others cannot. This is a rare puzzle that shows you can sometimes learn from your ears more than you can see with your eyes. Puzzle 13: Four Hats A villain has taken 4 captives. He offers them a chance to go free if they can solve a puzzle. He lines up three of the prisoners (A, B, and C) and a fourth prisoner D is placed in a separate room. A B C | D Each captive is wearing a hat. The villain explains to everyone there are 2 blue hats and 2 red hats. If anyone can guess the color of his hat, then they all are set free. No communication is allowed. The only information is that captive A can see the colors of the hats on captives B and C; and captive B can see the color of the hat on captive C. Here is the arrangement of colors: A(blue) B(red) C(blue) | D(red) After a couple of minutes, one of the captives calls out an answer. Who makes the guess and what color? Answer To Puzzle 13: Four Hats It is captive B who can figure out he is wearing a red colored hat. How can that be? Recall the distribution of hats. A(blue) B(red) C(blue) | D(red) Captive B makes his guess based on the following observation. All captive B sees is a blue hat on captive C. His hat could either be red or blue, but he is not sure. However, he reasons as follows. What if his hat were colored blue? In that case, captive A would be looking at two blue hats on captives B and C. This immediately would indicate to captive A that his hat must be colored red, and captive A would have called out his answer promptly. But since captive A kept quiet for a couple of minutes, he must not have been sure. That is, captive A must have been looking at one red and one blue hat. And since B knows C is wearing a blue hat, it must be the case that he is wearing a red hat. Puzzle 14: Water Jug This problem was featured in the film Die Hard With a Vengeance. You have a 3-gallon and a 5-gallon jug that you can fill from a fountain of water. How can you fill exactly 4 gallons of water? Answer To Puzzle 14: Water Jug Some people estimate 4 gallons by adding 3 gallons of water to 1/3 of the 3 gallon jug. But the riddle is asking for a precise measurement and so this solution does not work. The trick is to realize 5 - 3 = 2, which means 3 - (5 - 3) = 1, and so 5 - (3 - (5 - 3)) = 4. In other words, it is possible to obtain 4 gallons from operations involving 3 and 5 gallons. Here is one way to find the answer. 1. Fill up the 5-gallon jug. 2. Fill up the 3-gallon jug using the water from the 5-gallon jug (leaving 2 gallons in the 5-gallon jug). 3. Pour out the 3-gallon jug into the fountain. 4. Transfer the 2 gallons from the 5-gallon jug into the 3-gallon jug. 5. Fill up the 5-gallon jug. 6. Transfer water from the 5-gallon jug until the 3-gallon jug is full. Since the 3-gallon jug already had 2 gallons of water, there is room for just 1 gallon. 7. The amount of water in the 5-gallon jug is precisely 4 gallons. If we denote the contents of the jugs as the pair (5-gallon jug amount, 3-gallon jug amount), the sequence of events is the following: (5, 0)-->(2, 3)-->(2, 0)-->(0, 2)-->(5, 2)-->(4, 3) That's not the only solution. Here is another way to obtain 4 gallons. 1. Fill up the 3-gallon jug. 2. Transfer to the 5-gallon jug. 3. Fill up the 3-gallon jug again. 4. Transfer water to fill up the 5-gallon jug, leaving 1 gallon in the 3-gallon jug. 5. Empty out the 5-gallon jug. 6. Transfer the 1 gallon to the 5-gallon jug. 7. Fill up the 3-gallon jug and transfer that to the 5-gallon jug. 8. The 5-gallon jug contains 4 gallons of water. These steps can be written as the following sequence of pairs. (0, 3)-->(3, 0)-->(3, 3)-->(5, 1)-->(0, 1)-->(1, 0)-->(1, 3)-->(4,0) Incidentally, the reason we can find a solution is because the two numbers 5 and 3 are relatively prime--that is, they have no common divisors. We can actually generate any volume of water from 1 to 5 (in fact, we did get measurements of 1, 2, 3, 4, and 5 along the way in our solutions). The water jug problem is an example of a Diophantine equation. The general problem is finding integer solutions for the polynomial equation ax + by = c. It can be proven that a solution (x, y) exists when the greatest common divisor of a and b is a factor of c. So you can get 4 gallons from a 3 and 5 gallon jug, but it would be impossible to get 3 gallons from a 2 and 4 gallon jug (since 2 and 4 have a greatest common divisor of 2, which is not a factor of 3). Puzzle 15: Dehydrated Food Imagine you have 100 pounds of food that is 99 percent water by weight. In the hot sun, the food dehydrates until it is 98 percent water. How much will the food weigh? Assume the only weight loss is from water evaporating away. Answer To Puzzle 15: Dehydrated Food The surprising answer is the food will be 50 pounds! Even though the water content drops by a mere 1 percentage point, the dehydrated food will lose 50 percent of its original weight. A direct approach is to work out the algebra. The food starts at 100 pounds, and 1 percent, or 1 pound is non-water weight. The dehydrated food is 98 percent water, so it is 2 percent non-water. The total weight of the dehydrated food is found by dividing the non-water weight by its percent weight. The answer is 50 pounds = (1 pound)/(2 percent). We can verify the water will make up 49 of the 50 pounds, which is 98 percent. The dramatic weight loss might be easier to understand from the non-water component frame of reference. The non-water component weighs the same absolute amount in both cases, but its percent weight doubles in the dehydrated food. Since the non-water percent weight doubles, that means the dehydrated food must weigh half as much. Now that you've solved this puzzle, you can easily solve the following related problems. 1. A gallon of milk weighs 8 pounds and is 90 percent water by weight. If the milk is converted into evaporated milk, which is 60 percent water, how much will the evaporated milk weigh? (answer: 2 pounds). 2. A soup broth weighing 10 pounds is 99 percent water by weight. I add salt until the broth becomes 98 percent water. How much will the soup broth weigh? (answer: about 10.1 pounds). The dehydrated food puzzle is surprising because problems 1 and 2 sound similar but have drastically different answers. The weight change is large in problem 1 but quite small in problem 2. Puzzle 16: Crossing Trains There is a 100 mile train track that connects cities A and B. A train leaves from A to B and is scheduled to arrive 1 hour later. At the same time, a train leaves from B to A and will make the trip in 2 hours. When the trains cross paths, how far will they be from city A? Answer To Puzzle 16: Crossing Trains There are a variety of methods to solve this problem. For convenience, label the train going from A to B as train A and the one from B to A as train B. Method 1: rates of speed Train B requires double the time to make the trip; therefore, train B moves half as fast as train A. This means that in the same amount of time, train A moves twice the distance as train B. By the time train B has traveled the distance x, train A has traveled 2x. When they meet, the sum of the distances they traveled will be the entire journey of 100 miles. Setting the sum of train distances equal to the distance between the towns gives the equation 2x + x = 100. This has a solution x = 33 1/3. We want the distance from city A, which is the distance that train A has traveled. Since 2x = 66 2/3, the answer is the trains meet 66 2/3 miles from city A. Method 2: working together The train problem is phrased in a somewhat competitive manner since the trains are moving in opposite directions. But we can re-frame the problem cooperatively as follows. Train A can complete 100 miles in 1 hour; train B can do it in 2 hours. Working together, how long will it take them to travel 100 miles? At time t, train A has traveled the percentage t / 1 and train B has traveled t / 2. We need these percentages to add up to 1 whole job; therefore the equation is t / 1 + t / 2 = 1. We can solve this equation for t = 2/3. In 2/3 of an hour, train A is 2/3 of the journey. Thus, the distance is (2/3)(100) = 66 2/3. In general, the time it takes for two people working together is equal to half of the harmonic mean of the rates of work. The harmonic mean of two numbers x and y is 2/(1/x + 1/y). This might look complicated, but this formula often arises when averaging rates. Train A moves at twice the speed of train B, so the rates can be thought of as 2 and 1. The time to meet is half of the harmonic mean, which is 1/(1/2 + 1/1) = 1/(3/2) = 2/3. In 2/3 of an hour, train A has completed 2/3 of 100 miles, so the meeting point is (2/3)(100) = 66 2/3 miles from city A. Method 3: algebra This is my least favorite way of solving the problem, but it is assured to work, so it's worth knowing! Train A moves at a speed of 100 miles per hour. Train B moves at a speed of 100/2 = 50 miles per hour. At a given time t, train A has moved a distance of 100t from city A. Since train B starts 100 miles from city A, its distance at time t will be 100 - 50t. When the two trains meet, the distances will be equal. 100t = 100 - 50t 150t = 100 t = 2/3 In 2/3 of an hour, train A and B are therefore 100(2/3) = 100 - 50(2/3) = 66 2/3 miles away from city A. Puzzle 17: Monks Crossing There is a sacred hill where monks pray. At each hour, a monk leaves the base for the top of the hill. Also at each hour, a monk leaves from the top of the hill for the return journey. Traversing the hill takes 4 hours in either direction and there is only one path. If a monk starts his journey from the bottom at 12 noon, how many monks will he pass along the way to the top? Answer To Puzzle 17: Monks Crossing For each of the 4 hours the monk travels, there will be another monk that leaves the top to return. It would be tempting to think the answer is 4. But this is incorrect. The reason is some monks are already on their way down. This factor contributes another 4 monks who get crossed. There is also one extra monk who gets crossed: the one who is leaving just as the monk reaches the top. Thus, the answer is 9. Here is a visual graph of the journey, where the right-hand numbers indicate the time at the top of the hill, and the lines going southwest are the paths of the monks returning to the base of the hill. The monks passed correspond to intersections in the graph. I adapted this puzzle adapted from "Meeting of Ships" in the book Famous Puzzles of Great Mathematicians by Miodrag S. Petkovic. Puzzle 18: Crossing Trucks At exactly sunrise, a delivery truck starts driving from city A to B. At the same time, another delivery truck is going in the opposite direction from city B to A. The two trucks pass each other at 12 noon. The truck driving to city B reaches its destination at 4pm. The truck going to city A takes much longer and reaches at 9pm. What time was sunrise? Assume the two trucks moved at a constant rate, and they traveled along exactly the same road between the two cities. Answer To Puzzle 18: Crossing Trucks The puzzle is a bit more difficult than the previous "crossing" problems because neither the starting time, nor the distance, nor the rate of either truck is given. Remarkably, there is enough information to solve this problem. There are a variety of methods to tackle the puzzle. Method 1: standard approach Let C denote the location of the crossing point. The trip can be thought of as two distances AC and CB. Write t for the number of hours between sunrise and 12 noon. The truck going from A to B was able to cover the distance CB in a manner of 4 hours. It took the other truck t hours to cover the same distance. Similarly, the truck going from A to B covered the distance AC in t hours while truck B did the same in 9 hours. Now we proceed in the following fashion. Each truck was said to be moving at a constant speed. So we will calculate the speed of each truck for each segment of the trip AC and CB. The truck going from A to B had a constant speed given by AC/t and CB/4. Since the two expressions are for the same speed, their ratio is equal to 1. Therefore, (AC/t)/(CB/4) = (4 AC)/(t CB) = 1. The truck going from B to A had a constant speed given by CB/t and AC/9. Again the ratio of these values must be equal to 1, which means (AC/9)/(CB/t) = (t AC)/(9 CB) = 1. Now we have two equations that are both equal to 1, and therefore they must be equal to each other. A wonderful amount of cancellation happens when the two equations are set equal to each other. (4 AC)/(t CB) = (t AC)/(9 CB) (4 AC)/(t CB) = (t AC)/(9 CB) 4/t = t/9 t2 = 36 t = 6 (because t was defined as positive, -6 doesn't make sense) Thus, the two trucks started 6 hours before noon, which means sunrise took place at 6 a.m. Method 2: geometrical solution The path of the two trucks can be drawn out in a rectangular diagram as follows. The horizontal axis indicates the time of day, the vertical axis indicates the distance of the truck from cities A and B, and the path of each truck is drawn as a directed line. The two lines meet exactly at 12 noon, and the other times of sunrise, 4pm, and 9pm are all drawn as given in the setup. To solve the problem, the relevant details can be re-drawn in this simplified diagram. There are a multitude of similar triangles in the figure. Note that triangle A is similar to A', and B is similar to B'. One can work out that this implies the following ratios are equal. (leg of A')/(leg of A) = (leg of B')/(leg of B) 4/t = t/9 This is exactly the same equation as using the previous method. The answer is the same that t = 6 and the sunrise happened at 6 a.m. Method 3: the long (and boring) algebra This is the method that came to my mind first. While it is the least elegant, it does get the job done. Write sa for the speed of the truck going from A to B, and sb for the truck B to A. Write d for the distance of the trip, and write t for the number of hours between sunrise and 12 noon. In a matter of t hours, the two trucks crossed. That means that they jointly traveled a distance of d (since C is the crossing point, AC + CB = AB). This implies the following equation. (I): sa t + sb t = d We also know the following. One truck completed the journey in t + 4 hours, and the other truck did it in t + 9 hours. We can calculate the speeds by dividing the distance of the total trip by the time it took each to complete the trip. This yields the following equations. sa = d/(t + 4) sb = d/(t + 9) Now we can substitute these back into equation (I). [d/(t + 4)]t + [d/(t + 9)]t = d The term d cancels out, and we can solve the equation diligently. t/(t + 4) + t/(t + 9) = 1 t(t + 9) + t(t + 4) = (t + 4)(t + 9) 2t2 + 13t = t2 + 13t + 36 t2 = 36 t = 6 (as we reject the negative solution) It took the trucks 6 hours from sunrise to meet at noon, so once again the answer is they started at 6 a.m. Credit: this is a puzzle I saw on Reddit Math, where credit was given to an AMS interview with Vladimir Arnol'd (Yes the name Arnol'd has an apostrophe and that is not a typo!). Puzzle 19: Slicing Vegetables One of the vegetables I eat regularly is an ivy gourd, also known as tondli/tindora/gentlemen's toes. The vegetable is a type of cucumber and looks like a pickle. The dish I prepare requires slicing the tondli into "coins" which are like mini pickle slices. Initially, I would chop up the tondli one by one. It would take me about 30 minutes to chop everything up. I later realized I could increase efficiency by changing my cutting technique. I soon learned to chop 2 tondli pieces at a time, so I could slice up 2 pieces in the same amount of time I used to be able to chop 1. I can now chop 3 tondli pieces at a time. The question is, how much time did I save when going from slicing 1 at a time to 2 at a time to 3 at a time? Assume the number of tondli pieces is divisible by 3 so there are no "leftover" pieces I have to chop individually or two at a time. Answer To Puzzle 19: Slicing Vegetables I was able to save a lot of time when going from 1 piece to 2, but then sadly I did not save much time when going from 2 pieces to 3--even though in both cases I was cutting one more piece at a time. The reason is there are diminishing returns with marginal increases to a rate of change. This is why driving faster and faster does not keep saving you much more time, or why cutting back on the frequency of coffee drinking will not improve your finances drastically. The same math applies to cutting vegetables more efficiently. Let's work out a concrete example. Let's say there are 30 tondli pieces and it takes me 30 minutes to cut them 1 at a time. Then my rate of chopping is 1 tondli piece per minute. If I increase that to 2 pieces per minute, then the time I would take is 15 minutes = (30 pieces)/(2 pieces/min). If I increased to 3 pieces per minute, then the time is 10 minutes = (30 pieces)/(3 pieces/min). In other words, I would save 15 minutes by increasing to 2 pieces per minute, but only 20 minutes by increasing to 3 pieces per minute. Although I save more time by cutting 3 at a time, I only end up saving 5 extra minutes over cutting 2 at a time. You can see there are diminishing returns to trying to increase my efficiency any more. If I increase to 4 pieces at a time, then I would only end up saving 22.5 minutes. At 5 pieces at a time, I would save 24 minutes. Even though I'm increasing the rate at which I slice the tondli by 1 extra piece each time, each time I end up saving less time in absolute minutes saved. On a practical note, it also becomes harder to chop more pieces at the same time. So I figure that I'm pretty good chopping 3 pieces at a time and if I want to increase the efficiency in my life I'm better off working on some other skill besides chopping. More Precise Proof I made the above calculation using 30 pieces. That was an assumption made without loss of generality. The reason is the number of pieces cancels out in the final calculation of time savings. For instance, suppose I start with N pieces of tondli. The time it takes me to chop 1 piece at a time is 30 minutes. Hence my rate of work is (N/ 30) pieces/min. When I increase my rate to 2 pieces at a time, I will be chopping at the rate of (2N/30) pieces/min. And for 3 pieces at a time, I will be chopping at a rate of (3N/30) pieces/min. If I chop k pieces at a time, then my rate is (kN/30) pieces/min. Then I need to calculate how much time it takes at each chopping rate. This is where the N cancels out. If I chop at 2 pieces per minute, then my time is 15 min = (N pieces)/(2N/30). If I chop at 3 pieces per minute, then my time is 10 min = (N pieces)/(3N/30) = 10 min. If I chop at k pieces per minute, then my time is 30/k min = (N pieces)/(kN/30). Therefore, the calculation of time is independent of the number of pieces. Puzzle 20: Moving Walkway This is a neat mathematical problem, but moving walkways are an interesting topic on their own. This problem takes place at the famous moving walkway of Chicago's O'Hare airport. If I walk while I'm on the moving walkway, it takes me 172 seconds to go from one end to the other. If I walk against the moving walkway--that is, I go the wrong way--it takes me five times as long to go from one end to the other, 860 seconds. There are two questions. First, if I stood still on the moving walkway, how long would it take me to go from one end to the other? Second, if I just walked--without using the moving walkway--how long would that take me to move the same distance? First, I've never actually done this experiment, but the numbers are relatively accurate to data on actual speeds, which is why the odd number of 172 seconds appears. Second, you'll notice there is a lot of missing information. You don't know the moving walkway's speed, the distance traveled, or how fast I walk. That's the beauty of this puzzle: you can still solve the problem! Answer To Puzzle 20: Moving Walkway The problem is fairly easy to solve with the assistance of a formula from algebra or physics class. The formula is that distance (d) equals the product of the rate of speed (r) and the time taken (t). That is, d = rt. We have to modify the formula slightly for this problem. The speed at which I move is not a single rate. It is the combination of my walking speed (rme) and the speed of the moving walkway (rwalkway). When I walk going in the same direction as the moving walkway, the rate will be the sum of my walking speed and the moving walkway's speed (rme + rwalkway). When I go against the track, the rate will be the difference of my walking speed and the moving walkway's speed (rme - rwalkway). We are given two points of information: going the correct way took 172 seconds while going against the moving walkway took five times as long, 860 seconds. Note that in either case the distance traveled is the same. Therefore, we can set up two equations, using the times given and letting distance and the rates of speed be unknown constants. (I) Walking in the correct direction d = (rme + rwalkway)(172 seconds) (II) Walking in the wrong direction d = (rme - rwalkway)(860 seconds) Now we can solve the problem. The time it takes if I stand still on the walkway is given by the following equation. d = (rwalkway)(time if standing still) We can re-arrange the equation to solve for the time by dividing both sides by rwalkway. This gets us the next equation. time if standing still = d/rwalkway. Analogously, we can find out an equation for the time it takes to walk, not using the moving walkway. time if not using the moving walkway = d/rme In short, we wish to solve for d/rwalkway and d/rme. We can actually do this from our equations (I) and (II). In summary, our problem is the following. Solve for d/rwalkway and d/rme, given that: (I) Walking in the correct direction d = (rme + rwalkway)(172 seconds) (II) Walking in the wrong direction d = (rme - rwalkway)(860 seconds) A little bit of algebra will get us to the answer. If we multiply the equation (I) by 5, and then subtract equation (II) from it, we eliminate the variable rme to solve for the other variable. The result is the following. 5(I) - (II) 4d = (rwalkway)(1720 seconds) d/rwalkway = 430 seconds = the time it takes if I stood still Similarly, we can we multiply the equation (I) by 5, and then add equation (II) to it to eliminate the variable rwalkway. 5(I) + (II) 6d = (rme)(1720 seconds) d/rme = 1720/6 ≈ 287 seconds = the time it takes if I didn't use the moving walkway The problem is solved, but let us take a moment to summarize the results, ranked from fastest to slowest options. 172 seconds = time if walking on moving walkway 287 seconds = time if walking, no moving walkway 430 seconds = time if standing still on moving walkway 860 seconds = time if walking against the moving walkway The astute reader will notice something interesting about the results. It is faster to walk without any assistance than to stand still on the moving walkway. And yet, this is what almost everyone does. Before taking the numbers too seriously, I should explain how I got the numbers for this problem. The O'Hare moving walkway is about 860 feet. I assumed it moved at 2 feet per second. The walking rate to construct this problem is 3 feet per second, which is just a tad over a very leisurely rate of 2 miles per hour (one mile every 30 minutes). So the numbers in this problem are fairly realistic. Moving walkways actually slow us down? I will end with a small tangent about scientific studies on the impact of moving walkways. As reported in The Telegraph, researchers found moving walkways at airports slow people down, as people often stand at busy times and their luggage can block movement. The time gained on the moving walkway is minimal, but the time wasted during congesting walkways is significant. That is, the moving walkway marginally increases speed when the airport is not busy, but it tends to slow everyone down otherwise (because of blockages and the fact that people like to stand on it). New airports should take this lesson to heart. We as a world would probably move a little faster if we just walked, and the extra exercise is probably a good thing as well. Puzzle 21: Wind Speed Imagine you have just attained 1,000 miles per hour in a car on a one mile track, blowing away the official land speed record. You'd probably be pumped and ready to celebrate. But it's not quite time to break out the champagne. You would actually be preparing the car and refueling. For you see, the official land speed record, as regulated by the Federation Internationale de l'Automobile, is based on the average speed for two runs in opposite directions. The rule seems immediately fair, because if a factor like wind speed was beneficial in one direction, it would be detrimental in the other direction. The situation raises an interesting mathematical question. If you were planning to break the land speed record, would you want the weather to have strong winds or no wind at all? In other words, how does wind affect the average speed of the round trip? Answer To Puzzle 21: Wind Speed Initially it might seem that wind won't matter as its effect would "cancel out" between the two runs. Careful calculation shows that wind actually does matter. Specifically, wind will lower the average speed of the round trip. Why is that the case? The reason is that speed is a rate, not an absolute quantity, and so equal gains and losses do not cancel out. Let's do a simple example. Let's say your car runs at 55 mph, with wind at 5 mph. If wind simply added to your speed, that would mean you would drive 1 mile at 60 mph, and then you drive the 1 mile back at 50 mph. Doing the math, the average speed is not 55 mph. The time on the first run is 1/60 hour, and on the second it is 1/50 hour. For the round trip, this means it took (1/60 + 1/50) hours to drive 2 miles. The average speed for the round trip is therefore 54.5 mph. We can generalize the equations to prove the round-trip with wind is slower. With no wind, the average speed of the round trip is (2 miles)/(time 1 + time 2), where each time is (time) = 1 mile / (speed). With wind, the two times will get changed. Let's say that wind adds a speed of S in the first run reduces it by the same amount in the other. Then (new time 1) = (1 mile)/(speed + S) and (new time 2) = (1 mile)/(speed - S). The average speed for the round trip is: (2 miles) / ((1 mile)/(speed + S) + (1 mile)/(speed - S)). After a bit of algebra, this can be simplified to the following equation. (no-wind average) * 1/(1 - (S)2/(speed)2) Now label X = (S)2/(speed)2. We don't know the value of X, but we know that it will be non-negative since it is a squared term. Hence, the answer simplifies to the following equation. average with wind = (no-wind average) * 1/(1 - X) Since X is positive, this means the term 1/(1 - X) will be a fraction, and hence the average with wind will be a smaller number than the average without wind. In short, the average speed of the round-trip is fastest with no wind. Puzzle 22: Michelson-Morley In the 1800s scientists understood that light acted as a wave. Because sound waves travel through air, and tidal waves travel in water, they believed light waves traveled through a medium as well, what they called the aether. The theory implied that light from the sun had to "swim" in the aether to reach the earth. And just as a strong wind affects the propagation of sound, the presence of an aether wind would affect the flow of light. But how could one detect the aether and the speed of the aether wind? In 1887, two scientists developed an apparatus to detect the aether wind. One of the scientists used a math puzzle to explain the principle behind the experiment. So consider the following problem. Two equally strong swimmers race at a river. They start and end at the same point, but they take different paths. Swimmer 1 goes to the closest point across the river, 100 feet in width, and returns. Swimmer 2 goes directly upstream (against the current) for 100 feet and then returns by swimming downstream. Who wins the race? Assume the river flows at 3 feet per second, and the swimmers have a speed of 5 feet per second. Note that both swimmers are influenced by the flow of the river. Swimmer 1 has to fight the flow of the river to make a straight line path across and back. Swimmer 2 is actively swimming against the river flow in one direction and then swimming with the river flow on the return trip. Work out the puzzle. The solution will explain the connection of the problem to the aether wind. Answer To Puzzle 22: Michelson-Morley The easier case is the swimmer 2, who swims upstream (against the current) in one direction and then downstream (with the current) in the other. The net speed is equal to the combined effect of the swimmer's speed and the river's flow. Going downstream the swimmer's speed is the sum of his speed plus the river's flow (8 = 5 + 3), and going upstream his speed is his rate minus the river's flow (2 = 5 - 3). The time downstream is 100/8 = 12.5 seconds and the time upstream is 100/2 = 50 seconds. The total time is 62.5 seconds. Swimmer 1 is trickier because he is swimming across the flow of the river. The path he swims will be the net result of his velocity and the river flow's velocity. We can think about this in terms of vector math: the swimmer's vector plus the river's vector must be equal a straight line vector. In the diagram, the swimmer's vector is the hypotenuse and the river's flow is the short leg. The numbers have been chosen with a purpose: the swimmer's vector has a speed of 5 feet per second, the river's flow is 3 feet per second, and the vectors form a right triangle. So we must have a 3-4-5 right triangle! The swimmer's net speed is 4 feet per second. Note the size of the vectors will be the same for the trip across the river and the return trip, so the swimmer's speed is 4 feet per second on each trip. Swimmer 1 takes 100/4 = 25 seconds for each of the two trips. In total, the cross-stream swimmer takes 50 seconds in all, which is shorter than the 62.5 seconds of the upstream swimmer. The answer is swimmer 1 wins. And this turns out always to be true: swimmer 1, the cross-stream swimmer, always wins (so long as their swimming speed is faster than the flow of the river). The Michelson-Morley experiment In 1887 the scientists Albert A. Michelson and Edward W. Morley developed an apparatus to detect the aether wind. The device was called an interferometer, and it worked on the same principle as the swimming puzzle. (Michelson devised the puzzle to explain it to his children). The interferometer used a set of mirrors to split up a beam of light into two beams. The two beams then "raced" just like the two swimmers. One beam of light (call it a red beam) was like the cross-stream swimmer that was sent to the closest point across a certain distance. The other beam (call it a blue beam) was like the upstream swimmer and it was sent the same distance against the aether wind. If the aether wind existed, then the light beam that "swam" cross-stream would win every time. In other words, the red beam would arrive faster than the blue beam. This could be experimentally detected by the interaction of the light waves. The experimental results showed the two beams arrived at about the same time. The experiment provided strong evidence that the aether wind did not exist and is celebrated as one of the most famous experiments in physics. I read about this puzzle and its relationship to the experiment on the following website: http://galileo.phys.virginia.edu/classes/109N/lectures/michelson.html. The Michelson-Morley Experiment, Michael Fowler U. Va. Physics. 9/15/08. Puzzle 23: Smartphone Battery John's phone is a battery hog. It can last only 4 hours before the battery dies. John has an identical spare battery. But there are days he needs even more time from his phone. So in desperation, John devises a battery swapping and charging scheme. When the first battery dies, he immediately charges it while swapping in the spare battery. Then, when the spare battery dies, he immediately charges it while swapping in the other battery--which by that time has charged to 50%. He repeats this over and over until both batteries are dead. How many hours can John get out of his two batteries with one phone charger? Assume battery swaps are instantaneous, batteries discharge twice as fast as they charge, and both charging and discharging happen at a linear rate. Answer To Puzzle 23: Smartphone Battery At first you might be tempted to solve for the time each battery takes to die, and then sum up the infinite series of battery life times. I'll explain how to solve using that method. But there's a clever trick to solve it in a single linear equation! The trick takes some setup, but then the algebra is trivial. The key is to remember the conservation of energy: the total amount of battery life discharged (energy used) is equal to the total amount of battery life charged (energy available, accounting for the initial charge on both batteries). Energy used = Energy available The energy used is the rate the batteries discharge times the discharge rate. The energy available is the battery charge time times the charging rate, plus the initial energy that both batteries had since they were charged at the start. (discharge rate)(discharge time) = initial energy + (charge rate)(charge time) Let's say the batteries have an energy of 1 when they are fully charged. Since the batteries discharge in 4 hours, they discharge at a rate of 0.25 energy units per hour. They charge at half that speed, or 0.125 energy units per hour. Both batteries are charged to start, so the initial energy is 2. Let's say the total time until both batteries die is t. It takes 4 hours until the first battery dies, so the total time charging is t - 4. So we have the following equation. 0.25t = 2 + (0.125)(t - 4) We can solve for t which is the total time until both batteries die. 0.25t = 2 + 0.125t - 0.5 0.125t = 1.5 t = 12 So John can get 12 hours from his two batteries, which is probably just enough to last for a day. We can generalize this problem. If the charge rate is 50% of the discharge rate, John can always get 3 times whatever the battery life is. In other words, it's like John has a third spare battery! Let's prove this. We again suppose a battery starts with 1 energy unit. If the battery life is B, then the discharge rate is 1/B energy units per hour, and the charge rate is half of that, or 0.5/B energy units per hour. The first charge starts after B hours, and the initial energy is still 2 since both batteries start charged. So we solve the same problem for B. (1/B)t = 2 + (0.5/B)(t - B) t/B = 2 + 0.5t/B - 0.5 0.5t/B = 1.5 t = 3B Thus, the total time is 3 times the battery life. Further, we can generalize if the charging rate is a fraction f < 1 of the discharge rate. (If the charge time is as fast or faster than the discharge rate, then the battery charges until full each time, so the two batteries can last indefinitely). The rate of discharge is f/B energy units per hour. (1/B)t = 2 + (f/B)(t - B) t/B = 2 + ft/B - f (1 - f)t/B = 2 - f t = B(2 - f)/(1 - f) So, for example, if the battery charges only 1/3 as fast as it discharges, then the total time is 2.5 the battery life. Infinite Series It is not too difficult to solve the problem explicitly using infinite series. The first battery discharges in B hours. Let's call this time period t1. The spare battery then discharges in B hours. The next time period is t2. In the third period, the first battery has had B hours to charge, but only charges up a fraction f of the battery life. So the first battery will discharge in fB hours. This time period is t3. In the fourth period, the spare battery has had fB hours to charge (the time the first battery took to discharge in the last period), but only charges up a fraction f of the time. So the spare battery will discharge in f2B hours. This time period is t4. Now we can see the pattern that the next period lasts f times as long as the previous one. That is, in each time period tk, with k > 1, the battery discharges in fk-2B hours. The total time until both batteries discharge completely is the sum of every time period. T = t1 + t2 + t3 + ... T = B + B + fB + f2B + ... T = B + B(1 + f + f2 + ...) The sum of the infinite series in brackets is 1/(1 - f). Therefore, the total time is the following. T = B + B/(1 - f) T = B(2 - f)/(1 - f) Note this is the same result as when we used the trick! This problem is a variant of a puzzle from Cornell Engineering Magazine, brain teaser by Andy Ruina. Puzzle 24: Vietnam Problem This problem was posed to 3rd graders (8 year olds) in Vietnam. Many adults had trouble solving it and this problem was widely shared. The problem is to place the numbers 1 to 9, using each number once, to make a valid equation. The expression is read from left to right wrapping around the corners like a snake. Be sure to follow the order of operations: multiplication and division should be evaluated before addition and subtraction. There are in fact many answers to this problem. See if you can figure out at least one before reading the solution. Answer To Puzzle 24: Vietnam Problem Here is one possible answer: fill the boxes, from the left, with the numbers 1, 2, 6, 4, 7, 8, 3, 5, 9. In all there are 136 possible answers found by computer. Before I present those, I will explain how I reasoned to find a single answer. How many arrangements are there? How many ways can you place the numbers 1 to 9 in the empty boxes? There are 9 choices for the first box. Then there are 8 choices for the second box (as one number is already used up). Then there are 7 choices for the third box (as two numbers have been used), and so on, with each subsequent box having one fewer possibility. In all there are 9x8x7x6x5x4x3x2x1 = 9! = 362,880 possible ways to arrange the numbers. There are too many possibilities to check. So you'll have to think about the problem logically. Write the expression in a line A good first step is to re-write the expression in a single line. This will make it easier to understand the equation. I will use a slash mark (/) for the division symbol. _ + 13 x _ / _ + _ + 12 x _ - _ - 11 + _ x _ / _ - 10 = 66 The next step is to consider the order of operations. Multiplication and division take precedence over addition and subtraction. So we can add parentheses around those steps so we know to evaluate them first. _ + (13 x _ / _) + _ + (12 x _) - _ - 11 + (_ x _ / _) - 10 = 66 Now what do we do? Guess and check! I suspected the solution might be easy to find since it was given to 3rd graders. So I wondered: what would happen if I wrote the numbers 1 to 9 in ascending order? 1 + (13 x 2 / 3) + 4 + (12 x 5) - 6 - 11 + (7 x 8 / 9) - 10 = 52.889... It was actually pretty close! What if I tried the numbers in descending order, from 9 to 1? 9 + (13 x 8 / 7) + 6 + (12 x 5) - 4 - 11 + (3 x 2 / 1) - 10 = 70.857... Again this was pretty close! So I thought maybe I could adjust the numbers and get closer to 66. Dividing by 7 was going to lead to a fraction. So I thought of swapping the 4 and 7. That didn't immediately work, so I thought of cycling the 8, 7, and 4 so I was dividing 4 by 8. Since I would end up with 1/2, I thought of also shifting the 3, 2, and 1 around so I would have 3 divided by 2. Here's what I got. 9 + (13 x 4 / 8) + 6 + (12 x 5) - 7 - 11 + (1 x 3 / 2) - 10 = 55 This was a whole number, which was good. And it was only 11 less than the desired result of 66. Then I saw an easy way to solve this: I could swap the 6 and the 5. This would increase the expression by -1 + 12 = 11 and get to 66. 9 + (13 x 4 / 8) + 5 + (12 x 6) - 7 - 11 + (1 x 3 / 2) - 10 = 66 So that is one answer. Multitude of solutions Then I thought about the expression. 9 + (13 x 4 / 8) + 5 + (12 x 6) - 7 - 11 + (1 x 3 / 2) - 10 = 66 The numbers 9 and 5 can obviously be swapped since addition is commutative, so that's another solution. 5 + (13 x 4 / 8) + 9 + (12 x 6) - 7 - 11 + (1 x 3 / 2) - 10 = 66 And since multiplication is commutative, the numbers 1 and 3 can be swapped. 5 + (13 x 4 / 8) + 9 + (12 x 6) - 7 - 11 + (3 x 1 / 2) - 10 = 66 We can get a fourth solution by swapping the 5 and the 9 again. 9 + (13 x 4 / 8) + 5 + (12 x 6) - 7 - 11 + (3 x 1 / 2) - 10 = 66 Besides those related solutions, there are other combinations of numbers that solve the puzzle too. Here are a few examples. 5 + (13 x 4 / 1) + 9 + (12 x 2) - 7 - 11 + (3 x 8 / 6) - 10 = 66 5 + (13 x 9 / 3) + 6 + (12 x 2) - 1 - 11 + (7 x 8 / 4) - 10 = 66 6 + (13 x 3 / 1) + 9 + (12 x 2) - 5 - 11 + (7 x 8 / 4) - 10 = 66 Each of these equations also has 3 related solutions when considering swapping numbers, as explained above. How many solutions are there in all? We know that any equation results in a set of 4 answers. Therefore, we know the total number of answers should be a multiple of 4. If someone told you there were 101 solutions, that wouldn't make sense because 101 is not a multiple of 4. Brute Force calculation I used a spreadsheet and tested out every single possible expression and found there are 136 solutions. This would be 34 distinct answers, each with 3 related equations from swapping numbers. Here is my full list of answers, read from left to right. For example, the first set of numbers 1, 2, 6, 4, 7, 8, 3, 5, 9 corresponds to the expression 1+13x2/6+4+12x7-8-11+3x5/9-10 = 66. So here are all 136 solutions to this problem. 1, 2, 6, 4, 7, 8, 3, 5, 9 1, 2, 6, 4, 7, 8, 5, 3, 9 1, 3, 2, 9, 5, 6, 4, 7, 8 1, 3, 2, 9, 5, 6, 7, 4, 8 1, 3, 2, 4, 5, 8, 7, 9, 6 1, 3, 2, 4, 5, 8, 9, 7, 6 1, 3, 4, 7, 6, 5, 9, 2, 8 1, 3, 4, 7, 6, 5, 2, 9, 8 1, 3, 6, 2, 7, 9, 4, 5, 8 1, 3, 6, 2, 7, 9, 5, 4, 8 1, 3, 9, 4, 7, 8, 5, 2, 6 1, 3, 9, 4, 7, 8, 2, 5, 6 1, 4, 8, 2, 7, 9, 5, 3, 6 1, 4, 8, 2, 7, 9, 3, 5, 6 1, 5, 2, 8, 4, 7, 9, 3, 6 1, 5, 2, 8, 4, 7, 3, 9, 6 1, 5, 2, 3, 4, 8, 7, 9, 6 1, 5, 2, 3, 4, 8, 9, 7, 6 1, 5, 3, 9, 4, 2, 7, 8, 6 1, 5, 3, 9, 4, 2, 8, 7, 6 1, 8, 3, 7, 4, 5, 2, 6, 9 1, 8, 3, 7, 4, 5, 6, 2, 9 1, 9, 6, 4, 5, 8, 7, 3, 2 1, 9, 6, 4, 5, 8, 3, 7, 2 1, 9, 6, 7, 5, 2, 4, 3, 8 1, 9, 6, 7, 5, 2, 3, 4, 8 2, 1, 4, 3, 7, 9, 5, 6, 8 2, 1, 4, 3, 7, 9, 6, 5, 8 2, 3, 6, 1, 7, 9, 4, 5, 8 2, 3, 6, 1, 7, 9, 5, 4, 8 2, 4, 8, 1, 7, 9, 3, 5, 6 2, 4, 8, 1, 7, 9, 5, 3, 6 2, 6, 9, 8, 5, 1, 4, 7, 3 2, 6, 9, 8, 5, 1, 7, 4, 3 2, 8, 6, 9, 4, 1, 5, 7, 3 2, 8, 6, 9, 4, 1, 7, 5, 3 2, 9, 6, 3, 5, 1, 7, 4, 8 2, 9, 6, 3, 5, 1, 4, 7, 8 3, 1, 4, 2, 7, 9, 5, 6, 8 3, 1, 4, 2, 7, 9, 6, 5, 8 3, 2, 8, 6, 5, 1, 9, 7, 4 3, 2, 8, 6, 5, 1, 7, 9, 4 3, 2, 1, 5, 4, 7, 8, 9, 6 3, 2, 1, 5, 4, 7, 9, 8, 6 3, 2, 4, 8, 5, 1, 7, 9, 6 3, 2, 4, 8, 5, 1, 9, 7, 6 3, 5, 2, 1, 4, 8, 7, 9, 6 3, 5, 2, 1, 4, 8, 9, 7, 6 3, 6, 4, 9, 5, 8, 7, 1, 2 3, 6, 4, 9, 5, 8, 1, 7, 2 3, 9, 2, 8, 1, 5, 7, 6, 4 3, 9, 2, 8, 1, 5, 6, 7, 4 3, 9, 6, 2, 5, 1, 4, 7, 8 3, 9, 6, 2, 5, 1, 7, 4, 8 4, 2, 6, 1, 7, 8, 5, 3, 9 4, 2, 6, 1, 7, 8, 3, 5, 9 4, 3, 9, 1, 7, 8, 2, 5, 6 4, 3, 9, 1, 7, 8, 5, 2, 6 4, 3, 2, 1, 5, 8, 7, 9, 6 4, 3, 2, 1, 5, 8, 9, 7, 6 4, 9, 6, 1, 5, 8, 3, 7, 2 4, 9, 6, 1, 5, 8, 7, 3, 2 5, 1, 2, 9, 6, 7, 3, 4, 8 5, 1, 2, 9, 6, 7, 4, 3, 8 5, 2, 1, 3, 4, 7, 8, 9, 6 5, 2, 1, 3, 4, 7, 9, 8, 6 5, 3, 1, 7, 2, 6, 8, 9, 4 5, 3, 1, 7, 2, 6, 9, 8, 4 5, 4, 8, 9, 6, 7, 1, 3, 2 5, 4, 8, 9, 6, 7, 3, 1, 2 5, 4, 1, 9, 2, 7, 3, 8, 6 5, 4, 1, 9, 2, 7, 8, 3, 6 5, 7, 2, 8, 3, 9, 6, 1, 4 5, 7, 2, 8, 3, 9, 1, 6, 4 5, 9, 3, 6, 2, 1, 7, 8, 4 5, 9, 3, 6, 2, 1, 8, 7, 4 6, 2, 8, 3, 5, 1, 9, 7, 4 6, 2, 8, 3, 5, 1, 7, 9, 4 6, 3, 1, 9, 2, 5, 7, 8, 4 6, 3, 1, 9, 2, 5, 8, 7, 4 6, 9, 3, 5, 2, 1, 7, 8, 4 6, 9, 3, 5, 2, 1, 8, 7, 4 7, 1, 4, 9, 6, 5, 3, 2, 8 7, 1, 4, 9, 6, 5, 2, 3, 8 7, 2, 8, 9, 6, 5, 3, 1, 4 7, 2, 8, 9, 6, 5, 1, 3, 4 7, 3, 2, 8, 5, 9, 6, 1, 4 7, 3, 2, 8, 5, 9, 1, 6, 4 7, 3, 4, 1, 6, 5, 9, 2, 8 7, 3, 4, 1, 6, 5, 2, 9, 8 7, 3, 1, 5, 2, 6, 9, 8, 4 7, 3, 1, 5, 2, 6, 8, 9, 4 7, 5, 2, 8, 4, 9, 1, 3, 6 7, 5, 2, 8, 4, 9, 3, 1, 6 7, 6, 4, 8, 5, 9, 3, 1, 2 7, 6, 4, 8, 5, 9, 1, 3, 2 7, 8, 3, 1, 4, 5, 2, 6, 9 7, 8, 3, 1, 4, 5, 6, 2, 9 7, 9, 6, 1, 5, 2, 3, 4, 8 7, 9, 6, 1, 5, 2, 4, 3, 8 8, 2, 4, 3, 5, 1, 7, 9, 6 8, 2, 4, 3, 5, 1, 9, 7, 6 8, 3, 2, 7, 5, 9, 1, 6, 4 8, 3, 2, 7, 5, 9, 6, 1, 4 8, 5, 2, 1, 4, 7, 9, 3, 6 8, 5, 2, 1, 4, 7, 3, 9, 6 8, 5, 2, 7, 4, 9, 1, 3, 6 8, 5, 2, 7, 4, 9, 3, 1, 6 8, 6, 4, 7, 5, 9, 1, 3, 2 8, 6, 4, 7, 5, 9, 3, 1, 2 8, 6, 9, 2, 5, 1, 4, 7, 3 8, 6, 9, 2, 5, 1, 7, 4, 3 8, 7, 2, 5, 3, 9, 6, 1, 4 8, 7, 2, 5, 3, 9, 1, 6, 4 8, 9, 2, 3, 1, 5, 6, 7, 4 8, 9, 2, 3, 1, 5, 7, 6, 4 9, 1, 2, 5, 6, 7, 3, 4, 8 9, 1, 2, 5, 6, 7, 4, 3, 8 9, 1, 4, 7, 6, 5, 2, 3, 8 9, 1, 4, 7, 6, 5, 3, 2, 8 9, 2, 8, 7, 6, 5, 3, 1, 4 9, 2, 8, 7, 6, 5, 1, 3, 4 9, 3, 1, 6, 2, 5, 7, 8, 4 9, 3, 1, 6, 2, 5, 8, 7, 4 9, 3, 2, 1, 5, 6, 4, 7, 8 9, 3, 2, 1, 5, 6, 7, 4, 8 9, 4, 8, 5, 6, 7, 1, 3, 2 9, 4, 8, 5, 6, 7, 3, 1, 2 9, 4, 1, 5, 2, 7, 8, 3, 6 9, 4, 1, 5, 2, 7, 3, 8, 6 9, 5, 3, 1, 4, 2, 7, 8, 6 9, 5, 3, 1, 4, 2, 8, 7, 6 9, 6, 4, 3, 5, 8, 1, 7, 2 9, 6, 4, 3, 5, 8, 7, 1, 2 9, 8, 6, 2, 4, 1, 5, 7, 3 9, 8, 6, 2, 4, 1, 7, 5, 3 Source: the problem appeared in VN Express (Vietnamese) and I read about it from Alex Bellos via The Guardian. Part II: Medium Puzzles Puzzle 1: Paths Home Bob walks home from work. His home is 8 city blocks east and 8 city blocks north of his office. The walkways are exactly a rectangular grid. One way Bob could walk home is by going 8 blocks east and then 8 blocks north. He could also walk 5 blocks east, 5 blocks north, then 3 blocks east and 3 blocks north, as depicted below. Obviously there are many variations that Bob could take. The question is, how many paths home are there, if Bob only walks east and north, one block at a time, and walks 16 blocks in total? Answer To Puzzle 1: Paths Home The trick is to approach this problem combinatorially. Bob's path can be represented as a list of 16 steps, each step being "east" or "north." For instance, walking 8 blocks east and then 8 blocks north is (east, east, east, east, east, east, east, east, north, north, north, north, north, north, north, north). The question can be re-phrased in the following manner: how many ways are there to write a list of 16 items, where 8 of the items are east and the other 8 are north? The problem translates into the number of ways to arrange 8 indistinguishable objects out of 16 (once you select 8 spots as "east" the remaining 8 spots will be "north"). The answer is 16 choose 8 = 12,870. Puzzle 2: Two Sequences Test your knowledge of patterns on the following two sequences. Problem 1: What is the product of the following set of numbers? (1 - 1/4)(1 - 1/9)(1 - 1/16)(1 - 1/25)(1 - 1/36)(1 - 1/49) Can you generalize the sequence and the answer? Problem 2: A sequence of numbers, following a logical rule, starts out as follows. 1, 11, 21, 1211, 111221, ... Can you figure out the next number? Answer To Puzzle 2: Two Sequences Here is the first sequence. (1 - 1/4)(1 - 1/9)(1 - 1/16)(1 - 1/25)(1 - 1/36)(1 - 1/49) Notice each term is 1 minus the reciprocal of a square. That is, each term is (1 - 1/n2) = (1 - 1/n)(1 + 1/n). There is an interesting pattern if we write out each term in the expanded form. It turns out the middle terms are reciprocals of each other and will cancel out. (1 - 1/4)(1 - 1/9)(1 - 1/16)(1 - 1/25)(1 - 1/36)(1 - 1/49) = (1 - 1/2)(1 + 1/2)(1 - 1/3)(1 + 1/3)...(1 - 1/7)(1 + 1/7) = (1/2) (3/2)(3/2) (4/3)(3/4) ... (7/6)(6/7) (8/7) = (1/2) (1) (1) (1) ... (8/7) = (1/2)(8/7) = 8/14 = 4/7 We can generalize the sequence. When the product of consecutive integer terms (1 - 1/n2) ends on the square of k, we will have the following result. (1 - 1/4)(1 - 1/9)(1 - 1/16)...(1 - 1/k2) =(1 - 1/2)(1 + 1/2)...(1 - 1/k)(1 + 1/k) = (1/2) (1) (1) (1) ... (1 + 1/k) = (1/2)(1 + 1/k) = (k + 1)/(2k) So the product is (k + 1)/(2k). The second problem is a different beast. There is a logical rule, but it is not as easy to see the pattern. Here is the sequence. 1, 11, 21, 1211, 111221, ... These numbers are the start of the look and say sequence. The sequence starts out with 1. We read this number as "there is 1 term of 1." Retaining only the numbers in this sentence, in order, gives 11, which is then the next term of the sequence. Now we will read out 11 to get the next item in the sequence. We read this number as "there are 2 terms of 1." We again retain only the numbers in this sentence to get the next term, 21. You can see the pattern. Reading 21 out loud, we would say, "There is 1 term of 2 and 1 term of 1." Retaining only the numbers in this sentence gives the next term 1211. To solve the puzzle, we need to read 111221 as, "There are 3 terms of 1, 2 terms of 2, and 1 term of 1," which gives 312211 as the next item in the sequence. Puzzle 3: 100 Lamps One hundred lamps are placed in a row on a long table. The lamps are labeled sequentially, with the first lamp numbered "1" and the last lamp "100." The 1st person to enter the room hits the switch for each lamp, turning them all on. Then a 2nd person enters the room and hits the switch for every second lamp, which turns off the lamps numbered 2, 4, 6, etc. A 3rd person hits the switch for every third lamp, numbered 3, 6, 9, etc. Note that some lamps get turned off--like lamp 3--while others get turned on--like lamp 6. The pattern continues for the 4th, 5th, ..., and 100th person entering the room, with the nth person hitting the switch for the lamps numbered n, 2n, etc. After all 100 people are done, some lights will be on and some will be off. Will lamp 60 be on or off? Can you figure out exactly which lamps will be on and which will be off? Answer To Puzzle 3: 100 Lamps The solution could be found by simulating the experiment and seeing which lamps are on and off. But there is a more elegant method. A simple example will illustrate. Consider lamp number 6. Which people will alter the state of this lamp? Clearly the 1st person will turn the lamp on, and then the 2nd person will turn it off. The 3rd person will then turn the lamp back on. Finally, the 6th person will turn the lamp off. No other person will alter the state of the lamp because every subsequent person starts at a lamp number higher than 6. Therefore, lamp number 6 ends up in the off position. Which people altered the state of lamp 6? These were the 1st, 2nd, 3rd, and 6th persons. The connection should be made that these numbers are the factors of the number 6. Notice that the factors come in pairs because 6 = 1x6 = 2x3. The key observation is that each multiplicative pair corresponds to the lamp switch being hit two times in an (on position, off position) pairing. Therefore, if a lamp number has an even number of factors, then it will end up in the off position. And if it has an odd number of factors, it will end up in the on position. Returning to the question posed, the number 60 has 12 factors: the numbers 1, 2, 3, 4, 5, 6, 10, 12, 15, 30, and 60. This means the lamp gets turned on 6 times and turned off 6 times, so ultimately the lamp will be in the off position. Will any lamp be on after all 100 people? The answer is yes. Certain lamp numbers only have an odd number of factors. For instance, consider the number 4 which has factors 1, 2, and 4. This is an odd number because the factor 2 pairs with itself: 4 = 1x4 = 2x2. The lamp number 4 ends up in the on position--it gets turned on by person 1, then off by person 2, and then on again by person 4. Which other numbers have an odd number of factors? It is precisely the numbers where a factor pairs with itself, namely, the perfect squares. There are 10 perfect squares between 1 and 100 that will be in the on position at the end: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. All of the other lamps are composite numbers and will be off at the end. Puzzle 4: Trailing Zeroes The number 1,000 starts with the digit 1 and then finishes with 3 "trailing zeroes." The number 10,000 has 4 trailing zeroes. How many trailing zeroes are in the number 1000! = (1000)(999)...(1)? Answer To Puzzle 4: Trailing Zeroes What's the fastest way to solve this problem? You can get an answer from the website WolframAlpha. If you type the phrase "trailing zeroes in 1000!", you will get the answer of 249 immediately. That is the correct computation, but the question is how did people do it before WolframAlpha? Take a step back and consider why a number might have a trailing zero. The number 10 has 1 trailing zero because it is divisible by 10. The number 100 has 2 because it is divisible by 100 = 102, and the number 1,000,000 has 6 trailing zeroes because it is divisible by 106. A number like 1,010 has 1 trailing zero because it is divisible by 10 but not by 100 = 102. The question of "how many trailing zeroes are there?" is really asking "what's the highest power of 10 that the number is divisible by?" The number 1000! by its definition is clearly divisible by 10, 100, and 1,000, so to start, we know there are at least 3 trailing zeroes. In fact, since 10, 100 and 1000 are factors of 1000!, we know the number is also divisible by the product 10(100)(1000) = 106. Therefore, 1000! will have at least 6 trailing zeroes. What's the highest power of 10 that 1000! is divisible by? Rather than continuing to guess and check, we can take a systematic approach. We wish to find the largest number n such that 1000! is divisible by 10n. The idea, therefore, is to count the number of factors of 10 in 1000! For instance, the number 10 contributes one factor and the number 1,000 contributes 3 factors since 1,000 = 103. Now comes the first trick. The number 10 is factored as 10 = 2 x 5. To find the largest number n such that 1000! is divisible by 10n, we can equivalently find the largest n such that 1000! is divisible by (2 x 5)n = (2)n(5)n. In other words, we need to count how many factors of 2 and 5 are in the number 1000! The second trick is to realize there will be an abundance of factors of 2 in comparison to 5. This is because every other number contains a factor of 2 whereas only every fifth number contains a factor of 5. So the problem reduces to counting the number of factors of 5 in the number 1000! Now every 5th number contributes at least one factor of 5. That is, the numbers 5, 10, 15, ..., 1000 all contribute one factor of 5. There are 1000/5 = 200 numbers that contribute a factor of 5. Additionally, every 25th number contributes a second factor of 5, since 25 = 52. Therefore, the numbers 25, 50, ..., 1000 all contribute a second factor of 5. There are 1000/25 = 40 such numbers. The problem is solved by continuing this counting. Every 53 = 125th number contributes a third factor of 5, and there are 1000/125 = 8 such numbers. Finally the number 625 = 54 contributes a fourth factor of 5. (The next power of 5 is 3,125 = 55 which is larger than 1000 and so it is not a term in 1000!) Tabulating these results, there are 200 + 40 + 8 + 1 = 249 factors of 5 in the number 1000! Each of these factors gets paired with a factor of 2, meaning there are 249 factors of 10 in the number 1000! Therefore, 1000! is divisible by 10249 and it will have 249 trailing zeroes. The same procedure works for finding the trailing zeroes in n! You can count the number of trailing zeroes by counting the factors of 5. This can be found from the expression n/5 + n/25 + n/125 +..., which terminates at the largest power of 5 that is smaller than n. Interesting fact: Peter Thiel, one of the co-founders of PayPal, told the New Yorker that he and co-founder Max Levchin would try to stump each other with math puzzles, citing this problem as an example. Puzzle 5: Number Of Digits How many digits are in the number 125100? Answer To Puzzle 5: Number Of Digits Once again, this problem can be solved computationally. You can literally type in the phrase "digits in 125^100" on the website WolframAlpha to find the answer of 210 digits. But that is no fun. The real puzzle is to solve the problem without using a calculator. Function to find digits in a number We will proceed with some examples to see if we can find a pattern. What we want is to find a function so that for any whole number x, we will have f(x) = the number of digits in x. If x is between 1 and 9, then the number only has 1 digit. Once we get to 10, the number has 2 digits. In fact, any number between 10 and 99 has 2 digits. It is at 100 that we move to 3 digits, and all the numbers from 100 to 999 have 3 digits. We're beginning to see a pattern. The critical point for a number having an extra digit is related to the powers of 10. A number less than 101 has 1 digit A number greater than 101 but less than 102 has 2 digits A number greater than 102 but less than 103 has 3 digits ... A number greater than 10n but less than 10n+1 has n+1 digits We've found a useful pattern. The question is now this: if we have a given number x, how can we determine which powers of 10 that is in between? As luck would have it, there is a magical function that you already know that can do this: the logarithm! The logarithm (base 10) of a number x gives you the value y where 10y = x. For instance, the logarithm of 150 is approximately 2.176, because 102.176 is equal to 150. So we can conclude that 150 is between the powers 102 and 103, meaning that 150 has 3 digits. Another way of putting this: the answer 2.176 is between the numbers 2 and 3, and we need to round up to find the number of digits. The mathematical function for "rounding up" is typically called the "ceiling" function. So that's it: the function f(x) = ceiling(log(x)) will provide us the number of digits in a whole, positive number x. Actually there's a problem with this function. For the number 10, we get ceiling(log(10)) = 1, and obviously 10 has 2 digits. So we can slightly modify the function. Instead of rounding up, we will round down and then add 1. The correct function is f(x) = 1 + floor(log(x)) where "floor" means to round down. Now we will apply this method to our original problem. We need to find log(125100). Since 125 = 53, we can re-write this as log(5300) = 300 log(5). If you know that log(5) is about 0.699, then you can estimate this is between 209 and 210. Therefore, f(125100) = 1 + floor(log(125100)) = 1 + 209 = 210. And so there are 210 digits in digits in 125100. Personally I'm satisfied with this answer. However, some people feel it is cheating to use a log-table or have any knowledge of the values of logarithms. So there is another way of solving this problem that is also quite clever. Alternate method I found this solution in a collection of difficult math problems. The idea is to think about the largest power of 10 less than 125100, and that will involve a bunch of creative ways to re-write the expression. The first step is to re-write the expression in terms of powers of 10 and 2, because 5 = 10/2. 125100 = 5300 = 10300/2300 It is commonly known that 210 = 1024 (this is something computer scientists know, as everything is done in base 2. A kilo-byte is equal to 1024 bytes, not 1000 bytes). We can also write 1024 = 1000 x 1.024 = 103 x 1.024 (aka "scientific notation"). Therefore, we have 2300 = (103 x 1.024)30 = 1090 x 1.02430. Putting this all together, we find the following: 125100 = 10300/2300 = 10300/(1090 x 1.02430) We cancel the powers of 10 to get: 125100 = 10210/1.02430 Now we need to figure out how big 1.02430 is. This will require a bit of estimation from the binomial theorem. We have (1 +x)30 = 1 + 30x + 435x2 + ... The key is that x = 0.024 is a small number, so higher and higher powers of it will tend to zero. In this example, the term 30x = 0.72, and 435x2 is about 0.25, and the next term will be something like 0.05. It is evident the terms are getting smaller quickly so we can ignore higher powers. Therefore, we can conclude that 1.02430 will be larger than 1, but it will be less than 10. Therefore, we can bound 125100 = 10210/1.02430 from below by dividing by 10, and we can bound it from above by dividing by 1. This means that 125100 will be less than 10210 but it will be greater than 10209. Therefore, there are 210 digits in the number 125100. Puzzle 6: Odd Even Sequence From the numbers 1, 2, ... n, start by writing an odd number, and keep writing larger numbers--alternating between even and odd--until you stop at n. Call this an odd-even sequence of n. For example, if n = 3, then the only odd-even sequences are 123 and 3. If n = 8, then the sequences 1278 and 58 are odd-even, but other sequences are not, like 278 (starts with even number), 138 (two odd numbers in a row), 1438 (going from 4 to 3 is a smaller number). For an arbitrary n, can you figure out a pattern for how many odd-even sequences there are? Answer To Puzzle 6: Odd Even Sequence First, let's list out some sequences n = 1, sequences = 1 n = 2, sequences = 12 n = 3, sequences = 123, 3 n = 4, sequences = 1234, 14, 34 n = 5, sequences = 5, 345, 145, 125, 12345 n = 6, sequences = 56, 36, 3456, 16, 1456, 1256, 123456, 1236 n = 7, sequences = 7, 567, 347, 367, 34567, 147, 14567, 127, 12567, 12367, 12347, 1234567, 167 Counting the number of sequences for each case, the sequence is 1, 1, 2, 3, 5, 8, 13, ... Remarkably, this is the Fibonacci sequence! Write f(n) for the number of odd-even sequences of n. Now we need to understand why f(n) = f(n - 1) + f(n - 2). There is a correspondence between the number of sequences as follows. From a list of sequences of n - 1, we can append the number n to form an odd-even sequence of n. Therefore, there are at least f(n - 1) sequences for n. Similarly, for any sequence of n - 2, we can replace the last term n - 2 with the number n (this is legal because both n and n - 2 have the same parity). These sequences will all be different because none of them include the number n - 1. So we have f(n) is at least f(n - 1) + f(n - 2). Doing the logic in reverse will show that f(n) is at most f(n - 1) + f(n - 2): from a list of sequences of n, every sequence is either a concatenation of a sequence from n - 1 or it is a modification of one ending in n - 2. Therefore f(n) = f(n - 1) + f(n - 2). This puzzle is a variation of a problem on qbyte. Puzzle 7: Divisible By 3 Let's play a little game. Write down 5 positive whole numbers. Any 5 will do. If you hand me the list, there is an interesting thing I can do. I can always select 3 of the numbers you wrote and their sum will be divisible by 3. For instance, let's say you wrote down 1, 2, 3, 4, 5. This is an easy one. When you hand me the list, I can quickly identify 1 + 2 + 3 = 6 which is divisible by 3. If you instead wrote a different list like 11, 23, 7, 19, 54, the game will be a bit harder for me. But with a bit of work, I can figure out that 11 + 19 + 54 = 84, which is divisible by 3. The challenge is: why is this always the case? Why is it that in a list of 5 positive whole numbers there is always a group of 3 numbers that have a sum divisible by 3? Answer To Puzzle 7: Divisible By 3 It is instructive to work on a simpler problem before tackling the puzzle at hand. We will first prove that in any list of 3 positive whole numbers, there is a group of 2 numbers whose sum is divisible by 2. Working out divisible by 2 This problem is much easier to work out. Suppose the first number in the list is even. If either the second or the third number is even, then that will be a pair of even numbers. Clearly their sum will be even (since even + even = even) and we are done. If neither the second nor third number is even, then that means both the second and third number must be odd. In that case, the second and third number will have an even sum (since odd + odd = even). What if the first number in the list is odd? A similar argument works here. Either one of the second or third numbers is odd--creating a pair with an even sum (since odd + odd = even)--or both the second and third numbers are even--again creating a pair with an even sum (since even + even = even). The proof can also be explained more succinctly using the terminology of number theory. Since all we care about is whether the numbers are divisible by 2, we can work modulo 2. Therefore, each of the three numbers is either 0 or 1. There are 3 numbers to be placed into two "slots" of 0 or 1, so by the pigeonhole principle at least two of the numbers are equal to 0 or two of the numbers are equal to 1. In either case the pair has an even sum. (The pigeonhole principle states that if n + 1 pigeons are to be put into n pigeonholes, then at least one pigeonhole has more than one pigeon. An equivalent statement is the maximum is at least the average, or the minimum is at most the average.) Divisible by 3 We will use the pigeonhole principle to solve the problem. Each of the 5 numbers can be written in modulo 3 since all we care about is divisibility by 3. Each of the 5 numbers will either be 0, 1, or 2. The first case is if the list has one of each number. In that case, we are done since 0 + 1 + 2 = 3 which is divisible by 3. So assume the list only contains two of the possible remainders (either 0, 1 or 0, 2 or 1, 2). In that case, we have 5 numbers that need to be placed into two "slots." By the pigeonhole principle, one of the slots must contain at least 3 numbers from the list. This triplet of numbers will be divisible by 3 (because 0 + 0 + 0 = 0, 1 + 1 + 1 = 3, and 2 + 2 + 2 = 6, and each sum is divisible by 3). Therefore, in any list of 5 positive whole numbers, there is a group of 3 numbers that is divisible by 3. As a concluding remark, the result can be generalized that in a group of 2n - 1 numbers, there is always a subset of n numbers whose sum is divisible by n. This is known as the Erdos-Ginzburg-Ziv Theorem and is a bit more complicated to prove. Credit: I first read about this puzzle on the Harvard University Physics Department Problem of the week. The link I have is broken, but this was problem 80 "divisible by 9" (possibly accessible from the Wayback Machine.) Puzzle 8: Two Be Or Not Two Be Out of the numbers 0 to 9,999,999, which is larger: the set of numbers where the digit 2 appears at least once or the set of numbers where none of the digits is equal to 2? Answer To Puzzle 8: Two Be Or Not Two Be Write each number as a 7-digit number, so that a number like 8 is written with six leading zeroes as 0000008. A number that does not contain 2 is written using any of the other 9 digits: 0, 1, 3, 4, 5, 6, 7, 8, and 9. For a number that does not include the digit 2, there are 7 digits that can be any of the 9 digits not equal to 2. So there are 9 choices for the first digit, then 9 choices for the second digit, and so on for each of the nine digits. Therefore, there are 9(9)(9)...(9) = 97 = 4,782,969 numbers that do not contain the digit 2. The remaining 10,000,000 - 4,782,969 = 5,217,031 are numbers that have at least one appearance of the digit 2. Hence, the numbers with the digit 2 are more common. An alternative method is to count the numbers that contain the digit 2. In a 7 digit number, a number with exactly 7 - x digits equal to number 2 can be chosen in [7 choose (7 - x)]9x = (7 choose x)9x ways. This is because there are (7 choose x) spots to choose the digits not equal to 2, and each of those can be any of 9 possible digits. We want at least one appearance of the digit 2, so we need to sum this formula from x = 0 to x = 6. Doing this on WolframAlpha we arrive at the same answer of 5,217,031. Puzzle 9: Infinite Fraction What is the value of x in the following equation? Answer To Puzzle 9: Infinite Fraction The trick is noticing a repetition in the fraction. The quantity below the fraction is itself equal to x. This means an answer satisfies x = 1 + 1/x. Multiplying both sides by x and re-arranging terms, we get a quadratic equation x2 - x - 1 = 0. The solutions are x = (1 + √5)/2 ≈ 1.618 and x = 0.5(1 - √5) ≈ -0.618. Obviously x is the sum of positive terms, so we can rule out the negative solution as an extraneous solution. Therefore, x = (1 + √5)/2, and the golden ratio comes out of nowhere! Incidentally, such infinitely repeated fractions are known as continued fractions and they have some interesting mathematical properties. Puzzle 10: Nested Radical What does the following expression equal? Answer To Puzzle 10: Nested Radical Here is a derivation of the answer. We can solve the expression for a general constant a > 0 using the quadratic formula: Now consider the long-term behavior of this function compared to the simple square root function. In other words, the nested radical converges to the more familiar square root function. Puzzle 11: Infinite Exponents Solve for x in the following equation: Answer To Puzzle 11: Infinite Exponents Once again, there is a trick that the entire exponent tower is the same as the whole, so we can solve as follows. You can also solve the problem in another manner. Denote the exponent u = xx.... We know that xx... = 2, and so: xx... = x2 = 2 The answer is x = √2 Here an intuitive explanation of the solution (this is not a way you could have found the answer, but it somewhat explains why the answer is true). Remember that when you raise a number to a power, you end up multiplying the exponents. That is, (xa)b = xab Since √2 = 21/2, consider what happens when this number is raised to the power of 2. We get (2(1/2))2 = 2(1/2)2 = 2 In the expression with infinite exponents, we have 21/2 being raised to itself over and over again. Each time that x = 21/2 is raised to another power x = 21/2, the exponent in the base term (1/2) gets multiplied by the base term from the next exponent (2). These terms cancel out to 1, and the process repeats with each successive power. In the end, the expression turns out to be 2 to the power of 1, which is 2. I should clarify everything done above is contingent on the infinite tower of exponents converging. If you do the same problem with the infinite exponents equaling 4, then you would get x4 = 4, which is also an answer of x = √2. This is nonsense, since we just found out that x = √2 converges to a value of 2. So to be more careful, we must consider when the tower converges in the first place. If the infinite tower converges to a value y, then our value x must satisfy the equation xy = y. Thus we have x = y1/y. Now we can do a bit of work to show this converges when x is between the values of e-e and e1/e, which is roughly 0.066 to 1.44. So the infinite tower only has a solution when it is set to a value between 1/e and e, roughly between 0.368 and 2.718. That's why we got a nonsensical result when we set the equation equal to 4: that equation does not have a solution. Puzzle 12: Guess My Polynomial I'm thinking of a polynomial f(x) where the coefficients can only take the values of -1, 0, and 1. I will give you information. For any number a you submit, I will tell you the value of f(a). But each time you ask me a number it will cost you a dollar. What's the least cost method to figure out my polynomial? Answer To Puzzle 12: Guess My Polynomial Remarkably you can figure out my polynomial after asking for one number! The short answer is you need to ask for a = 3 and convert f(3) to base 3. From there it will be easy to deduce the polynomial. Let's do an example to see why. Suppose I tell you that f(3) = 9. The base 3 representation of the decimal number 9 is (100)3 because 9 = 1(3)2 + 0(3)1 + 0(3)0. Since the base 3 representation of a number is unique, it must have been that f(x) = 1(x)2 + 0(x)1 + 0(x)0. In fact, whenever the base 3 representation of f(3) contains only 0's and 1's, we can simply read off the base 3 representation as the coefficients of the polynomial. Things are only slightly trickier when the base 3 number contains some 2's. For example, let's say f(3) = 8. We again convert into base 3 to get f(3) = (22)3. If our polynomial could have coefficients of 0, 1, and 2, then we could just read off the values of the base 3 number as the coefficients. That is f(x) would be 2x + 2. But our polynomial can only take values of 0, 1, and -1. So we need to do one more conversion: if the value for 3k is 2, we convert that coefficient into a -1 by subtracting 3(3k) and then we will add 3k+1, which has the effect of increasing the placeholder for 3k+1. This number base system is known as balanced ternary. By this process we can convert every unique representation in base 3 to a unique representation in balanced ternary. Therefore, the value of f(3) in balanced ternary will give us the coefficients of the polynomial. In our example, f(3) = 2(3) + 2. Now we convert to balanced ternary. First we will change the 2 in the units value into a -1 by adding and subtracting 3. We will do this step in detail to illustrate the process. That is, f(3) = 2 + [(-3) + (3)] + 2(3) = (2 + -3) + (3 + 2(3)) = -1 + 3(3). Now we write 3(3) = 32 and include placeholders for 31 and 30. So we have f(3) = (1)32 + (0)31 + (-1)30, and therefore our balanced ternary representation is (1 0 -1). Our original polynomial must have been f(x) = 1(x)2 + 0(x)1 + -1(x)0. To prove this procedure works generally, note the following. For a polynomial f(x) = cnxn + ... c1x + c0, f(3) = cn3n + ... c1(3) + c0 f(3) in base 3 = (cn...c1 c0) And we can find the balanced ternary by converting from the unique representation in base 3. Let's do a final example to illustrate once more. Let's say f(3) = 99. We have 99 = (10200)3 = (1)34 + (2)32. We need to get rid of the 2 so we add and subtract 33. That is, (1)34 + [33 - 33] + (2)32 = (1)34 + 33 + [-33 + (2)32] = (1)34 + (1)33 + (-1)32 + (0)31 + (0)30. Therefore f(3) = (1 1 -1 0 0) in balanced ternary, and f(x) = x4 + x3 - x2. And a fun fact of trivia, the Soviets developed a computer using balanced ternary as an alternative to binary. But it seems whatever computational advantages it had did not stop binary computing from being adopted. Puzzle 13: Find The Missing Number Microsoft used to ask this problem in interviews to test knowledge of algorithms. I've re-characterized the puzzle in terms of a situation involving an Excel spreadsheet. Your boss sends you a spreadsheet with a list of tasks. In one column your boss has written the task, and in the column next to it he has ranked each task in importance from 1 to 100. The list is unordered. Your boss, however, is incompetent, and sends you a list with only 99 items--so you know one of the items is missing. How can you quickly find out which task number is missing? There are many ways to do this. The puzzle is to come up with an efficient algorithm. Bonus: What if there are 2 tasks missing? Answer To Puzzle 13: Find The Missing Number A brute force method is to check if the list contains task 1, then task 2, and so on. This is obviously inefficient as you have to keep looping through the list. A much better method is