E20. The 5-5-9-9 Problem
Introduction: A problem that has been well publicized on the Internet is the "Four Fours" problem. It asks for a representation of all integers from 1 to N (where N is as large as possible) using the digit 4 exactly four times, in addition to basic arithmetic symbols as needed. See, for example, http://www.wheels.org/math/44s.html. I have found this problem to be excellent for group work for students at the middle school or high school level, because it allows students of many different ability levels to participate. However, when I gave this problem to a group of teachers in an online course, one teacher responded by listing the answers available from an online source, verbatim, even though it was clear she did not even understand some of the symbols used in "her" solution. I thought this was a clear case of cheating, but the student felt that using the Internet was a legitimate way to solve a mathematics problem. Maybe she had a point. In any case, it became clear to me that it was time to modify the problem to make it one whose solutions would not be available on line. See the following.
Problem: Show how to represent each of the integers from 1 to 50 using the digit 5 exactly twice and the digit 9 exactly twice, in addition to basic mathematics symbols as needed. Allowed symbols are plus, minus, times, divides (including fraction bar), parentheses, square root, exponentiation, decimal point, factorial, floor function, and ceiling function.
Comments:
Problem: Show how to represent each of the integers from 1 to 50 using the digit 5 exactly twice and the digit 9 exactly twice, in addition to basic mathematics symbols as needed. Allowed symbols are plus, minus, times, divides (including fraction bar), parentheses, square root, exponentiation, decimal point, factorial, floor function, and ceiling function.
Comments:
- The numbers 5, 9, and 50 in the problem are all arbitrary, and the teacher is free to change them to customize the problem.
- The definition of "basic mathematics symbols" is crucial to the problem. For example, if you allow the successor function (++ suffix in the C programming language), the problem is trivial, and uninteresting. On the other hand, disallowing the decimal point, floor function, and ceiling function would make the problem much more difficult.
- There are some ambiguities that will come up that must be resolved, such as whether (9-5)(9-5) may be used to represent 44. A question like this would make for good class discussion.
- The following lemma makes the problem easier to solve: If a number can be represented using a subset of the 4 allowed digits, it can be represented using all 4 allowed digits. Proofs involve showing how to use any number of the allowed digits to produce either a factor with value 1, or a term with value 0. I think most students at the high school level could arrive at this lemma without being told about it. In any case, this lemma might make the idea of using a simplifying lemma, so important in mathematics, something students would remember.
Simple but remarkable math facts
I'm putting together a list of simple but remarkable math facts that could be used to spice up a math class, more-or-less at the level of high school math. These should be presentable in the form of questions that could be asked of a class, using some showmanship to draw students into them. I'll give a starter list of questions. Most are from geometry, a couple from probability. Happy to hear from anyone of similar questions.
(1) A length of railroad track is two miles long. To account for expansion in hot weather, the track has been joined in the middle. In hot weather the track expands, with each one-mile long piece expanding by one foot. It will form a shallow isosceles triangle, with base exactly two miles long, and sides 2 miles + 1 foot. How high will the track be at the middle? Less than 1 inch? More than one inch but less than one foot? More than one foot but less than 10 feet? More than 10 feet but less than 20 ft? More than 20 ft?
(2) Tennis balls are frequently sold in packages of 3, with the 3 balls packed into a cylinder. Which is greater, the height of the can or the circumference of the can? By how much? The answer to this question will be much more surprising if the teacher displays such a can. Most students will guess from looking that the height of the can is considerably greater than the circumference.
(3) This is a very common optical illusion. Draw two lines exactly the same length. At the end of one place arrowheads, and at the end of the other reverse arrowheads, something like this:
<--------------------> >--------------------<
Which line is shorter? By what percentage? While not strictly a math problem, it does show that we cannot always depend on the evidence of our eyes, and that in this case measurement with a ruler is more reliable than vision.
(4) Display two statues. The statues are similar (in the sense of geometry, same shape but different size). Tell the class that both statues are made of the steel (or gold?) that the smaller statue weights 10 pounds, and the larger statue is exactly twice the height of the other. How much would they guess it would weigh? You could tie this into the use of a scale model of the Titanic in James Cameron's movie. This is also related to the misuse of 3-d figures in statistical graphs, where typically oil consumption might be indicated by the size of an oil barrel, with the height of the barrel proportional to a country's consumption, greatly exaggerating the difference in consumption between different countries.
(5) A rope has been stretched around the Equator of the Earth (25,000 miles, approximately). How much longer does the rope need to be if it is to be raised two feet off the ground and remain a closed loop?
(6) How many people, picked at random, must be in a room before the probability that two or more people share the same birthday is greater than 1/2?
(7) The Monty Hall problem. You are a contestant in Monty's TV show. You are presented with three doors. There is a prize behind just one of them. You choose one door. Without opening that door, Monty opens one of the other two doors that does not hide the prize. (If your first pick was correct so both unpicked doors have no prize, Monty chooses randomly which of those to open.) He says you may stay with your original pick, or switch to the other unopened door. Should you switch or not? How would your choice affect the probability of your winning?
(1) A length of railroad track is two miles long. To account for expansion in hot weather, the track has been joined in the middle. In hot weather the track expands, with each one-mile long piece expanding by one foot. It will form a shallow isosceles triangle, with base exactly two miles long, and sides 2 miles + 1 foot. How high will the track be at the middle? Less than 1 inch? More than one inch but less than one foot? More than one foot but less than 10 feet? More than 10 feet but less than 20 ft? More than 20 ft?
(2) Tennis balls are frequently sold in packages of 3, with the 3 balls packed into a cylinder. Which is greater, the height of the can or the circumference of the can? By how much? The answer to this question will be much more surprising if the teacher displays such a can. Most students will guess from looking that the height of the can is considerably greater than the circumference.
(3) This is a very common optical illusion. Draw two lines exactly the same length. At the end of one place arrowheads, and at the end of the other reverse arrowheads, something like this:
<--------------------> >--------------------<
Which line is shorter? By what percentage? While not strictly a math problem, it does show that we cannot always depend on the evidence of our eyes, and that in this case measurement with a ruler is more reliable than vision.
(4) Display two statues. The statues are similar (in the sense of geometry, same shape but different size). Tell the class that both statues are made of the steel (or gold?) that the smaller statue weights 10 pounds, and the larger statue is exactly twice the height of the other. How much would they guess it would weigh? You could tie this into the use of a scale model of the Titanic in James Cameron's movie. This is also related to the misuse of 3-d figures in statistical graphs, where typically oil consumption might be indicated by the size of an oil barrel, with the height of the barrel proportional to a country's consumption, greatly exaggerating the difference in consumption between different countries.
(5) A rope has been stretched around the Equator of the Earth (25,000 miles, approximately). How much longer does the rope need to be if it is to be raised two feet off the ground and remain a closed loop?
(6) How many people, picked at random, must be in a room before the probability that two or more people share the same birthday is greater than 1/2?
(7) The Monty Hall problem. You are a contestant in Monty's TV show. You are presented with three doors. There is a prize behind just one of them. You choose one door. Without opening that door, Monty opens one of the other two doors that does not hide the prize. (If your first pick was correct so both unpicked doors have no prize, Monty chooses randomly which of those to open.) He says you may stay with your original pick, or switch to the other unopened door. Should you switch or not? How would your choice affect the probability of your winning?
Changes in Mathematics Research Methods
The following math problem appeared in a math forum that I
follow:
You have a deck of 56 cards, labeled 1 through 56. All the
cards are drawn randomly one at a time. What is the probability that for
exactly one card, the face value of the card is one less than the face value of
the card before it.
The reason for considering the number 56 was not specified,
but that doesn't matter because it is clear that to solve the problem in any
kind of satisfying way we have to solve it in a more general case, where 56 is
replaced by n. In this case, the probability is P(n)/n!, where P(n) is the
number of permutations p of (1, … ,n) for which p(k – 1) – p(k) = 1 for exactly
one k. The problem reduces to finding P(n).
The answer is rather neat, and (SPOILER ALERT) I give it below.
However what I find most interesting is the way my finding the solution to this
problem depended so much on technology. To solve it I did not need to know much
mathematics at all. If I had had to solve the problem 30 years ago, it would
have taken much more knowledge and/or much more time.
The first thing I did was to generate some numerical
evidence. By writing out the acceptable permutations and counting them, I found
that P(2) = 1, P(3) = 2, P(4) = 9, and P(5) = 43. I sent the problem to a
friend of mine, Ken Cutter, who is a MATLAB guru, and he wrote a short program
in MATLAB, using perms(1 … n) to list all permutations and the diff function to
compute the differences p(k) – p(k-1). He discovered that I had missed one
acceptable permutation of (1 … 5) so that actually P(5) = 44. He also gave me
the list of a few more values of P, including P(6) = 265.
I now knew I was looking for a sequence 1 , 2, 9, 44, 265, …
, so I went to the Online Encyclopedia of Integer Sequences (OEIS, https://oeis.org/)
and entered 1 , 2, 9, 44, 265 into the search field, and out came two known
sequences. Only the first of these two sequences seemed to relate to
permutations, and sure enough, one the descriptions of this sequence identified
it as what I was looking for.
The answer turns out to be that P(n) number of derangements
of P(n), that is, the number of permutations with no fixed points. The formula
for P(n) is given on OEIS as P(n) = n!*Sum((-1)^k/k!, k=0..n). On the Wikipedia page for derangements,
it is noted that a common notation for P(n) is !n, so the desired probability
is !n/n! = Sum((-1)^k/k!,
k=0..n) which, as
Wikipedia notes, converges rapidly to 1/e. In fact, it is the first n terms of
the Taylor expansion for exp(x) about 0, evaluated at x = -1. For the original problem with n = 56, the
answer for all practical purposes is 1/e.
Looking
back, the most crucial tool in my finding the solution was The Online
Encyclopedia of Integer Sequences, started by Neil J. A. Sloane, and a
wonderful resource for anyone involved in mathematical work. MATLAB was also
very helpful. Without it, I might have still gotten the answer if I had gone
over my work and discovered my mistake which made me get P(5) off by one. If I
had entered the correct first 4 terms, Online Encyclopedia of Integer Sequences
would have returned 17 sequences, but it would still have been pretty easy to
find the correct sequence from amongst these 17. But MATLAB (and Ken Cutter) saved
a lot of time. Lastly, Wikipedia was a help in explaining the result.
When I was
in school, none of these resources were available. If I knew more about
combinatorial mathematics, I might have known the answer immediately, or at
least recognized it once I generated the numerical examples. Otherwise, I would
have had to look at my lists of acceptable permutations more carefully and perhaps
derived a recursion relation or induction step that would enable me to find the
solution. I would be interested in hearing from anyone would like to send me a
solution to this problem from scratch, imagining that they do not know the
answer already.
This
experiences brings home to me how much the methods of mathematics research have
changed since I was in school. I wonder what changes we should be making in
K-12 math education that take into account these changes.
Reed Magazine Profile
My undergraduate Alma Mater, Reed College, just published a profile of me focusing on Math for the Rest of Us at http://www.reed.edu/reed_magazine/march2012/articles/alumni_profiles/ash.html. I feel particularly honored because not only do I have great fondness for Reed College, but Reed Magazine is one publication I make a point of reading. The writing is superior to most college alumni magazines I have seen, and the articles describe varied, idiosyncratic work by fascinating people in many intellectual areas.
Toastmaster Project Followup
Sources mentioned in my presentation at Lexington ISBN Toastmasters on February 23:
The Online Encyclopedia of Integer Sequences which allows you to search for previously studied sequences by simply entering the first several numbers of the sequence: http://oeis.org. This is an indispensable resource for mathematicians and math students. You can find out a lot about Alcuin's sequence here.
The paper I used to prepare my presentation was by Donald J Bindner and Martin Erickson. It appeared in the February 2012 American Mathematical Monthly, which can be obtained at JSTOR:
http://www.jstor.org/pss/10.4169/amer.math.monthly.119.02.115
Cost is $12 unless you have a JSTOR subscription for this journal, and you can read the abstract and first page for free. It is very much worth reading for those wanting an in-depth treatment of Alcuin's Sequence.
The Online Encyclopedia of Integer Sequences which allows you to search for previously studied sequences by simply entering the first several numbers of the sequence: http://oeis.org. This is an indispensable resource for mathematicians and math students. You can find out a lot about Alcuin's sequence here.
The paper I used to prepare my presentation was by Donald J Bindner and Martin Erickson. It appeared in the February 2012 American Mathematical Monthly, which can be obtained at JSTOR:
http://www.jstor.org/pss/10.4169/amer.math.monthly.119.02.115
Cost is $12 unless you have a JSTOR subscription for this journal, and you can read the abstract and first page for free. It is very much worth reading for those wanting an in-depth treatment of Alcuin's Sequence.
The Toastmaster Project
I am using a puzzle problem to illustrate the way in which I teach math to adult students who may not have much experience in the subject, which is the purpose of my company, Math for the Rest of Us.
I will introduce the puzzle and some problems related to it in this blog, and then will talk about its solution during the meeting of Lexington (MA) Toastmasters at 12 noon on February 23. (The source of my presentation and information relating to the solution will be listed on the blog after February 23.)
A rich merchant died and left an inheritance to his three sons. The inheritance consisted of 30 identical silver boxes, of which 10 were full of gold, 10 were exactly half-full of gold, and 10 were empty. He instructed that the inheritance be divided equally, so that each of the three sons received the same amount of silver and the same amount of gold. For the purpose of the division, it is impossible to remove any gold from any box. How can the treasure be divided equally?
This puzzle goes back to the early middle ages. Before following the link, try your hand at solving the puzzle. It can be solved by a little trial and error, and some elementary algebra may be helpful.
Subscribe to:
Posts (Atom)
