A problem for the innocent minds

There is a well known problem of finding two points of the same color in the plane all points of which have been colored either red or blue distance 1 unit apart. It is simple but not trivial. This said what about finding two points of different colors under the extra condition that there are points of both colors.

So the problem is this:

The plane is colored in two colors: red and blue. Prove there are always two points of different colors 1 unit apart.

As usual, you are urged to give the problem a thought before looking at the solution.

The plane is colored in two colors: red and blue. Prove there are always two points of different colors 1 unit apart.

I'll give three solutions to the problem.

Solution 1

It's a condition of the problem that there is a pair of points of different colors. Consider any such pair. Draw a sequence of circles of radii 1, 2, 3, ... around each of the points.

Some of these circles are bound to intersect. Pick any point of intersection and join it to the two selected points by straight lines. On these lines mark the points at distance of 1 unit from each other. (These points are provisionally colored yellow.) Moving from, say, red point in steps of 1 unit, consider successive pairs of points. Since the entire stroll starts with a red point and ends with a blue point, the color had to have changed somewhere in-between. This gives you a pair of points 1 unit apart.

Solution 2

Join the two selected points by a straight line and start moving from the red point towards the blue one in steps of 1 unit. Color the provisional points yellow. There may be the case where the distance between the two points is integer. Keep this possibility in mind and consider the other case. On the latter occasion, we won't reach the blue point but get close enough, i.e., at the distance less than 1 unit. Form an isosceles triangle with sides 1 unit and the base joining the blue point to the last of the yellow points.

In both cases, like in Solution 1, we obtain a path from one of the selected points to the other that consists of unit steps. The same reasoning applies.

Solution 3

Consider the sets of all red points and all blue points. Both are not empty and their union covers the plane. There are border points - the points in whose vicinity, however small, there are points from two sets:

So there are always points of different colors at distance less than 1 unit. Join them by an isosceles triangle:

and apply the same reasoning as before.

Remark

There is a story behind the three solutions. When I first came across this problem, I immediately thought about the more popular and better known problem of finding two points of the same color. The problem is solved geometrically with circles and straight line segments. So, perhaps, the memory of that problem has conditioned me to think in these terms. The result was Solution 1 and Solution 2.

Now, last week, while driving my 8th grader to a swim practice, I posed him this problem. This is not the kind of the problem they work on in the honors geometry class. So he was stumped with it. To help him out I suggested that he should pick two points of different colors and consider three cases according as the distance between the points is equal to, less than, or more than 1 unit. He discharged the first case. I helped him with second one by pointing out the possibility of constructing an isosceles triangle. He then announced that this solves the problem because there are always points of different colors as close as we wish. He explained that this happens near any border point between the two monochromatic sets - essentially along the lines of Solution 3.

I was rather surprised that I have not thought about that at the outset. In fact I believe that this is the most natural solution to the problem. I shall never know whether I would have come up with it had it not been of my remembering the other problem. Had I really been conditioned?

Another question is bothering me: seeing how natural it was for my son to talk of sets and borders, may it be more appropriate for him to study elements of topology rather than the more traditional topics in elementary geometry?

Daniel Kahneman's - Thinking, fast and slow - an amazon.com selection as one of "Best Books of 2011" received an inspiring NY Times review by Jim Holt. Thinking, fast and slow is the first of Kahneman's books that I'll be reading on my Android tablet. Kahneman's earlier Judgement under Uncertainty; Choices, Values, and Frames; Heuristics and Biases: The Psychology of Intuitive Judgment; Well-Being: Foundations of Hedonic Psychology are on my shelves in a still more traditional, printed form. Now that I looked at the collection, there are two other books that deservedly stand next to Kahneman's. One is Predictably Irrational: The Hidden Forces That Shape Our Decisions by Dan Ariely and the other Sway: The Irresistible Pull of Irrational Behavior by Ori and Rom Brafman.

Ori and Rom Brafman gathered real-life examples, while Dan Ariely, like Kahneman, weaved a theory based on deliberate experimentation. Both offer a fascinating and edifying read. Below is an sample from Ariely's book that has repercussions on the grading philosophy underlying modern educational systems.

In this experiment, a circle was presented on the left side of a computer screen and a box was presented on the right. The task was to drag the circle, using the computer mouse, onto the square. Once the circle was successfully dragged to the square, it disappeared from the screen and a new circle appeared at the starting point. We asked the participants to drag as many circles as they could, and we measured how many circles they dragged within five minutes. This was our measure of their labor output—the effort that they would put into this task.

How could this setup shed light on social and market exchanges? Some of the participants received five dollars for participating in the short experiment. They were given the money as they walked into the lab; and they were told that at the end of the five minutes, the computer would alert them that the task was done, at which point they were to leave the lab. Because we paid them for their efforts, we expected them to apply market norms to this situation and act accordingly.

Participants in a second group were presented with the same basic instructions and task; but for them the reward was much lower (50 cents in one experiment and 10 cents in the other). Again we expected the participants to apply market norms to this situation and act accordingly.

Finally, we had a third group, to whom we introduced the tasks as a social request. We didn’t offer the participants in this group anything concrete in return for their effort; nor did we mention money. It was merely a favor that we asked of them. We expected these participants to apply social norms to the situation and act accordingly.

How hard did the different groups work? In line with the ethos of market norms, those who received five dollars dragged on average 159 circles, and those who received 50 cents dragged on average 101 circles. As expected, more money caused our participants to be more motivated and work harder (by about 50 percent).

What about the condition with no money? Did this participants work less than the ones who got the low monetary payment—or, in the absence of money, did they apply social norms to the situation and work harder? The results showed that on average they dragged 168 circles, much more than those who were paid 50 cents, and just slightly more than those who were paid five dollars. In other words, our participants worked harder under the nonmonetary social norms than for the almighty buck (OK, 50 cents.)

Recently, I've been reading and solving problems from a Russian publication by A. V. Shapovalov. As is now customary with popular books, in this book too every chapter is preceded by a suggestive epigraph cuing the reader to the content of the chapter. Every chapter in the book contains solved examples and exercises that come without solution. The last chapter consists solely of exercises. Appropriately and meaningfully the epigraph to the chapter poses an inquiry

So you broke the wall with your head. But what are you going to do in the next room?

The credit for that is given to Stanisław Jerzy Lec of whom - I am sorry to say - I have not heard before. What I found about Stanisław Jerzy Lec on the web made me realize - and regret - the hole in my education. On the other hand, I was gratified to have surreptitiously discovered the hole and being able to fill it in, if only a little. This blog is an attempt to share my elation at learning about such a remarkable person.

I made an additional web search for a proverb that would express my satisfaction of coming across of new to me information through an activity of my own. (A tap on my shoulder.) The caption of the post is the best approximation to what I've been seeking that came up. The search was for "proverb water stone". Naturally, there were other pieces of ageless world wisdom:

Constant dripping wears away a stone. Chinese Proverbs
Dripping water hollows out a stone. Ovid
The drops of rain make a hole in the stone, not by violence, but by oft falling. Lucretius
You cannot get water out of a stone.
A rolling stone gathers no moss. Pablius Syrus
The rock in the water does not know the pain of the rock in the sun.

Stanisław Jerzy Lec was a master aphorist that, among others, published books of satire and epigrams, at least some of which are in a philosophical league of the ancient classics:

You can close your eyes to reality but not to memories.
A dream will always triumph over reality, once it is given the chance.
In a war of ideas, it is people who get killed.
What keeps us on this globe except force of gravity?
The first condition of immortality is death.
I don't agree with mathematics; the sum total of zeros is a frightening figure.

The Bottleneck Principle

The Bottleneck Principle is a problem-solving strategy according to which it may be useful to look into the circumstances in which the conditions of a problem at hand are either hardly or not at all satisfied. It is different from the Worst-Case Scenario in that the latter looks at the problem as a whole while the former seeks to distinguish between problem's details.

A few examples will make the essence of the Bottleneck Principle strategy clear. (The examples have been adapted from a Russian publication by A. V. Shapovalov.)

A math circle distributes 2-3 problem brochures a year: #1 and #2 in 2005, #3 and ... in 2006, and so on. Assuming the math circle survives and continues in this activity indefinitely, prove that the time will come when the number born by the last published brochure will be equal to the year of its publication.

The bottleneck metaphor applies to that problem almost literally. There are two sets of numbers: one, for which the difference is positive, the other for which it is negative. If we look at the values, there are just the sets of negative and positive differences, with a single (narrow) link of zero between the two.

Is it possible to arrange integers from 1 through 99 in a line so that the difference between any two neighbors (the greater minus the least) is always at least 50?

Each of the numbers can be thought of as having a neighborhood of potential neighbors in a linear arrangement. E.g., the neighbors of 1 range from 51 to 99, the neighbors of two are in the range from 52 to 99, and so on. The neighbors of 99 are all below 50, etc. As the numbers grow from one 1 to 50 or decrease from 99 to 50, their neighborhoods shrink. As a matter of fact, the neighborhood of 50 is empty, which implies a negative solution to the problem.

Is it possible to arrange integers from 1 through 100 in a line so that the difference between any two neighbors (the greater minus the least) is always at least 50?

13 integers are arranged in a row such that the sum of any successive triple is positive. Is it possible that the sum of all 13 is negative?

Is there an equilateral triangle with vertices at the nodes of a square grid?

In the Foreward to the new book by John McCormick, Chris Bishop wrote

Computing is transforming our society in ways that are as profound as the changes wrought by physics and chemistry in the previous two centuries. Indeed, there is hardly an aspect of our lives that hasn't already been influenced, or even revolutionized, by digital technology. Given the importance of computing to the modern society, it is therefore somewhat paradoxical that there is so little awareness of the fundamental concepts that make it all possible. The study of these concepts lies at the heart of the computer science, and this new book by MacCormick is one of the relatively few to present them to a general audience.

Chapter-by-chapter, the book covers search engine indexing, the PageRank algorithm, public key cryptography, error-correcting codes, pattern recognition, data compression, databases. These are followed by a general discussion on the limitations and the mundane performance of computers.

As of this writing, I have looked through the chapters 1, 2, 6, and 7 - mainly because of my recent introduction to the algorithms for compressive sensing. Unfortunately, there is no mention of this new field of computer science research. I am a little disappointed but bear no grudge - the author had to make his choices, and the book is certainly not all inclusive, nor it was supposed to be. As the author puts it his

chief goal was to give readers enough knowledge about the great algorithms that they gain a sense of wonder at some of their ordinary computing tasks - much as an amateur astronomer hasa heightened appreciation of the night sky.

The chapters I read impressed me by their prose - unhurried and very clear. At times, I felt like the author not only shares his knowledge of but also his admiration and pride for the algorithms - those gems of human thought - that accomplish the incredibly hard tasks, all without the public being aware of the feats being committed continuously all around us.

The book is indeed an easy read. References are often made to popular articles in the dailies and periodicals; and so are many recommendations for further reading. If I see one feature that I could consider a shortcoming it is that the author glosses over the fact that in some algorithms mathematics provides the essential tools and insights. Most likely, this was done deliberately in order to keep the book attractive to the broadest swathe of potential readers.

I've been reading an outstanding collection An Invitation to Mathematics edited by D. Schleicher and M. Lackmann. There are 14 contributions by leading mathematicians, each introducing a direction of current mathematical research. The remarkable aspect of all the articles is that they all start at a level that could be appreciated by a curious high school student and then gently lead the reader to the frontiers of the Unknown.

On first reading, one article caught my attention, Small Divisors: Number Theory in Dynamical Systems (pp. 43-54) by J.-C. Yoccoz. The article begins thus:

We discuss dynamical systems with two or more particles, such as two planets orbiting around the sun. If the ratio of their rotation periods, say $\alpha$, is rational, then the planets are in resonance, and the mutual interaction will make the dynamics unstable.

I lived many more years to fondly remember my school days than I ever spent on schooling, but that mention of the resonance caused a knee-jerk reaction as if I still was a teenager. On reading that paragraph, I had a flash recollection of an oft-told (but likely untrue) story of Euler embarrassing the encyclopedist Diderot with a frivolous argument that ended with "...hence God exists." The association was rather exhilarating to let the opportunity pass. In my excitement, I rushed to post a message on twitter, "Two planets around a sun with periods T1 & T2. For T1/T2 rational, interaction gives resonance & unstable. Hence irrational numbers exist."

To me, the existence of irrational numbers required no confirmation beyond the argument with sources in the Pythagorean School. As the reaction to my tweet showed, this view is not universally shared. (It was labeled "creationism" and then denied on the basis of the limitations imposed on measurements by the Heisenberg Uncertainty Principle.) In any event, while it may be entertaining (which it was intended to), the argument was rather shaky. It was set straight for me by Colm Mulcahy (@CardColm) and his astronomer friend Carl Murray (Queen Mary College, Univ of London); I am indebted to them both.

The article goes on to model the motion of a single planet with an iterative process (discrete dynamic system) $z_{n+1}=\lambda z_{n}$, where $\lambda=e^{2\pi\alpha}$, $\alpha$ is real, making $\lambda$ a complex number of unit module. As Eugene Wigner (1963 Nobel Prize in Physics) wrote (among much more consequential observation),

Certainly nothing in our experience suggests the introduction of these quantities (complex numbers).

For $\alpha$ rational, the iterations are periodic, while, for irrational $\alpha$, they are chaotic becoming dense on the circle $|z]=|z_{0}|.$

The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve.

The influence of the second planet is modeled with the introduction of a quadratic term: $z_{n+1}=\lambda z_{n} + z^{2}_{n}$. The behavior of the perturbed system differs much from the unperturbed one. For the rational $\alpha$, the system loses stability: the iterations do not stay close to the origin for any non-zero $z_{0}$. However, for some irrational $\alpha$, viz., those that satisfy certain (Diophantine!) conditions on their proximity to the rational numbers, the system becomes periodic.

All the laws of nature are conditional statements which permit a prediction of some future events on the basis of the knowledge of the present, except that some aspects of the present state of the world, in practice the overwhelming majority of the determinants of the present state of the world, are irrelevant from the point of view of the prediction.

In reality, the planet motions are practically periodic, and the influence the planets exert on each other is often realized as the phenomenon of stable orbital resonance. Bodies involved in an orbital resonance have periods related by rational numbers with small numerators end denominators. Examples are numerous. Jupiter's moons Ganymede, Europa and Io have periods in ratios 4:2:1; the periods of Pluto and Neptune relate as 3:2. In such a configuration the planets periodically disturb each other's trajectory but also undergo mutual trajectory corrections that keep them in stable relation.

On the other hand, the gaps between Saturn's inner moons is believed to be the result of unstable resonance: some moons have been ejected from their trajectories years ago (on the cosmological scale.)

References

1. K. Dombrowski, Rational Numbers Distribution and Resonance, Progress in Physics, v 1, 2005, pp. 65-67

   Oscillating systems, having a peculiarity to change their own parameters because of interactions inside the systems, have a tendency to reach a stable state where the separate oscillators frequencies are interrelated by specific numbers - minima of the rational number density on number line.

2. P. Goldreich, An explanation of the frequent occurrence of commensurable mean motions in the solar system, Monthly Notices of the Royal Astronomical Society, Vol. 130, 1965, pp. 159-181

   We now realize that the orbits of a pair of near-commensurate satellites will still evolve as the tides feed angular momentum from the planet's spin into the satellites' orbits. However, we shall see that the satellites will share this angular momentum between them in just the correct proportion to keep their mean motions near-commensurate.

3. A. E. Roy, M. W. Ovenden, On the occurrence of commensurable mean motions in the solar system, Monthly Notices of the Royal Astronomical Society, Vol. 114, 1954, pp. 232-241

   The present analysis of the actual mean motions in the solar system indicates that, far from orbits with commensurable mean motions being unstable, there is a distinct preference for them.

   Twoo possible interpretations suggest themselves. The observed distribution of orbits may be explained by supposing either that the mechanism of formation of the planets and satellites was such as to favor orbits with commensurable mean motions, or that such orbits are relatively more stable over long periods of time than the neighboring orbits, the planets and satellites thus tending towards commensurable configurations.

The Extreme Principle

The Extreme Principle is a misnamed problem-solving tactic akin to the Worst-Case Scenario often used in combinatorics and computer science. It does not make any claim (like, say, the Pigeonhole Principle) per se, but only suggests that, for some problems, looking into extreme circumstances or elements within the conditions of the problem may be helpful in solving the problem. Below are a few examples where the tactic proves indeed helpful. There are additional examples in The Art and Craft of Problem Solving by P. Zeitz. (One of his examples features a dynamic illustration.) Even more examples can be found in Problem-Solving Strategies by A. Engel.

Four circles are drawn on the sides of a convex quadrilateral as diameters. Prove that together they cover the whole of the quadrilateral.

Let the quadrilateral be ABCD. Assume there is point P that belongs to no circle with diameters AB, BC, CD, and AD. Consider angles APB, BPC, CPD, and DPA. The largest of them is not less than 90° for, otherwise, they would add up to less than 360° (which would make no sense.) If the largest is ∠APB then P lies inside the circle with diameter AB.

In this case, the Extreme Principle works as the Pigeonhole: at least one of the four angles whose average is 360°/4 = 90° is not less than the average.

The next problem could be treated in a similar way.

In a country there is a big number of airports, say, about 100, with a plane in each. At some point, the planes move to the airport nearest to their location. (Assume all distances are different.) Prove that at no airport have landed more than 5 airplanes.

Assume planes from the airports A, B, C, D, E, and F landed on a field P. Of the six angles APB, ..., FPA one is the smallest and thus does not exceed 60°. If that's the case, AF is shorter than at least one of AP or FP.

Among all projections of a point in the interior of a convex polygon onto its sides, at least one is inside the polygon.

Prove that a cube cannot be divided into any number of small cubes of different sizes.

Hint: how could the smallest cube be surrounded by bigger ones?

In every cell of an infinite grid there is written a natural number such that every number is not less than the average of its 4-neighbors. Prove that all numbers are equal.

Any subset of natural numbers has the smallest element. Let m be such a number with the 4-neighbors a, b, c, d. Then, on one hand, m ≥ (a+b+c+d)/4, while, on the other, m ≤ a, ..., m ≤ d. This is only possible when all five numbers are equal. Now, looking at the neighrbors of a, b, c, d, we similarly find that all are equal. Finally, in the grid, there are 4-paths from any cell to any cell. As we see, all the number along any such path are bound to be equal, therefore, all are.

In every cell of an infinite grid there is written a real number. Prove that there is a cell whose number does not exceed at least four of its 8-neighbors.

There are mathematical statements that appear counterintuitive. For example, when it comes to infinities, counterintuitive statements are abundant. At the other extreme, there are statements intuitively obvious that are rather hard to prove. Such, for example, is the famous Jordan Curve Theorem.

Naturally, mathematics does not lack in statements of any intermediate kind. Here is one that is intuitively obvious and admits several simple proofs, one of which (the one below) I judge rather elegant.

Proposition

The perimeter of a convex polygon situated wholly inside another polygon is less than the perimeter of the latter.

Proof

The perimeter of a convex polygon situated wholly inside another polygon is less than the perimeter of the latter.

Proof

Form semibands perpendicular to the sides of the inner polygon:

These semibands cut off the outer polygon pieces whose total length is not greater than its perimeter and is not less than the perimeter of the inner polygon.

This is a beautifully illustrated collection of interviews and biographical etudes of 16 mathematicians of different backgrounds, varied professional interests, diverse level of achievement - all incredibly interesting as human beings. The sixteen interviewees lived and were active in the 1900s, though some are yet alive; the stories throw light - if only in the form of personal perspectives - on many aspects, events and personalities of the 20th century.

Lars Ahlfors came first to the US at the time of the Great Depression (find out how much a Harvard professor was making at the time,) but then at the outset of the WWII felt that his place was at home when his country - Finland - was at war. Towards the end of the war the moods had changed and he and his family were secretly flown to Scotland by the British.

Tom Apostol was the first-born of an immigrant shoemaker father and a mail-order bride. During the Depression his mother took in laundry to help out but also in exchange for piano lessons for him and his sister.

Fast forward to Tom's C.L.E. Moore Instructorship at MIT, he sat on Norman Levinson lecture on differential equation. The first time the room was packed but the lecture was terrible. At the end Levinson made an announcement: "This is probably the clearest lecture you'll hear all year." Next time, only a third of the audience showed up but the lecture was excellent. The first one appeared a subterfuge to get rid of the uninterested students.

In 1967, Tom was invited to be a visiting professor at the University of Athens. When he arrived, there were no classes as the students were on strike. The reason? They wanted to be promoted from year to year even if they had not passed any exams. (They already had daily food allowances, free books, free tuition.) Greece was clearly on a course to the current economic crisis.

The conservative Harold Bacon held a secret of getting through life: trust in God and vote the Democratic ticket.

Tom Banchoff did not hear the word "mathematics" until the high school (it was all "arithemtic" beforehand. I guess no "New Arithmetic" has ever emerged.)

Leon Bankoff was a dentist in Hollywood with occasional practice on zoo inhabitants. His Erdös number was 1.

Now, truth be told, I have not finished the book; I'll be reading it leisurely - as I did so far - in the coming days, perhaps weeks. The book does not appear to be intended or suitable for uninterrupted reading. I'll be keeping it at a shelf within an easy reach. It is an awfully good and entertaining read for the time when one needs quiet and rest. I can imagine that the younger readers may disagree and would devour the book in a single session. Even then, it will do them a lot of good. I heartily recommend the book to a broadly aged audience.

This Is Just Plain Counting

I and many others think it's a good idea to start a math class with a simple non-traditional problem to get the students into the right mood for the class. My main source for the problems below is a Russian booklet by E. G. Kozlova intended for early and middle grades math circles.

The problems are a variation on one of my favorites: breaking chocolate bars. The focus is on the essence of plain counting with a little twist.

A log is sawed into 10 pieces - How many cuts have been made?

In the beginning there was just one piece (the log itself). Every cut adds 1 piece to the count. To get 10 pieces one has to make 9 cuts.

There were several logs to start with. After 10 cuts, there were 16 pieces. How many logs there were at the beginning?

Logic is exactly the same. Every cut adds 1 piece to the count. 10 cuts add 10 pieces. You had to start with 6 logs to end up with 16 pieces after 10 cuts.

For both problems it may be observed that it does not matter which logs or pieces get cut. The only parameter of consequence is the number of cuts.

One of the ends of a log is fixed in a mechanical claw. After 10 cuts, how many pieces will fall to the ground?

1 cut will reduce the problem to that of a free log. The remaining 9 cuts will leave 10 pieces.

Both ends of a log are fixed in mechanical claws. After 10 cuts, how many pieces will fall to the ground?

2 cuts will reduce the problem to that of a free log. The remaining 8 cuts will leave 9 pieces.

The log is rigidly fixed in the middle. After 10 cuts, how many pieces will fall to the ground?

As with a free log, the total number of pieces does not depend on the sequence of cuts: you may cut from either end in any order; the result is always the same. Thus, it is also irrelevant at what point the log is actually fixed - the middle or the end. It follows that the number of pieces that fall on the ground after 10 cuts is 10, with one piece being held fixed.

A sponge cake (with a hole in the middle) was cut with 10 radial cuts, how many pieces are there?

The first cut creates a shape topologically equivalent to a log: one can imagine unbending the cake into one straight piece with two ends. The remaining 9 cuts will result in 10 pieces.