These puzzlers are to test your resolve. See if you can solve them before reading the solutions.
The Manhole Covers problem is a warm-up puzzler...just to get you started solving Thinking Problems, problems that you probably have not seen before and thus require some thinking. There is even kind of a surprising result for this Manhole Covers problem, so be sure to download and read the PDF solution file...
Are these shapes possible for manhole covers?
The January 2011 issue of the German View magazine showed the following photographs by Remo Camerota of various decorative manhole covers in Japan. Notice that even these artistic manhole covers are still circular.
<-- click on the Download (down arrow) to download this PDF in order to enter the password and view it locally.This PDF file explains the more or less obvious reason why manhole covers must be circular --- otherwise it would be possible for the covers to fall through the manhole openings. But did you know that other shapes are also possible? Did you know that a Pennsylvania company, Watts Brothers Tool Works from Wilmerding, PA sells drill bits that drill square holes?Puzzler: How is this possible? How can one drill a square hole?
- Two glasses, one containing precisely 1 cup of water, the other with precisely 1 cup of wine.
- Take exactly one teaspoon of water from the water glass and add it to the wine glass. Stir well.
- Take exactly one teaspoon from the water in wine mixture glass and return it to the water glass.
Puzzler: Is there more wine in the water glass or water in the wine glass?
[Note: While wine is roughly 90% water, for this puzzler we consider wine to be make up of "wine" molecules. Thus wine is 100% wine molecules, and water is 100% water molecules.]
This problem has spawned many a fight at dinner parties, why even I have come dangerously close to suffering a punch from a dinner guest who refused to believe the Pigeonhole Principle.
Follow this link to a webpage illustrating the Pigeonhole Principle solution to this Wine and Water, Water and Wine Puzzler: Wine and Water SolutionThis PDF file begins with several Card Tricks and ends with the Water and Wine Problem. Have fun!
How many revolutions will the 1992 quarter make as it is rotated around another quarter? The knurled edges of the quarters mean that there is no slippage during this operation; it is just as if the quarters were two gears with meshed teeth.
If you were to roll the 1992 quarter all the way around the 1991 quarter so that it returns to its position as shown, then how many rotations, or revolutions, will the 1992 quarter make during its travels around the 1991 quarter? In other words, how often will the head turn over during its roll? Please carefully explain your answer. That is, I want to know why your answer is what it is. I don't want you to just say that when I did the experiment with two quarters, this is what I found. I want you to explain, as best as you can, why you found the result that you obtained empirically.
If you answered 1 (perhaps you said to yourself, "the 1992 quarter is making one circuit around the 1991, so it must make one revolution"), would you believe that I have found a magical quarter that revolves twice during this trip? And I'll sell my magical quarter to you for only 50 cents!
If you do not wish to see the explanation for the coin revolution problem at this time, then skip the following Coin Rotation Explained link, Coin Rotation Explained, to arrive at the actual Puzzler.
And now for the actual Puzzler:Puzzler: How long is a Sidereal Day?
The Earth orbits the Sun once in 365.2422 Solar Days (24 hour days), roughly. A Sidereal Day (sidere is Latin for star) is the time it takes the Earth to spin 1 revolution about its axis relative to the distant stars (and therefore not relative to the Sun). If I told you that the rotation direction of the Earth around its axis is the same direction as the Earth's orbit around the Sun, then calculate the length of a Sidereal Day (how many hours, minutes, and seconds in a sidereal day?).
Hint: Remember the Coin revolutions!
The following PDF explains and calculates the length of a sidereal day to within 1/100th of a second:
Knowing six simple facts allows one to determine the geometry of the spins and orbits of the Earth, Moon, and Sun around each other. For instance, the fact that the Sun rises in the East and sets in the West, and the solar day is much shorter than the year, allows us to conclude that from a viewpoint above the North pole the Earth spins in a counterclockwise direction.Knowing that the sidereal day is slightly shorter than the solar day allows one to determine the direction of the Earth's orbit around the Sun.Likewise, with the knowledge that the synodic month is longer than the sidereal month, one can find the orbital direction of the Moon around the Earth. And observing that we only see one side of the Moon from the Earth allows us to determine the direction of the Moon's spinning.
Now that we have calculated that the Sidereal Day is shorter than the Solar Day (previous Puzzler), using this information in conjunction with the fact that you know the Sun rises in the East and sets in the West, determine the direction that the Earth orbits the Sun.
We turn now to studying the orbital motions of the Moon. First of all, let's discuss the phases of the Moon and what they mean for the positioning of the Earth, Moon, and Sun, shall we?
Can you "see'" a new Moon at midnight? Draw a diagram to help explain your answer. And lastly, why can we sometimes "see" a very, very dim disk of the new Moon anyway? Where does the light come from, are there lights on the Moon?
Please sketch a diagram showing the relative positions of you (the observer), the Earth, the Moon, and the Sun during a full Moon, a new Moon, a crescent Moon, a gibbous Moon, and a half Moon.
Can you ever see the lunar eclipse of a crescent Moon?
Goodness, you certainly are getting good at thinking through these 3-dimensional problems! You have done a magnificent job! Let's exercise some of your 3-dimensional prowess by continuing on to the Moon's orbital motion.
What is known as the Synodic Month is the time taken by the Moon to orbit the Earth, as measured from new Moon to new Moon. The Sidereal Month, on the other hand, is the period of the Moon's orbit relative to the fixed stars. If I told you that the Synodic Month was longer than the Sidereal Month, please determine in which direction the Moon orbits the Earth.
There is one more interesting motion of the Moon. I'm sure you have noticed that whenever you gaze at the Moon, you always see the same side. In fact, there have only been a handful of humans who have ever personally seen the other side of the Moon (specifically, the Apollo astronauts who have orbited the Moon). Now for the question, does the Moon also spin about its axis?
All of these questions and more are answered in the following PDF file:
Which way does Newton roll his roller? Here is a puzzler to test your physical intuition...
Notice that if Steve tugs on the orange string, then he is applying a force on the roller to the right which should roll the roller to the right, right? But wait, the force from the string is also applying a torque to the smaller disk attached to the roller. And this torque would try to roll the roller to the left. So which is it? Does the roller roll right or left?Puzzler: Does the roller roll to the right or to the left when the string is pulled?
Here is the analysis:
(I may demonstrate this experiment during one of the FPF talks.)
How high does the ball bounce? How about another test of your intuition into physics...
In this photograph a small marble (red, white, and blue ball) is balanced on top of a large Superball (large translucent ball with orange swirls inside). If Sandy is holding the Superball about 9 inches above the floor when she drops it, then how high will the marble bounce?
There are a few possibilities. Some people think that the marble remains in contact with the Superball during the bounce, thus the marble bounces as high as the Superball. Since the coefficient of restitution for a Superball is roughly 0.95, the Superball/marble combination bounces to a height of roughly 8.1225 inches. Others think that the marble bounces on the Superball itself, thus the marble will reach a height twice as high as the bounce of the Superball, or roughly 16.25 inches. And a few individuals believe the marble will bounce to a height of roughly 80 inches --- patently absurd, don't you think?
Warning: If you attempt to repeat this experiment at home, wear eye protection and perform the experiment outside.Puzzler: How high will the marble bounce? Explain why.
Here is the analysis:
P.S. Did you know that without this mechanism, we would not be here?!!! (Explanation in the above PDF file.)
(I may demonstrate this experiment during one of the FPF talks.)
Here is a real twister of a problem that is guaranteed to twist those brains of yours into knots.
Xena is now twice as old as Yotta was, when Xena was as old as Yotta is now. Xena is now 16 years old. How old is Yotta?
Hints:
- Say you have a younger sister. If you are now 10 and your sister is 7, how old will your sister be when you are 120? Write this relationship as a formula entailing variables for your and your sister's ages instead of your actual ages. Then write an additional equation involving not only variables for your and your sister's ages today, but also additional variables for your and your sister's ages at some time in the past. This equation should help you in your solution of the above Puzzler.
- If you are having trouble with the first hint, then you might want to try this one. Since Yotta must be at least 0 years old and he must also be less than or equal to Xena's current age, we have 18 cases to check: {0, 1, 2, ..., 15, 16}. So, first assume Yotta's age is 0 and check if this satisfies the conditions of the problem. You will discover it does not, so try 1 and check this age. Continue in this fashion until you find the age that satisfies the problem statement. This method is called the Trial-and-Error method, as discussed in our General Solution Strategies maxim.
Here are a couple ways to solve this type of problem: (These kinds of problems are very famous.)
Examine the configuration of quarters as shown in the Figure below. Note that there are two lines of quarters, the horizontal line contains four quarters (1994, 1992, 1995, 1996) and the vertical line contains three quarters (1991, 1992, 1993). You may only move a single quarter: you must move one quarter so that both the horizontal and vertical lines have 4 quarters apiece.
Here is the trick solution:
Oh, no, not another quarter problem! Yup, another one.
In this problem, please refer to following Figure. Notice that on the left-hand side of this drawing there are ten quarters arranged into a triangular shape, like a pyramid. Also note that on the right-hand side of this figure there are again ten quarters arranged into another triangular shape, but this one is "upside-down" relative to the left-hand drawing.
Your task is to convert the coin triangle on the left into the inverted coin triangle on the right. BUT, you must follow the rules. And the rules state that you can only move three quarters while performing this transformation. Can you do it? I bet you can.
And here is the solution:
Here is a problem that was circulating around the halls of MIT in the Fall of 2000. One strategy is to guess the solution by trial and error. See if you can prove the validity of your solution without trying every possible case but rather using a little Number Theory.
The entering freshman class at MIT has precisely 1000 students in it. Following the fine MIT tradition (you should understand that MIT's buildings, subjects, etc. are all numbered, and not named --- for instance, an undergraduate might tell you that she is majoring in 6 instead of chemistry, or has a class this morning in Building 8), let us number these freshman and denote them with an index i, 1 <= i <= 1000. Along the "Infinite Hallway" beginning in Building 1, there are precisely 1000 empty lockers remaining for these new freshmen. Likewise, we label these lockers with index J, 1 <= J <= 1000. Lockers can be in one of two possible states: Open or Closed. When the freshmen arrive in the fall, all lockers are closed.
Being freshmen, the students are assigned the following pseudo-"hazing'' tasks.
- Student 1 passes through the school and opens all 1000 lockers.
- Student 2 makes the rounds of the halls and alters the state of all lockers whose indices are given by J=2k, k a positive integer. In other words, Student 2 examines all of the even numbered lockers and if an even numbered locker is open he closes it and if it is closed he opens it.
- Student 3's job is to alter the state of all lockers with indices J=3k, k a positive integer. She opens or closes every third locker, in other words.
- In general, Student i alters the state of all lockers having indices J=ik, k a positive integer.
Puzzler: When all 1000 freshmen have completed their tasks, how many lockers are open?
My guess is 31! ... Hey, wait a minute, Student 1 opens all 1000 lockers, Student 2 closes all of the open even-numbered lockers, leaving 500 open, Student 3 opens/closes those lockers divisible by 3 and of these half will also be divisible by 2 and thus already closed and the other half will be open, thus after Student 3 the same number of lockers will be open as before Student 3 since Student 3 simply opens the closed lockers and closes the open lockers of which she encounters half and half. ... Therefore doesn't it seem that 31 is way too small of a number for the lockers remaining open? Even from the pseudo-symmetry of the Students's tasks it would appear that many more lockers should be left open at the end, maybe even nearly 500 of them. So my guess of 31 is probably wrong...what is your guess? Prove it.
Here is the PDF describing my Number Theory solution. Enjoy!
Have you ever wondered how to find the day of the week for some specific date in the past, say grandpa's or grandma's birthdate? What if you can't find a calendar for the date? Is there a way to write a formula for calculating such a thing?
Let's see, the days of the week are periodic, repeating every 7 days: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday. And our Calendar, known as the Gregorian Calendar, is also periodic but has complicated rules for exceptions, such as Leap Years, and so forth. Since both are periodic, there must be a way to design a formula to connect one period to the other.
This is a tellurium clock. It has motion works for the Earth's spinning on its axis (day/night) and the Earth's orbit around the Sun (year). In addition it also orbits the Moon around the Earth and spins the Moon about its own axis. All of this is accomplished by the various gears that you see below the Sun, Earth, and Moon. These gears implement some of the periodicities of the Calendar and the motions of the Sun, Earth, and Moon.There are actually many possible such formulae for determining the Day of the Week given a date, depending upon exactly which choices you make while deriving your own formula. For instance, my formula is:
Click for full-size image
This might appear complicated, but it is really quite easy to compute. The variables D, Y', and M' are just simple integers based upon the chosen date. And the funny-looking "half-brackets" simply mean to take only the integer portion of the fraction and throw away the decimal portion. The mod 7 means to divide by 7 and take whatever integer remainder results. Thus d has one of the values 0, 1, 2, 3, 4, 5, or 6 corresponding to Sunday through Saturday.
The above Day of the Week formula is based upon the Gregorian calendar. This calendar was adopted in 1582, and thus this algorithm correctly determines the day of the week from that date forward. [Because of the inaccuracy of the previous Julian calendar, the astronomical vernal equinox had drifted from its March 21st date. Thus, to get the astronomical equinox to correspond with this calendar date required for ten days to be deleted from the calendar. And we might ask why should the vernal equinox correspond with March 21st? There were a couple religious reasons for this readjustment of the spring equinox. The first was to keep Easter from colliding with religious holidays at the start of January. The other was to keep Easter from colliding with Passover. This last criterion is not perfectly followed by the Gregorian calendar, however, as Easter and Passover do occasionally fall on the same date. Most recently, 1981 had both holidays on the same day, and the next time this will occur is in 2123. But, back to 1582, in that year Pope Gregory XIII decreed that the Church would adopt the Gregorian calendar, and, in doing so, 10 days were deleted from the calendar in order to adjust the vernal equinox. Thus, Thursday, October 4, 1582 was followed immediately by Friday, October 15, 1582. This produced a jump discontinuity in the day of the month cycle while keeping the days of the week cycle intact.] The Gregorian calendar is an effort to more closely match the calendar with the actual value of a tropical year, from equinox to equinox. A tropical year is not a whole number of days, rather it is roughly 365.24219878 ephemeris days. To account for the roughly 1/4 of a day over 365 days, the Julian calendar added a day every 4 years. This added day was known as a leap day. Adding a day every four years yields a length of the year as 365.25 days, which is just a little too long. To compensate, the Gregorian calendar skipped the leap day once every 100 years. This adjustment lead to 24 leaps days every 100 years for an average year length of 365.24, which is now just a shade too small. Consequently, the Gregorian calendar also added back the leap day once every 400 years. This meant that there were 97 leap days added to the calendar every 400 years producing an average length of the year as 365.2425 days, which is now just a smidgen too long. But with this explanation of the Gregorian Calendar, you now recognize why the denominators of 4, 100, and 400 appear in my formula above, they represent the various exceptions rules correcting the Gregorian Calendar.
See if you can come up with your own formula for computing the Day of the Week for years past. Then pick your grandma's birthdate, and determine on which Day of the Week she was born. Or, if you would rather, you might just use my formula to compute the Day of the Week of grandma's birth.Example: July 4, 1776
As an example, let's pick the birthday of our nation. Even though the Second Continental Congress authorized separation from Great Britain on July 2, 1776, and the Declaration of Independence was not fully signed until August 2, 1776, the birthdate of our nation is typically taken to be July 4, 1776, the date listed on the Declaration of Independence. Since July 4, 1776 is after October 15, 1582 when the Gregorian Calendar took affect, our formula is applicable to this date. Performing the calculation, I find that July 4, 1776 was a Friday.
The full details of the Day of the Week computation are included in this PDF file:
Just before your exam, you accidentally spill water all over your calculator. You dry your calculator, test a simple addition, thank your lucky stars it still works, and then rush to your exam. When you get there, you're exasperated to find that your calculator is having some problems, however. In particular, all of the digit keys (1, 2, ..., 9, 0) and the decimal point key are working. And the "+", "-", and "1/x" keys are operating fine. But when you try to multiply two numbers, you pushed the times, "X", key and got no response. The divide key, "/", also isn't working. (Also, you can assume that a memory location into which you can store and recall a number is also working. Depending upon the type of calculator you have, this memory might be a separate memory key or keys, or it might be a "stack" as on Hewlett-Packard RPN calculators. In any case, assume that you have enough memory to store whatever intermediate results you may wish to save.) When you open the exam, your stomach sinks to your feet when you scan the first page and it is covered with problems like the following.
So, can you try to use your "brain dead" calculator with only the +, -, and 1/x keys working properly, or do you bite the bullet and resort to longhand multiplication?
Click for full-size image
Of course, your father's words come back to haunt you: "Always take your slide rule to your exams. No batteries to run out of juice in the middle of a test. It will never fail you!" Oh, if only you had listened and brought your slide rule as a backup.
The Pickett N4 and N600 slide rules...
Troubles? If you are having some trouble with this task, then read the following Hints one at a time. Each subsequent hint provides a little more guidance.
Hint 1: You guessed it: Figure out how to use only the +, -, and 1/x keys to perform multiplications.
Hint 2: If you are having trouble thinking about how to solve this dilemma, why don't you first just experiment with your calculator trying different things using only the +, -, and 1/x keys. If you find something interesting, this might suggest an insight into solving this problem. This is a difficult problem, and you must work diligently in order to solve it. Good luck!
Warning! This is a fairly difficult problem, so please don't be discouraged if you haven't solved it the first day. You may need to mull it over in your mind for several days before the insights needed to solve this problem glide down to rest upon your window sill. If you are still troubled after a few days time, and you wish to entertain further hints, then read on.
Hint 3: You might begin by first attempting a slightly easier problem: using only the +, -, and x^2 operator keys on the calculator, design a procedure for multiplying any two numbers. The solution to this simpler "broken calculator" problem will be instrumental for your solution to this Puzzler.
Hint 4: OK, if you really have thought hard about this problem and tinkered around on your calculator for a good day or two, and you now wish to see a detailed hint, then read further. Think about using the equations: 1/(1/x)=x, 1/x+1/y=(x+y)/xy, (x+y)^2=x^2+2xy+y^2, and 1/z+1/z=2/z. There is one thing missing from these equations: how do you get rid of the (x+y) in the 1/x+1/y equation. Be creative, think about what you might set (x+y) to equal. (See Hint 5.)
Hint 5: Try setting (x+y)=1 in the addition of reciprocals. You should then understand why the (x+y)^2 equation was included in Hint 3.
Good luck!
The following PDF file derives the method of multiplying using only +, -, and 1/x. You should also know that computers often use alternative methods for multiplying, especially for multiplying extremely large numbers, for reasons of speed. Here is the Broken Calculator solution:
Okay, so this is our Battle Cry ... whenever we feel overwhelmed, we just stand up and scream, "Quod est, Nullum non problema solvere." ("There is no problem that cannot be solved.")
And Euler said, "Carry out the following computations on a calculator, oh youthful soul, and you shall be rewarded." [Okay, I'm teasing you, of course Euler didn't really say this; there were no calculators in his day. Euler said to use a slide rule instead! ... just kidding once more ... Euler didn't say this either. But you really should carry out these computations nevertheless.]
Before you begin the subsequent calculator computations, allow me to ask you a question. Did you know that solving a math problem once saved the neck of a King of France? Yup, that's right ... and I'll get around to telling you about this little bit of math trivia in the solution to this problem given in the PDF file. But first, I'd like to quote that very same Renaissance mathematician who once saved the life of his king by solving a math problem:
"Quod est, Nullum non problema solvere." ("There is no problem that cannot be solved.")As I mentioned above, the solution in the PDF file discusses the multifaceted relevance of the above quote from Viete to this problem.--- Francois Viete, in In artem analyticam isagoge
(Introduction to the analytic art), Tours, France, 1591.
Note: In the following algorithm, the symbol |-> used in the expression V |-> (V+W)/2 means that the new value of the variable V is set equal to the current value of the variable V added to W and divided by 2. Also, the following algorithm assumes that you have six memories on your calculator, one for each of the variables listed in Step (1.) below. If your calculator does not have six memories, then you will need to record their intermediate values to the full resolution of your calculator (i.e., all 10 to 15 digits) in a table and re-enter them when needed.
Calculator Computations:
- Initialization: Set T=U=V=W=X=Y=1 .
- X |-> X/2 .
- Repeat Step (2.) once (thus for a total of two times).
- Z |-> (1/2)((V+W)(V+W)/2X) .
Record this value of Z in a table.- W |-> W/2 + (1/2W)/2 .
- Repeat Step (5.) four times (thus for a total of five times). Important: The number of iterations in this step must be greater than the number of iterations that you perform in Step (16.).
- Z |-> (1/2)((V+W)(V+W)/2X) .
Also record this value of Z in your table.- U |-> V .
- V |-> (V+W)/2 .
- T |-> T/2 + WU/2T .
- Repeat Step (10.) five times (thus for a total of six times).
- W |-> T .
- X |-> X - Y(V-U)(V-U) .
- Y |-> 2Y .
- Z |-> (1/2)((V+W)(V+W)/2X) .
Record the value of Z for each iteration in your table, too.- Repeat Steps (8.) to (15.) three times (thus for a total of four times). Important: The number of iterations computed in this step must be less than the number of iterations that you performed in Step (6.).
What do you notice about Z ?
Note: The only calculator keys that you employ in this computation are: 1, 2, +, -, X, /, and maybe (), if your calculator has parentheses. You also might need to use your calculator's Memory Store and Recall keys or Stack manipulation commands, but only to save intermediate results. (When I say that you use only the number keys 1 and 2 for this computation, this assumes that you did not have to re-enter any of the intermediate computed variables: T, U, V, W, X, or Y. If you had to record and re-enter these intermediate variables, this does not count towards using other number keys besides 1 and 2, since if your calculator had more memories you would not have needed to re-enter these numbers.)
The following PDF file explains this calculator computation as well as discussing Archimedes, Viete, Newton, Turing, and numerous other calculations of Z:
P.S. I once gave this calculator problem as a weekly homework assignment to a group of students attending a Math Club I was running. The following week a number of the students had computed the correct value of Z.P.P.S. Mathematics Details: This algorithm is based upon Gauss's discovery for using the Arithmetic-Geometric Mean (AGM) to calculate Elliptic Integrals of the First Kind. Normally, the geometric mean requires the computation of the square root. I modified the AGM procedure to eliminate the need to directly compute the square root thereby allowing this algorithm to be carried out on the simplest of calculators, a four function (+,-,x,/) calculator, that does not have a square root key.
Here is a sequence of six problems that will hone your skills for performing Mathematical Induction proofs. If you aren't versant in the technique of Mathematical Induction, see this page for an introduction:Mathematical Induction
Preliminaries:
You own a cattle ranch. And you take a major pride in your seven premier prize bulls that are recognized as some of the finest specimens in all of Texas. One condition that you must carefully ensure is that the bulls are always in separate paddocks during breeding season, for if they are housed together they have a tendency to fight and can seriously injure one another. One day, by mistake, the seven bulls, the Bs, are routed into a single pen together with a number of cows, the Cs. It's too dangerous to attempt to separate the bulls by horse, and you need to get them in separate pens quickly before anything serious happens. You do have a fence posting machine that attaches to your tractor that can relatively quickly lay a new line of fence. Unfortunately, the fence posting machine really only lays fence quickly along a straight line; if you want to make a bend in the fence by turning your tractor, it is a very time consuming task to realign the equipment. You can, however, cross another line of fence simply by cutting the barbed wire of one line, laying the new fence through the hole, and then mending the original line.
Since each of the bulls is presently entertaining a harem of cows, they are fairly stationary in their present locations, but you worry that once a bull starts looking around he is likely to charge another bull. So, as the fastest possible way to safely separate the bulls, you decide to lay new straight fence lines across your paddock. Of course, the fewer the number of lines you need to lay to separate the bulls the better. One of your ranch hands has designed a plan that requires four lengths of fence. But several of your prize bulls are drifting dangerously close to one another and you worry about a fight breaking out any minute. Can you separate the seven bulls with fewer lines thus accomplishing this task faster, with less risk of a fight, and also using less fence and thus less expense to you?
So, you have created a design that uses only 3 new fences which both separates the bulls more quickly thus reducing risk of injury stemming from a fight as well as minimizes your expense for new fence. How do you know that this is the best that can be accomplished under these conditions? Is there a way to separate the bulls using only two new fence lines?
I know this fictitious scenario is a little far fetched, but I only wanted you to think about dividing a plane into separate regions using straight lines. Notice that the above 3 new fence lines divide the original paddock into 7 regions.
Before we proceed to our actual Puzzler whose solution will also answer our questions about separating the seven bulls, you may wish to review the Mathematical Induction technique by clicking on this link: Mathematical InductionBelow are the Region Counting Puzzlers:
Take a plane and divide it into regions using straight lines. For instance, with zero lines the plane is divided into 1 region, the entire plane, as illustrated by the upper left-hand diagram of the above figure. The first line divides the plane into two regions, as illustrated in the drawing labeled 1. The second line divides the plane into either 3 regions (if the second line is parallel to the first as shown in 2a) or 4 regions (if the second line intersects the first as in 2b).
Always assume that each new line drawn is not parallel to any previous line, as in the drawing 3a above, and the new line is not drawn so that it passes through the intersection point of two previous lines, as in 3b. Thus each new line intersects all previous lines at new points of intersection, as shown in 3c. How many regions will result from k lines?
One of the more famous elementary problems in mathematics is known as the Map Coloring Problem. Given any map, how many colors suffice to color the map so that no two bordering countries have the same color? This problem has attracted numerous attempts at solutions, and a number of false solutions have been published, thoroughly humbling those authors. Only in 1976 was this problem finally solved, and its solution required a supercomputer. This was the first "computer" proof of a mathematical theorem, and many mathematicians are still not comfortable with a "computer" proof that has not been checked by a human mathematician. And many mathematicians still secretly hunger for a short, beautiful, human proof of the 4-Color Map Theorem. Maybe you will be the one to discover this clever human proof thereby beating the computer?!
One of the proposals for a demonstration is to examine this Map Coloring Problem in detail in order to understand why it is so difficult of a problem and then to understand the clever techniques that were created to eventually solve it. For this Puzzler, however, we will not consider the full Map Coloring Problem, rather we restrict ourselves to maps generated by straight lines. For these straight line maps (see the drawing below), it would appear that only two colors are required. Is this always true for any straight line map?
For a map generated by the regions of the plane formed by k lines as in the above problem, how many colors are needed to color this map so that no two adjacent countries have the same coloring?
Now divide the plane using circles. Every new circle has a distinct center and is not tangent to any previously drawn circle. As long as each new circle intersects all previously drawn circles at two points, then the greatest number of regions will be created. How many regions result from k circles?
Congratulations, you have now solved some dissection counting problems using Mathematical Induction (if you followed my solutions, that is). Let's next extend these plane dissection problems to three dimensions. So the new problem is how many volumes are generated by planes.
Consider 3-space. A plane divides 3-space into two volumes, as shown in 1 above. A second plane that intersects the first one divides 3-space into 4 volumes, as in 2b. Assuming that each new plane is not parallel to any previously drawn plane, that is, each new plane intersects all previous planes, then how many volume regions result from k planes?
Again consider 3-space, but this time divide the space into regions by spheres. Each new sphere has a distinct center and is not tangent to any previously drawn sphere, and each new sphere intersects all previous spheres. The intersection between any two spheres is a circle. How many volume regions result from k spheres?
Okay, you are probably pretty confident in your abilities to use Mathematical Induction to derive and prove these types of counting problems. And you have accomplished much in performing the above countings. I hope these problems have been good practice for you. But let me warn you, you must be cautious, as the following problem illustrates, and make certain that you properly prove your steps when using Mathematical Induction. The following counting problem is quite tricky.
Take a circle. Pick a point on the circumference of the circle. With a single point we cannot draw a chord, thus the circular disk is left with 1 region, the entire circular disk. Choose a second distinct point on the circumference, and connect these two points with a line thus forming a chord, as drawn in the upper right-hand diagram above. This chord divides the circular disk into 2 regions. Choose a third point, and draw all possible chords between pairs of these three points. The circular disk is now dissected into 4 regions (bottom left-hand drawing). Pick a fourth point, draw all possible chords, and now we find 8 regions (bottom right-hand diagram). Pick a fifth point, drawing all chords yields 16 regions. For each new point, make certain that all of its chords do not pass through the intersection points of previously drawn chords. How many regions are possible after selecting k points?
(As you have probably surmised from my warning, the solution is not 2^(k-1) as would be implied by the first 5 cases listed above.)
When I first ran into these equalities, I was surprised that the sum of a bunch of the reciprocals of integers and powers of integers had anything to do with pi=3.14159265358979323846..., the ratio of the circumference of a circle to the circle's diameter. See if you can prove the following equalities. The first three are easiest to derive using Fourier Series, the fourth one can be derived using simple trigonometry. Even if you don't want to tackle the derivations of these equalities, are they not magical to contemplate? ...
- pi/4 = sum_{i=1}^{infinity}(-1)^{i+1}1/(2i-1)
Isn't it amazing that the alternating infinite sum of the odd integer reciprocals is equal to pi/4?!
Click for full-size image [Make sure you are comfortable with Fourier Series before attempting to derive the above equality.]
Hint: Find the Fourier Series for f(x)=1+x for -x_0 < x < x_0 and periodic outside this interval. Let x_0=pi and then substitute x=pi/2 into the resulting Fourier Series. Once you realize that trigonometric sine and cosine functions have a lot to do with pi, it then becomes clear why pi is related to the alternating infinite series of the reciprocals of odd integers.
This PDF contains the Fourier Series derivation:And if you did not like the Fourier Series derivation, the following PDF file contains the derivation using a Taylor Series expansion:
- pi^2/6 = sum_{k=1}^{infinity}1/k^2
Isn't it surprising that the sum of the reciprocals of the squares of all integers is pi^2/6 while if we eliminate all of the even integers and only sum the reciprocals of the squares of all odd integers the answer is pi^2/8. Would it not seem that eliminating one-half of the integers should give a smaller value?
Click for full-size image
Hint: Find the Fourier Series for the periodic triangular wave f(x) = -x for -x_0 < x < 0 and f(x) = x for 0 < x < x_0.
The following PDF derives these summations from the Fourier Series expansion of the triangular wave:
- pi^4/90 = sum_{k=1}^{infinity}1/k^4
Click for full-size image
Once again, the sum of the reciprocals of the 4th powers of all of the integers is pi^4/90 while the sum of the reciprocals of the 4th powers of just the odd integers, leaving out all of the even integers, is pi^4/96.
Hint: Apply Parseval's Identity to the Fourier Series for the periodic triangular wave.
This PDF derives these summations from the Fourier Series:
- 2/pi = sqrt(1/2)sqrt(1/2+1/2(sqrt(1/2)))...
Click for full-size image Now isn't this an amazing infinite product?!
[Make sure you are comfortable with the trigonometric identities before attempting to derive this equality.]
Hint: Use the Sum of Sines and the Half-angle Cosine identities in conjunction with the fact that lim_{x->0}sin(x)/x = 1 to derive this equality.
This PDF derives the above remarkable identity using simple trigonometry:
Comments