CTK Insights

The three angle bisectors of a triangle meet at incenter of the triangle. Reversing the problem we may ask a relevant question:

Given three concurrent lines: α, β, and γ. Is there always a triangle with the three lines as the angle bisectors. If so, construct the triangle.

Solution

Given three concurrent lines: α, β, and γ. Is there always a triangle with the three lines as the angle bisectors. If so, construct the triangle.

Solution

The answer to the question is in positive, and the triangle can be constructed is as follows.

First construct a triangle for which the three lines serve as the altitudes. The orthic triangle of the latter is the one we are after, because of the mirror property the orthic triangles possess.

Obvioiusly, the construction is not unique, what is unique is the shape of the triangles - they all are similar.

The medians of a triangle meet at a point known at the center of the triangle. Reversing the problem we may ask a relevant question:

Given three concurrent lines: α, β, and γ. Is there always a triangle with the three lines as the medians. If so, construct the triangle.

Solution

Given three concurrent lines: α, β, and γ. Is there always a triangle with the three lines as the medians. If so, construct the triangle.

Solution

The answer to the question is in positive, and the triangle can be constructed is as follows.

Pick point A on α, find points B on β and C on γ such that AB is bisected by γ and AC is bisected by β. There is a simple way to achieve that goal. (We already used this construction in finding a parallelogram cross-section of a pyramid.)

In ΔABC, β and γ house two of the medians BB' and CC'. The third median AA' meets them at the center of the triangle and lies, therefore, on α, implying that α bisects BC.

Obvioiusly, the construction is not unique, what is unique is the shape of the triangles - they all are similar.

The altitudes of a triangle concur at a point - the orthocenter of the triangle. There are multitudes of proofs, each shedding light of a different hue on the existence of the orthocenter. Collecting these proofs was an enjoyable undertaking, and edifying, too. Not until a few days ago, when I came across another problem, have I realized that, while diligently searching and documenting the proofs, I was negligent in one aspect of problem solving.

Looking back is the last step of G. Polya's problem solving methodology that is often omitted once a satisfactory solution to a problem had been found.

So, the altitudes of a triangle concur at a point. Let's see what we can do with that problem. Starting literally from the end, assume there are three lines that meet at a point; is there a triangle for which the three lines serve as the altitudes? If so, how to construct such a triangle?

The answer to the first question is positive and one possible construction is based on a solution to a related problem:

Given three concurrent lines: α, β, and γ. From point A on on α drop perpendiculars AB to γ and AC to β, with B on β and C on γ. Prove that BC is perpendicular to α

The existence of the orthocenter shows the way of solving this problem. Indeed, in ΔABC, lines β and γ are the altitudes. The point of their intersection is the orthocenter, which belongs to the third altitude (the one through A) as well. But the line through A and the orthocenter is exactly α; and the problem is solved making the construction clear.

When point A is selected on one side of the common point of α, β, and γ all triangle the construction leads to are similar. What if A is chosen on the other side of α?

No. It seems that three concurrent lines uniquely define a shape of the triangle for which they serve as altitudes. Is that clear? Are there any special cases?

Imagine a pyramid with no symmetries or regularities whatsoever. To construct a pyramid like that, pick a plane, four arbitrary points in the plane and one point outside. The lines (or rays) joining the latter to the four points in the plane serve as the edges of a slanted and likely irregular pyramid. However, the following exercise shows some regularity is still present regardless of how irregular the pyramid may appear.

There are a couple of ways to formulate the problem I have in mind.

1. For a random pyramid built as described above, with the four coplanar points forming a convex quadrilateral, there is always a plane that cuts the pyramid in a parallelogram.

2. Consider a class of pyramids constructed by choosing four coplanar points and joining an extra fifth point not in the same plane to the chosen four. The second class is constructed similarly with a restriction that the four coplanar points form a parallelogram. The fact is that the two classes of pyramids coincide.

Parallelogram is a convex quadrilateral with the opposite side lines parallel. Among several characterizations of parallelogram there is a couple that will help solve the problem:

1. Parallelogram is a convex quadrilateral with a pair of equal and parallel sides.

2. Parallelogram is a quadrilateral in which the diagonals bisect each other.

The three solutions below are each based either on the definition or one of the characterizations of parallelogram.

First lets look into how to get a plane cut parallel lines on two opposite faces of a pyramid. Start with just two faces, i.e., two planes that meet in a line:

A plane that cuts parallel lines on the two faces is necessarily parallel to their line of intersection (otherwise, this is where the two lines would meet). Chose one such plane and rotate it around one of the parallel segments on one of the faces of the pyramid; the segment on the opposite face - while remaining parallel to itself - will change in length from zero (near the apex of the pyramid) to infinity. The change is continuous, so that at some intermediate position the plane will cut to equal segments.

Note that there is a simple planar construction of the segment inscribed into an angle equal and parallel to the given one.

Now it is possible to have a solution based on the definition of parallelogram as a convex quadrilateral with two pairs of parallel sides. The opposite faces of a pyramid meet at two lines through the apex of the pyramid:

This two lines determine a plane such that a plane parallel to the latter cuts parallel lines on both pairs of the opposite faces of the pyramid.

The third solution to the problem is based on the fact that the diagonals in a parallelogram bisect each other. The opposite edges of the pyramid define two planes that meet in a line through the apex of the pyramid:

Focus now on each of the two planes. In each, two edges of the pyramid define an angle with a third ray in-between. The task is to construct a line segment with the end points on the sides of the angle which is divided in half by the middle ray. This is a nice planar problem that admits a simple and instructive solution. Solving two planar problems - one for each of the planes - produces to segments with the end points on the opposite edges of the pyramid that bisect each other and, therefore, define a parallelogram.

In addition to the line-wise properties, parallelogram can be characterized as a convex quadrilateral with the pairs of equal opposite angles. The three forgoing constructions show then how to find a plane that cuts equal angles on two dihedral angles - 3D angles formed by two intersecting planes - that share an apex. I have a difficulty finding a construction of the plane based on this property of parallelogram

Indeed, is it possible to miss the New Year moment? The question is not meant to account for a possible tragic circumstance and is being asked plainly and candidly. Assuming you are in good health on December 31 of one year and remain healthy on January 1 of the next year, is it possible to have missed the New Year moment?

The answer is Yes, and a delightful book Insurmountable Simplicities by Roberto Casati and Achille Varzi, shows how this may happen. Imagine boarding a plane flying from New York to London some time on a New Year's eve, say 10:45 pm. It may so happen that an hour later at 11:45 pm the plane will cross the boundary of a time zone, such that instantaneously you would find yourself in the 00:45 am time zone. Simple? Still curious - the tricks the presence of time zones may play with an uninitiated.

Now that you know the answer to that question, there is another one: Is it possible for two people to be born at exactly same moment in time, but have different birthdays? The answer to this question is also Yes. Imagine one baby born in Los Angeles at 10:30 pm on say, June 1 when in New York it's already 1:30 am, June 2. A baby born at this time in New York will be 1 day younger than the baby born in Los Angeles. In time, they will be eligible for the Social Security benefits one day apart. Talk about social justice.

There are 39 dialogues in the book that illuminate various philosophical conundrums of everyday life. As another example, is the Aral Sea still where it is used to be? Being drained practically of all its water following the grandiose plans of the successive Soviet governments to irrigate the surrounding arid steps, is the sea still around? As a matter of fact, at his point in time, there is no sea over there as there is no water. Until about 50 years ago, the Aral Sea was the fourth largest lake in the world. So, what about that lake? If it is not there any more, has it moved to an ocean? Is it not where it used to be in the same sense as the Bamyian Bhuddas are no longer where they used to be?

This is a fascinating book raising questions that I am going to discuss with my 8th grader boy - easy to understand, not so easy to answer.

It's hard to overestimate the influence Alcuin of York (c. 732-804) had on Western civilization. He also left the earliest known European collection of puzzles, Propositiones alcuini doctoris caroli magni imperatoris ad acuendos juvenes - Propositions by Alcuin Teacher to the Great Emperor Charles to Sharpen up the Young. The collection consists of 53 problems (some of which became classic, like the problem #18 of moving Cabage, Goat, and Wolf to the other shore of a river constrained by a small size boat and unfriendly attitude of the actors toward each other.)

Here I am concerned with problem #12:

A certain father died and left as an inheritance to his three sons 30 glass flasks, of which 10 were full of oil; another 10 were half full, while another 10 were empty. Divide the oil and flasks so that an equal share of the commodities should equally come down to the three sons, both of oil and glass.

David Wells translates Alcuin's own solution:

To each son will come ten flasks as his portion. But divided them as follows; give the first son the ten half-full flasks; then to the second give five full and five empty flasks, and similarly to the third.

Martin Ereckson points out that this is not the only possible solution and asks how many there are. There in fact five distinct solutions, not counting the permutations as distinct. Can you find them?

At a recent dinner I posed this problem to my 8-grader boy. With a twinkle in his eye he immediately suggested to fill five empty flasks with the contents of the ten half-empty ones, making the solution obvious and, in some sense, fairer than other solutions. Not only each of the sons receives equal number of bottles and equal amounts of oil - they receive them in identical packages.

The boy knew that his solution was not what was expected but enjoyed himself on my account. Right away, he proceeded with another solution that was that of Alcuin's. Then, with a little prompting, he came up with the remaining solutions.

You know, I was happy he did not ask that pernicious question, What is it good for? We may speculate that the question occurred to neither Alcuin himself nor to Charlemagne (to whom the problems have been sent occasionally, one at a time, and later collected in a book). After all, Charlemagne made Alcuin his effective Secretary of Education, even though some of the problems have been plain jokes. E.g., #14 reads

An ox ploughs a field all day. How many footprints does he leave in the last furrow.

A joke or not, but the problem has an answer [Wells, p. 203]:

The ox leaves no trace in the last furrow, because he precedes the plough. However many footprints he makes in the earth as he goes forward, the cultivating plough destroys them all as it follows. Thus no footprint is revealed in the last furrow.

Another one (#43) does not require an answer:

A certain man had 300 pigs. He ordered all of them slaughtered in three days, but with an uneven number being killed each day. He wished the same thing to be done with 30 pigs. What odd number of pigs out of 300 or 30 were to be killed in three days? (This ratio is indissoluble and was composed for rebuking.)

Alcuin is not remembered because of his problem book but, ironically, another great - Leonardo of Pisa - who lived 400 years later, has his name immortalized in the connection with a certain puzzle, not the accounting revolution his work engendered. (See, Devlin.)

Nonetheless, in time, some of Alcuin's problems got involved with a good deal of mathematics. The flasks inheritance problem has been extended to a generic "n full, n half-empty, and n empty flasks." The number of solution to each is usually denoted t(n) and the sequence {t(n)} is known as Alcuin's sequence. The sequence satisfies an 8-term recurrence relation and has a nice generating function [Erickson, p. 91]. It comes up as a number of integer triangles with a given perimeter. In [Yaglom & Yaglom, #30], that latter problem is marked with two stars as very difficult.

The transportation problems (of which there are four and of which Cabage, Goat, and Wolf is an example) serve popular examples in integer programming.

Many of Alcuin's problems were too simple to leave any trace in history; most were rather artificial; it is not known whether any were original. This is inspiring, however, to have access to this collection, as it throws - if only a quantum of - light on the life of this great man. Looks like he found amusement in mathematics.

References

1. D. Darling, The Universal Book of Mathematics, Wiley & Sons, 2004
2. K. Devlin, The Man of Numbers: Fibonacci's Arithmetic Revolution, Walker & Company, 2011
3. M. Erickson, Beautiful Mathematics, MAA, 2011
4. D. Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, 1992
5. A. M. Yaglom & I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York, Dover Publications, Inc., 1987

Solition

A solution can be expressed by the number of full flasks received by each son. For example, Alcuin's solution could be expressed as {0, 5, 5}. A triple {1, 4, 5} tells us that the first son receives 1 full flasks, and to make up for the required quantities, 8 half-full and 1 empty flask are added. The second son gets 4 full, 2 half-empty and 4 empty flasks, the last one gets 5 of each full and empty flasks. The other solutions in that form are {2, 3, 5}, {2, 4, 4}, and {3, 3, 4}.

In the Chinese calendar, years are named cyclically after the Chinese zodiac symbols: rat, ox, tiger, rabbit, dragon, snake, horse, sheep, monkey, rooster, dog, pig.

Until 1912 the traditional Chinese calendar was the only one in use. Traditionally, the signs of the zodiac played a more universal role that included, e.g., the designations for time of the day and directions: hour of snake (~10-noon) and dragon-snake (south-east).

By 1950s, the Gregorian calendar was broadly adopted, although the tradional one is still used to mark the holidays, such as the New Year day. This time around, New Year falls on January 23, 2012 and the coming year will be the Year of the Dragon. The dragon in Chinese mythology is characterized as (wikipedia) magnanimous, stately, vigorous, strong, self-assured, proud, noble, direct, dignified, eccentric, intellectual, fiery, passionate, decisive, pioneering, artistic, generous, loyal, wise, not as good as The Rat, humble, imperious, foresighted, demanding, intolerant, peaceful, impetuous, understanding, and blunt.

Victor Gutenmacher has kindly suggested that facing the coming of the year of the Dragon, may provide an opportunity to mention the dragon-like mathematical objects. The article Victor coauthored with N. Vasilyev for the Russian Kvant magazine (with a translated version in Quantum) describes the construction of plane filling dragon curves with paperfolding and the L-systems.

This one Victor describes appropriately as "mama, kid, and papa." It may not be altogether obvious but the curve consists of two identical non-overlapping parts in the manner that many fractals do. Actually, this property of self-similarity (sometimes with sensible distortions) is one of characterizations of fractal sets.

Below is another fractal dragon. This, too, consists of two identical (but smaller) copies of itself. Recursively, each of these is a union of two identical (but smaller) copies of itself, so that the whole set consists of four identical (even smaller) copies of itself. The process of counting the copies may go on and on. The dragon below is seen to be formed by four identical copies, rotated to fit each other's curves.

The shape below, known as the "twin-dragon" - because of the symmetry - is the union of 16 small copies of itself.

Exquisite creatures.

It's a rare pleasure to get a good book ahead of its planned publishing date. In Pursuit of the Traveling Salesman by William Cook that was expected at the beginning of 2012, was delivered yesterday right to my door. My first impression is that this is the sort of a book that are read in one sitting, from cover to cover. The book is clearly intended for the "general audience" and is sweetly written. The author has an obvious writer's streak.

The book narrates the history of the so called "Traveling Salesman Problem", TSP for short. Occasionally (and rather suitably for Christmas time) it is also known as the Santa Claus Problem. In its TSP incarnation, the problem is to find the shortest route that passes through a given number of cities. For Santa Claus it may be important to make the planned visits in the shortest time possible. When it comes to drilling points of contact on a printed board or a computer chip, it's crucial - to make the cheaper chips - that the robot arm that drills the holes moves in a shortest possible path.

Here's a portion of such an itinerary on a board

The whole picture is available elsewhere. In fact, the TSP has numerous practical applications of which helping campaigning politicians is the most trifling.

TSP is NP-complete, which makes it of fundamental importance in Computer Sciences. It is natural that finding an optimal route between 10 cities takes less time than finding an optimal route between 100 cities. As a rule, as the input for an algorithm grows in size so do the memory and time requirements needed to execute the algorithm. An algorithm is thought to be good if that dependency is expressed as a polynomial in the size of the problem and bad if the dependency is exponential. "P" in "NP-complete" stands for "Polynomial". "N" stands for "Non-deterministic". How?

This is one thing to solve a problem and another to check whether or not a submitted solution is correct. Problem whose solution can be checked in polynomial time are said to belong to the NP-class. Those whose solution can be found in polynomial time belong to the P-class. Are the two classes the same? If you still do not know that, The Clay Mathematics Institute has announced a $1,000,000 prize for answering this question. The fact that TSP is NP-complete means that the existence of a polynomial time algorithm for its solution will imply N = NP. Every one is welcome to try his or her prowess.

The book In Pursuit of the Traveling Salesman is a first-hand and a first-class introduction into the evolution of TSP, with chapters devoted to related mathematics and algorithmic topics. TSP is really at the heart of much of the research and development of modern computer science, so the author leads the reader through the past and emerging landscape of relevant research up to the very end of the mapped territory. Reading the book looks like an exciting adventure, with the itinerary mapped for the reader by a master story-teller whose work squarely places him in the forefront of the TSP research.

In the words of W. Cook:

I plan to take the reader on a path that goes well beyond basic familiarity of the TSP, moving right up to current theory and state-of-the-art solution machinery.

For more information on TSP, check a dedicated site.

I am not sure who coined the term "The Star of David Theorem" to designate the identities discovered in the early 1970s. There are in fact two of them, both related to the "Star of David" configuration in Pascal triangle

(The diagram is courtesy wikipedia.org.)

The first result discovered by Hoggatt and Hansell in 1971 comes in a round-about way as a corollary of the following

Theorem 1

For $n, m, 0 < n < m , m > 2$, the product of the six binomial coefficients surrounding $m \choose n$ is a perfect integer square.

The proof is a little bit strange in my view so that I reproduce it below:

Proof

The six binomial coefficients are:

${m-1 \choose n-1},{m-1 \choose n},{m \choose n+1},{m+1 \choose n+1},{m+1 \choose n},{m \choose n-1}$

The product is

${m-1 \choose n-1}\times {m-1 \choose n}\times {m \choose n+1}\times {m+1 \choose n+1}\times {m+1 \choose n}\times {m \choose n-1}$

which is equal to

$\big[ \frac{(m-1)!m!(m+1)!}{(m-n-1)!(m-n)!(m-n+1)!} \big]^2$

Since each binomial coefficient is an integer, the product is an integer, and since the square of a rational number is an integer if and only if the rational number is an integer, it follows that the product is an integer square.

Corollary

Each alternate triad of the six binomial coefficients have equal products.

Or, formally,

${m-1 \choose n-1}\times {m \choose n+1}\times {m+1 \choose n} = {m-1 \choose n}\times {m+1 \choose n+1}\times {m \choose n-1},$

which can be verified directly, since each of the two products equals

$\frac{(m-1)!m!(m+1)!}{(m-n-1)!(m-n)!(m-n+1)!}.$

The round-about derivation may be a curiosity, but I believe that its form led H. W. Gould to a 1972 conjecture which has been proved by Hoggatt and Hillman later that year.

Theorem

$\text{gcd}({m-1 \choose n-1}, {m \choose n+1}, {m+1 \choose n}) = \text{gcd}({m-1 \choose n}, {m+1 \choose n+1}, {m \choose n-1}).$

Both theorems are now known under the moniker of The Star of David Theorem. They were mentioned in the blogosphere here and here.

References

1. H. W. Gould, A New Greatest Common Divisor Property of The Binomial Coefficients, Fibonacci Quarterly 10 (1972), 579–584. (Part 1, Part 2)
2. V. E. Hoggatt, Jr., W. Hansell, "The Hidden Hexagon Squares", Fibonacci Quarterly, Vol. 9, No. 2 (1971), pp. 120, 133. (Part 1)
3. V. E. Hoggatt, Jr., A. P. Hillman, "Proof of Gould's Conjecture on Greatest Common Divisors", Fibonacci Ouarterly. Vol. 10, No. 6 (1972), pp. 565-568. (Part 1, Part 2)

Going through the old issues of the Mathematics Magazine, I have stumbled on the following note by Dawn Lindquist (Vol. 78, No. 3, Jun., 2005, p. 245)

Mathematicians in the market for a car today have many choices. While analytic geometers might be drawn to the Ford Focus and algebraists may assume the Isuzu Axiom is for them, graph theorists would probably still choose a Nissan Pathfinder. For linear drivers, there's the Toyota Matrix, but if its dimensions are too large, the Honda Element is an option. Though the Oldsmobile Delta 88 attracted analysts in the past, Infiniti currently offers them boundless choices.

Alas, my heart is set on a concept car, the Lincoln Lemma, but I'm waiting for them to work out the details.

After a quick search I found that Ford turned its attention to graph theorists with its Edge and to M. Gardner's admirers with the newer Flex. Nissan went after high school geometers with the Cube and broad stratum of undergraduates with the Maxima. KIA's Optima was clearly designated to appeal to the specialists in Calculus of Variations.

While my attention was directed to the mathematical facets of the car market, I could not fail to notice that the automakers minded other theoretical sciences, mostly pondering to physicists. Here's just a short list: Chevrolet' Avalanche, Equinox, Sonic, Spark and Volt; Dodge's Charger, Dart, and Nitro; Ford's Fusion; Jeep's Compass; Mitsubishi's Eclipse; Suzuki's Equator, not to mention the electric Tesla, with 0 tail-pipe emission.

I leave it to scientists in other fields to check for themselves popularity of their subjects among the automakers.