A16. Treasure search

A treasure hunter is on an island which is in the shape of the unit disc, and they are located on the boundary at (1,0). The treasure hunter has a treasure-detector, which will light up if the detector is within 1/2 unit of any buried treasure. The treasure hunter can move along any path (say, continuous and piecewise infinitely differentiable) that starts at (1,0) and stays within the closed unit disk. The treasure hunter claims that they can discover whether or not there is treasure buried on the island (or in other words, that the union of all disks of radius 1/2 centered on points along the path covers the unit disk) by traveling along a path of length π. Prove or disprove the claim.

This is my revision of a problem sent to me by Apratim Roy.

A15. A Problem by Henry Dudeney

The houses on a long street have addresses 1, 2, 3, ... n. (Dudeney was British. Unlike the custom in most of the US, odd and even house numbers in Britain occur on the same side of the street. Assume all houses are on the same side of the street.) Call a house a half-way house if the sum of the numbers of the houses before it are equal to the sum of the numbers of the houses after it. Depending on n, there may or may not be a half-way house. For example, if n = 8, then there is a half-way house, namely 6, because 1 + 2 +3 + 4 + 5 = 7 + 8. You can check there is no half-way house if 1 < n < 8.

Find the value of n if you know that 50 < n < 500 and there is a half-way house.

You could do this easily by a brute-force search with a computer, so to make it interesting, no computer/calculator use is allowed.

I saw this problem presented online by the Mathologer. It connects with many fascinating parts of number theory, and there is an interesting connection with Ramanujan.

A13. Points of tangency of an ellipse and a circle

Let E be the ellipse with equation x²/4 + y² = 1 and C(r) be the circle with center (1,0) and radius r. For which values of r do the curves E and C(r) have point(s) of tangency?

This is fairly routine, but still a bit challenging to find all solutions.

A12. Fifth powers final digit - generalized.

If numbers are expressed in base b, for which b is it true that n⁵ and n end in the same digit for all positive integers n?
This is an obvious generalization of Problem E32.

A11. Splitting a triangle and a tetrahedron

János Kurdics published this interesting problem in The Math Connection Linkedin group:
Given a triangle, find the shortest line segment that divides the triangle into two regions of equal area. A solution that does not involve calculus is preferred.
The solution that I know is very nice, and gives quite a workout in elementary trigonometry.

János says that he is working on three-dimensional analog (plane that divides a tetrahedron into two regions of equal volume and gives smallest possible cross-sectional area with the tetrahedron) but has only solved it for a regular tetrahedron.

A10. Triangle with sides in arithmetic sequence.

Find a number n such that there is a triangle with sides n, n + 1, and n + 2 in which the largest angle is twice the smallest angle. How many such numbers n are there? Note that n does not have to be an integer.

This problem came up in a high school textbook during a tutoring session, except there were several hints given that made the problem much easier. See if you can do it without hints.

A9. Squares erected on a triangle.

Here is a nice problem from Coxeter and Greitzer’s classic book, Geometry Revisited, where an elegant solution is given.

Let ABC be a triangle, and construct squares externally on the sides. Let O₁ be the center of the square on AB, O₂ the center of the square on BC, and O₃ the center of the square on AC, as in the following diagram:

Prove that the segments O₁O₃ and O₂A have the same length and are perpendicular to each other.

A8. Acute triangles with given side lengths

This is a neat problem from last year's Putnam Examination. It was published (with answer given) in the most recent MAA Monthly.

Given 12 real numbers d₁, ... , d₁₂ on the interval (1, 12), show that there exist distinct indices i, j, k such that there is an acute triangle with side lengths d_i, d_j, d_k.

I will post a hint as a comment in a few days.

A7. Comparing areas

In the diagram below, ABCD is a square, DCE is an equilateral triangle, F is the intersection of AE with CD, G is the intersection of BE with CD, IFJ and HGK are perpendicular to CD, and L is on CB so CF = CL. Prove that the area of triangle AFL is equal to the area of rectangle FGKJ.

Sangaku, Harold Jacobs, and Geometer's Sketchpad

As I mentioned at the time, I delivered a talk at the New England Section of the Mathematical Association of America meeting in Bridgewater, Massachusetts, in November. I decided that it would be good to make the talk available online. The talk was about my adventures in trying to prove a difficult theorem mentioned in Harold Jacobs' Geometry. After finding a proof with the aid of Geometer's Sketchpad I happened to discover through Wikipedia that the theorem has a name: The Japanese Theorem For Quadrilaterals. Then Peter Renz, one of Jacobs' editors, suggested I look at the book Sacred Geometry: Japanese Temple Geometry by Fukagawa Hidetoshi and Tony Rothman, which allowed me to place the theorem in a rich cultural and mathematical context.

The talk is at http://www.scribd.com/doc/129968316/NES-MAA-Presentation. This consists of the slides that I used, put in portrait page orientation, but otherwise unchanged. It is a bit terse, but I hope some find it interesting.

A Sangaku Problem

I will be giving a talk Saturday at the NES-MAA meeting in Bridgewater MA in which I will talk about sangaku, or Japanese temple geometry problems. These problems, created by people from a wide walk of life, were beautifully drawn on wooden tablets which were then placed in Buddhist temples or Shinto shrines. Hundreds have been discovered, and probably thousands existed at one time. I became involved in this when I was challenged to solve one of the difficult sangaku. Here I present one of the easier ones, from the delightful book Sacred Geometry: Japanese Temple Geometry by Fukagawa Hidetoshi and Tony Rothman.

I chose this problem because the diagram is so beautiful, the solution is fairly simple, yet satisfying, and it is one of the few sangaku created by a woman (Okuda Tsume).

In a circle of diameter AB = 2R, draw two arcs of radius R with centers A and B respectively, and 10 inscribed circles, two green circles of diameter R, four red circles of radius t, and four blue circles of radius t'. Show that t = t' = R/6.

In the diagram below, we follow the convention of labeling the center of a circle with the radius of that circle.

A6. Counting Triangulations

Here is a counting problem that was solved a long time ago. Feel free to try your hand at it.

Given P, a convex n-gon, a triangulation of P is a subdivision of P into n - 2 non-overlapping triangles. A triangulation is obtained by drawing n - 3 non-intersecting diagonals. Let f(n) be the number of different triangulations. Clearly, f(3) = 1, f(4) = 2, and f(5) = 5. Careful counting shows f(6) = 14. Find an expression for f(n).

A4. Five Circles Theorem

Harold Jacobs presents the fascinating Five Circles Theorem on page 568 of his excellent high school text: Geometry: Seeing, Doing, Understanding (3rd ed.). It states if one starts with a cyclic quadrilateral ABCD, draws the diagonals AC and BD, inscribes a circle in each of the 4 triangles produced, and connects the centers of these circles, then the quadrilateral EFGH produced is a rectangle!

Peter Renz, an editor of Jacobs, called this theorem to my attention and mentioned that the proof that Jacobs gives in the Teacher's Guide uses transformational geometry. He asked if I could find a more elementary proof.

I struggled a bit with this, but finally came up a proof which I have posted at http://www.scribd.com/doc/98720253. I found the Geometer's Sketchpad computer program to be invaluable in helping me discovering geometric truths which I was able to prove and put together to create the proof.

If you are good at geometry, you may want to see if you can come up with a proof on your own.

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.

More on Ordering a Multiset

I posed problem A3, to find a formula for the k-th largest element of an n-element multiset A. I found a very interesting formula that is unknown to several famous combinatorists, including Donald Knuth, and I have submitted a problem to the MAA Monthly Problems section which asks for the solution that I found, a linear combination of certain symmetric functions. However, Knuth told me that there is a simpler known formula of a different type. Knuth's formula is

min(max_k)

where (max_k) is a set of C(n,k) numbers, each of which is the maximum of a different subset of A of size k.

Pretty cute!

A3. Ordering a multiset

Given a multiset of real numbers {a₁, ...,a_n} find expressions e₁, ...,e_n such that {a₁, ...,a_n} = {e₁, ...,e_n}, and {e_i} is a non-increasing sequence, where each expression is formed from the a_i, the max function, and elementary arithmetic operations.
I will not post the answer to this problem, because I plan to publish it if it is not already known. If it is a known result, I would appreciate a reference.

Freeman Dyson's Problem

My friend John Lamperti turned my attention to a number theory problem in an article on Freeman Dyson in the March 29 New York Times Magazine Section. It is an excellent article, which I recommend. The section with the problem is the following:

[T]aking problems to Dyson is something of a parlor trick. A group of scientists will be sitting around the cafeteria, and one will idly wonder if there is an integer where, if you take its last digit and move it to the front, turning, say, 112 to 211, it’s possible to exactly double the value. Dyson will immediately say, “Oh, that’s not difficult,” allow two short beats to pass and then add, “but of course the smallest such number is 18 digits long.” When this happened one day at lunch, William Press remembers, “the table fell silent; nobody had the slightest idea how Freeman could have known such a fact or, even more terrifying, could have derived it in his head in about two seconds.” The meal then ended with men who tend to be described with words like “brilliant,” “Nobel” and “MacArthur” quietly retreating to their offices to work out what Dyson just knew.

The discovery (or proof) of the smallest such number, 105263157894736842, makes a good problem for an elementary number theory course or a bright high school student.

The first time John told me the problem, he had heard it second-hand, and it was backwards: Is there an integer which if you take its first digit and move it to the back you can exactly double the value? In this case the answer is no, and the proof is simpler than the solution for Dyson’s problem.

To see my solutions, go here.

A2. A Trip Around Antarctica

I found this neat problem in Peter Winkler's excellent book, Mathematical Puzzles: A Connoisseur's Collection. I've dressed it up a little.

You have planned an expedition to travel in a 8000 mile loop around Antarctica. Your advance team has set up 20 fuel caches along the route, and has distributed 8000 miles worth of fuel among the caches. You know the amount of fuel at each cache, and the amount of fuel required to travel between any two consecutive caches. Prove that, regardless of the spacing of the caches or the amounts of fuel in each cache, you can complete the trip, assuming that you have an infinitely large fuel tank. Determine how to pick a cache you can start from.

(This might be an elementary problem, depending on how you look at it.)

A1. Relative and Absolute Extrema

In finding minima and maxima, first-year calculus students often use the fact that, for a function differentiable on the entire real line, if the function has exactly one relative extremum, that extremum is an absolute extremum. The proof is simple: WLOG, say the function has a relative maximum at a. If a is not an absolute maximum, then there is a point b where f(b) > f(a). Then on the closed interval with endpoints a and b, f has a minimum value. Since the minimum is less than f(a), it is not attained at either a or b, so it is in the open interval, and thus is a relative minimum.

Does the above result generalize to R²? In particular, say f is differentiable on the entire plane, and has a relative maximum at (0,0), and no other relative extrema. Must the function have an absolute maximum at (0,0)? Why or why not?