CTK Insights

26 Apr

Not too easy - not too difficult

The other day, while driving my HS senior son to school (he could have taken a bus, but, for one, his time is at a premium; also, the drive gives us an opportunity for a small chat), we talked about how words with different basic meanings may mean the same thing in certain contexts. As an example I mentioned the expressions "not too late" and "not too early" both of which may mean "just in time." This conversation came to mind when I tried to characterize Problem #1 from the European Girls’ Math Olympiad which Mike Lawler posted on his recent blog:

Let n be an odd positive integer, and let x_1,x_2,\ldots,x_n be non-negative real numbers. Prove that

\displaystyle\qquad\min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2})\le\max_{1,2,\ldots,n}2x_ix_{i+1},

where x_{n+1}=x_1.

At first sight, the inequality appeared strange, if not erroneous because, for every two positive numbers a and b, a^2+b^2\ge 2ab since the latter reduces to (a-b)^2\ge 0.

Assuming, however, that the problem posed a meaningful question, it appears to be essential to take into account the fact that n was an odd number. This leads to the assumption that n\ge 3. The moment that the magnitude of n came into the picture, the mathematical induction seemed like the one venue to follow to crack the problem.

To start with, suppose there are three non-negative real numbers a,b,c, listed in that order, and that a^2+b^2\le b^2+c^2 and a^2+b^2\le c^2+a^2. These imply a\le c and b\le c. Without loss of generality, a\le b\le c. Then, obviously, bc is the maximum of the three products. We need to show that a^2+b^2\le 2bc. This follows from a^2+b^2\le 2b^2\le 2bc.

Now, the intuition for the inductive step: in passing from n to n+2 the maximum on the right may only grow, whereas the minimum on the left may only decrease. This is naturally also true in passing from n to n+1 such that the requirement that n is odd may be a red herring, only stipulated as a disguised substitute for n\ge 3.

Well, trying to implement the induction I ran into one essential difficulty: increasing n not only leads to additional terms among which to choose maximum or minimum, it also causes the terms x_n^2+x_1^2 and 2x_nx_1 to be dropped from consideration. If neither \displaystyle x_n^2+x_1^2=\min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2}) nor \displaystyle2x_nx_1=\max_{1,2,\ldots,n}2x_ix_{i+1} the underlying intuition worked just fine but bad things do happen and there was a need to account for the exceptional cases. The bright spot was that the two conditions can't complicate the proof simultaneously. If, for example, \displaystyle x_n^2+x_1^2=\min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2}) then, in particular x_n^2+x_1^2\le x_1^2+x_2^2, implying x_n\le x_2 and, subsequently, 2x_nx_1\le 2x_1x_2 so that the removal of 2x_nx_1 could not affect the maximum on the right. Similarly, if \displaystyle2x_nx_1=\max_{1,2,\ldots,n}2x_ix_{i+1} then x_n\ge x_2 from which x_n^2+x_1^2\ge x_1^2+x_2^2 and so the removal of x_n^2+x_1^2 would have no effect on \displaystyle \min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2}).

Beyond this, I had to consider several cases of where the dropped terms were smaller or greater of the added ones. I sought to simplify the situation and make it more formal. To this end, I replaced each number in the sequence x_1,x_2,\ldots,x_n with 0 or 1. When x_i\le x_{i+1} I replaced x_i with 0; otherwise it became 1. (Of course x_{n} was followed by x_1.) Now I had a sequence of 0's and 1's. From the base of my attempted induction it transpired that "good" sequences (i.e., the sequences that satisfied the required inequality) were reducing to sequences that contain at least two consecutive 0s or two consecutive 1s. The question became to insert one or two digits and to verify that, starting with a good sequence, the insertion would always lead to a "good" sequence.

This process made it obvious that my attempt at induction was misguided. Clearly, some insertions will work but others will not. For example, inserting 1 between two zeros is liable to cause damage to the sequence unless the two zeros were a part of a triple 000. If it was not, i.e., if we attempted to insert 1 between the two zeros in 1001, we'd get 10101.

So what now? That stumbling step still had a positive effect: it led to a realization of what is a "bad" sequence. A bad sequence is the one that has no consecutive 1s or 0s. In other words, it's an intermittent sequence of 1s and 0s. I should have thought of this sooner without losing that much time. The idea of a bad sequence has highlighted another of my missteps. The fact is that for n even there are bad sequences: 010101\ldots 1 while, for n odd, all sequences are good, for, in a bad sequence every 0 may be paired with a preceding 1 which makes its length even. Thus the induction from n to n+1 did not have a chance to succeed. It also proved to be altogether unnecessary due to a simple statement:

For n odd, all sequences of 1s and 0s are good.

The required inequality holds for any sequence that reduces to a good one, i.e., for any sequence of odd length. Woof.

13 Apr

7 or 22

"Have you guessed the riddle yet?" the Hatter said, turning to Alice again.

"No, I give it up," Alice replied. "What's the answer?"

"I haven't the slightest idea," said the Hatter.

L. Carroll, Alice's Adventures in Wonderland


I have an instinctive dislike for the kind of questions that appear regularly on various forums and social networks. Here's an example that was posted at the CutTheKnotMath facebook page:

a hateful problem

Without ever trying to answer such questions, I was always confident that the poster (if not the author) were smugly awaiting a definite reply, although, even with the most benevolent interpretation, the problem has to be considered ill-posed, like that of asserting the next term in a given sequence.

The question being posted at the CutTheKnotMath facebook page, I gave it some thought. The anticipated answer was likely to be

Since (3+4=\;) 19 = 3 + 4 + 3\cdot 4 and (5+6=\;) 41 = 5 + 6 + 5\cdot 6, then (1+3=) 1+3+1\cdot 3=7.

Obviously, the author expected an algorithmic procedure (a formula most likely) that when applied to 3 and 4 led to 19 but when applied to 5 and 6 produced 41. That algorithm had then to be applied to the pair 1,3.

Bui Quang Tuan offered a different interpretation and wondered which is more natural:

1 + 3 = (5 + 6)-(3 + 4) = 41-19 = 22

That was an interesting approach to a question, most certainly overlooked by the author. (While the latter used the symbol of addition just to suggest a presence of an algorithm, Bui Quang Tuan cleverly accepted the two given identities as such and applied to them the regular operations of addition and subtraction. But even choosing a more orthodox interpretation, an algorithm that would bewilder the problem's author is not difficult to find.

Let's agree to denote the algorithm as a function of two variables. E.g., the above cold be described as f(x,y)=x+y+x\cdot y with the common meaning of arithmetic operations. But here's another possibility: g(x,y)=x\cdot y+y+y-x/x, such that g(3,4)=19 and g(5,6)=41. With this interpretation 1+3=g(1,3)=1\cdot 3+3+3-1/1=8.

Vu Xuan Hanh posted another example: h(x,y)=x+y\cdot y. Indeed, h(3,4)=3+4\cdot 4=19 and h(5,6)=5+6\cdot 6=41, implying that 1+3=h(1,3)=1+3\cdot 3=10.

The latter example has caused a shift in my view of the problem. Perhaps, it is less like finding the next term of a sequence than expressing various integers with a fixed set of numbers using various arithmetic operations. For example, if the task is to place the symbols of arithmetic operations of parentheses between the digits 624663 so as to get, say, 20 as the result, we get the possibilities: 6\cdot 2+4+6+6/3=20, (6-2)\cdot 4+6/6+3=20, -(6-2)/(4-6)+6\cdot 3=20, 6-2+4+6\cdot 6/3. There bound to be more.

Why do I prefer the latter kind of problems to the one I considered at the beginning? The difference between them is in the veil of mystery with which one is presented. There is always an implicit stipulation that somehow the problem has a unique solution. It often comes with an enticing warning "99% of the population can't do that right. Can you?" But, obviously, it would be a rare circumstance where the problem of this kind has a unique solution. With this realization, the problem becomes less obnoxious and can be looked at from other angles. For example,

  1. Find several formulas f(x,y) for which f(3,4)=19 and f(5,6)=41. See what is f(1,3).
  2. For a given formula f(x,y) such that f(3,4)=19 and f(5,6)=41, find which other integers can be represented as f(x,y).
  3. For which integers n there are a,\; b,\; and f(x,y), such that f(3,4)=19, f(5,6)=41, and f(a,b)=n.
  4. Are there integers n provably not expressible as f(x,y), where f(3,4)=19, f(5,6)=41, perhaps for a given f.
04 Apr

Weekly report, the week of March 28, 2016

The week started with Gregoire Nicollier's posting where he applied his beautiful theory of spectral decomposition of polygons to quadrilaterals. I added a GeoGebra illustration to make the theory more accessible, not that it needed that.
Spectral decomposition of quadrilaterals

Gregoire showed how his theory supplied one-line proofs to the problems considered in the previous week: squares on the sides of a parallelogram and squares on the sides of an arbitrary quadrilateral. The whole episode serves a signal example of the unifying, illuminating power of general theory.

Next came a posting about emergence of a parallelogram in a trapezoid, with one sides passing through the apex of an isosceles triangle with the base the opposite side of the trapezoid. The problem, especially when furnished with an illustration, appeared quite intuitively simple. However, several remarks made online by the visitors showed that the intuition alone may be quite misleading.

Parallelogram in trapezoid

One solution employed analytic geometry, another disguised indirect reasoning based on the uniqueness of the solution to the famous Heron's problem. But the third solution stemmed from the observation (by Gregoire Nicollier) that the whole configuration is just a special case of Pappus' theorem.

On April 1st I indulged myself in a doodling with a problem that appeared to beg for a generalization and seemed to hold a promise of a non-trivial result. I am afraid that the promise remained illusionary. But the weekend brought a very satisfying compensation.

Leo Giugiuc and Dan Sitaru shared on the CutTheKnotMath facebok page an elementary problem from their article at the Gazeta Matematica.

An inequality from Gazeta Matematica

The purpose of the article was to introduce an application of Linear Algebra to proving various inequalities. The one they posted at the facebook was the simplest example of such an application. The posting engendered a stream of responses with elementary solutions. As of this writing, ten different proofs have been added to their original one. The present collection supplies a perfect illustration to the fact that even the most simplest of the problems may be looked at from various angles. I wish that the authors of school textbooks that often include only answers or "solutions to the odd-numbered problems" paid more attention to the possibility of alternative view points.

01 Apr

Doodling on April 1st

I came across the following problem several days ago but hesitated to write about it until April 1st. It is simple, practically trivial, and still, after doodling with it for some time, I was left with an open question. If it appears too trivial, even unworthy of mention, do please make an allowance for the date, selected in the hope of forgiveness.

Here's the problem:

Given that (1+\sin\alpha)(1+\sin\beta)(1+\sin\gamma)=\cos\alpha\cos\beta\cos\gamma. Find an alternative expression for

\qquad(1-\sin\alpha)(1-\sin\beta)(1-\sin\gamma).

Do give it a thought before reading further.

To be on safe side, assume that none of the factors (1-\sin\alpha), (1-\sin\beta), (1-\sin\gamma) vanishes, for, otherwise, 0 would be an alternative form. Under this assumption, we may multiply (1+\sin\alpha)(1+\sin\beta)(1+\sin\gamma)=\cos\alpha\cos\beta\cos\gamma by (1-\sin\alpha)(1-\sin\beta)(1-\sin\gamma):

\qquad(1-\sin^2\alpha)(1-\sin^2\beta)(1-\sin^2\gamma)=\cos\alpha\cos\beta\cos\gamma(1-\sin\alpha)(1-\sin\beta)(1-\sin\gamma)

or (\cos^2\alpha)(\cos^2\beta)(\cos^2\gamma)=\cos\alpha\cos\beta\cos\gamma(1-\sin\alpha)(1-\sin\beta)(1-\sin\gamma) and, assuming \cos\alpha\cos\beta\cos\gamma\ne 0, we obtain

\qquad(1-\sin\alpha)(1-\sin\beta)(1-\sin\gamma)=\cos\alpha\cos\beta\cos\gamma.

So, under the assumption \cos\alpha\cos\beta\cos\gamma\ne 0, that product is equal to both (1+\sin\alpha)(1+\sin\beta)(1+\sin\gamma) and (1-\sin\alpha)(1-\sin\beta)(1-\sin\gamma). Clearly the angles must be special.

First, the problem is generalized in an obvious way: Assuming \displaystyle\prod_{i=1}^{n}\cos\alpha_i\ne 0, that product is equal to both \displaystyle\prod_{i=1}^{n}(1-\sin\alpha_i) and \displaystyle\prod_{i=1}^{n}(1+\sin\alpha_i).

That looks quite right, but for what n? For n=1 there is no product but the question still makes sense: if 1+\sin\alpha=\cos\alpha and \cos\alpha\ne 0, what is 1-\sin\alpha? As before, 1+\sin\alpha=\cos\alpha=1-\sin\alpha. The two equations give \sin\alpha=0 and \cos\alpha=1.

Next, consider the case n=2: \cos\alpha\cos\beta\ne 0 and (1+\sin\alpha)(1+\sin\beta)=\cos\alpha\cos\beta. In this case, (1-\sin\alpha)(1-\sin\beta)=\cos\alpha\cos\beta. The difference of the two equations 2(\sin\alpha+\sin\beta)=0 and we get \displaystyle\sin\frac{\alpha+\beta}{2}\cos\frac{\alpha-\beta}{2}=0, meaning \alpha+\beta=2\pi k, k an integer, or \alpha-\beta=\pi (2k+1). Thus we see that, for example, \alpha=-\beta is a suitable pair of angles. The given equation becomes 1-\sin^2\alpha=\cos^2\alpha which is true.

For n=3, we obtain the equation

\qquad\sin\alpha+\sin\beta+\sin\gamma+\sin\alpha\sin\beta\sin\gamma=0.

With the choce of, say, \alpha=0, we reduce the problem to the case of n=2. Are there other solutions that bind all three variables? There bound to be. For example, suppose \alpha+\beta+\gamma=\pi. Then \sin 2\alpha+\sin 2\beta+\sin 2\gamma=4\sin\alpha\sin\beta\sin\gamma, meaning that, for \alpha+\beta+\gamma=2\pi, \displaystyle\sin \alpha+\sin \beta+\sin\gamma=4\sin\frac{\alpha}{2}\sin\frac{\beta}{2}\sin\frac{\gamma}{2}, which converts our equation to

\qquad 4\sin\frac{\alpha}{2}\sin\frac{\beta}{2}\sin\frac{\gamma}{2}+\sin\alpha\sin\beta\sin\gamma=0

or, via the double argument formulas, and assuming that none of the sines vanishes,

\qquad\cos\frac{\alpha}{2}\cos\frac{\beta}{2}\cos\frac{\gamma}{2}=-\frac{1}{2}.

A solution is plausible; I'll have to look into that later on.

Now, for the general case, \displaystyle\prod_{i=1}^{n}(1+\sin\alpha_i)=\prod_{i=1}^{n}\cos\alpha_i, with the latter not being 0.

Immediately, there are special values of \alpha\text{'s}, for which our derivation will work. For example we may split all factors into single angle expressions or pair up some angles and solve equations with one or two variables. Let's call such sets of angles reducible. In general, for a given n, the set \{\alpha_i\},\,i=1,\ldots,n is said to be reducible if it may be split into two non-empty sets, say, I_1 and I_2 such that I_1\cup I_2=\{1,\ldots,n\} and \displaystyle\prod_{i\in I_1}(1+\sin\alpha_i)=\prod_{i\in I_1}\cos\alpha_i=\prod_{i\in I_1}(1-\sin\alpha_i) and \displaystyle\prod_{i\in I_2}(1+\sin\alpha_i)=\prod_{i\in I_2}\cos\alpha_i=\prod_{i\in I_2}(1-\sin\alpha_i).

The original problem did not require solving equations, however, the question for which angles the stipulation of the problem made sense, was reasonable and natural. So lets call such sets of angles "solutions." In this terminology, we just defined "reducible solutions." Thus the questions pops up, "Are there irreducible solutions?"

For n=2, \alpha=\beta=0 should be considered "reducible" but, say, \displaystyle\alpha=-\beta=\frac{\pi}{4} is "irreducible". Thus the question of the existence of the irreducible solutions for n\gt 2 appears quite legitimate: "Are there irreducible solutions?" If that is too difficult, we may try answering an easier question: "Assuming all solutions are reducible, in how many ways the problem may be reduced?"

27 Mar

Weekly report, March 21-27, 2016

This week a discussion on tweeter, brought to mind a quote by Underwood Dudley I used years ago

Can you recall why you fell in love with mathematics? It was not, I think, because of its usefulness in controlling inventories. Was it not because of the delight, the feeling of power and satisfaction it gave; the theorems that inspired awe, or jubilation, or amazement; the wonder and glory of what I think is the human race's supreme intellectual achievement? Mathematics is more important than jobs. It transcends them, it does not need them.

Is mathematics necessary? No. But it is sufficient.

With nine pages - solved problems and proved math statements - added to my site this week, I truly have a very good reason to mention that quote.

In the prior week, Galina Gavrilenko - a Russian mathematics teacher -has informed me of a theorem that she discovered, and that long searches on the web made her believe that the theorem was new.

Let similarly oriented squares ABGH, BCIJ, CDKL, and ADEF be erected on the sides of a parallelogram ABCD. Assume U,V,W,Z are the midpoints of segments FH, GJ, IL, and KE, respectively.

Squares on the sides of a parallelogram

Prove that the quadrilateral UVWZ is a square.

The theorem was obviously related to a few well-known and popular results in geometry: Finsler-Hadwiger theorem, van Aubel's theorem, Vecten's configuration, Thebault's first problem. With such a variety of possible connections, it seemed rather implausible that the statement has been overlooked so far. But my web searches also failed to find a precedent. With that, I set out to prove that theorem, found three simple but independent proofs, with confirmed connections to the better known problems. Finding the proofs was a delight in itself; it was augmented by the realization that, although the connections to the older problems have been really very strong and direct, Galina's discovery was in all likelihood indeed new.

Another enjoyable piece of mathematics has been supplied by Miguel Ochoa Sanchez from Peru.

AreaInequalityInSquare

He formulated a statement for a square, but his beautiful proof worked equally well for trapezoids. It was a pleasure to come up with this realization. Sometimes problem posers insert into their formulations unnecessary details that may obscure the real focus of the problem. These are commonly referred to as red herrings. Miguel is a great inventor of geometric problems; I am quite confident he chose a more specific configuration because it suggested applicability of analytic methods thus leading away from his wonderfully simple and general geometric argument.

I also received an attractive statement from Teo Lopez Puccio from Argentina - an aspiring student of mathematics. The statement is related to the configuration of arbelos, the shoemaker's knife, made famous yet by Archimedes.

ArbelosMorsels

In the two diagrams, the blue and yellow figures have the same areas, to check which is a simple exercise.

My Romanian correspondents continued the stream of various inequalities. Dorin Marghidanu offered an inequality involving the three altitudes of a triangle:

InequalityInTriangle

Solutions came from Japan (Kunihiko Chikaya); Greece (Vaggelis Stamatiadis); Romania (Dorin Marghidanu's and separately by Leo Giugiuc.) Leo Giugiuc was also a partner with Daniel Sitaru in coming up with another inequality

ApplicationOfSchursInequality2

The two solutions (one by Imad Zak from Lebanon) were both based on the famous and very useful Schur's inequality.

23 Feb

A First Look at "The Population Explosion" Book

book review of Population Explosion
The book in fact has a longer title: The Population Explosion and Other Mathematical Puzzles. The title warrants an observation.

I once wrote of the difference in attitude of mathematicians and puzzlists to solving problems. While, for a puzzlist, solving a problem is a goal in itself, for a mathematician it may serve as a starting point for further investigation, for turning the problem each other way, for trying to generalize, and learn something from. As Murray S. Klamkin once wrote

...small solved and unsolved problems lead to larger solved and unsolved problems which in turn lead to important mathematical results.

At first glance, the author of the book, Dick Hess, is fully justified to refer to the book as a collection of mathematical puzzles. And this is not only because the problems in the book - the puzzles - need some kind of mathematics to be solved successfully, but also because the author exhibits a remarkably "mathematician's attitude" in his approach to generating the puzzles. Many a problem in the book come as modifications of each other or of various better known puzzles. This is pretty uncommon for a puzzle book. Some readers might want to have a greater puzzle variety, but in my view, having problems turned around, seen from different angles, even munched under slightly modified conditions, makes the book a valuable resource not just for puzzle fans, but for teachers of mathematics who may want to introduce their students to problem solving strategies and instill in them the right kind of attitude to problem solving in general.

Here, for example, the opening of Chapter 2, Geometric Puzzles that come as a modification of a well-known geometric conundrum:

Mining on Rigel IV An amazing thing about the planet Rigel IV is that it is a perfectly smooth sphere of radius 4,000 miles. Like the earth it rotates about a north pole so a latitude and longitude system of coordinates referenced to the poles serves to locate positions on Rigel IV just as it does on earth. Three prospectors make the following reports to headquarters.

(a) Prospector A: "From my base camp I faced north and went 1 mile in that direction without turning. Then I went east for 1 mile. I rested for lunch before facing north again and going 1 mile in that direction without turning. Finally, I went west for 1 mile and arrived precisely at my base camp." What are the possible locations for base camp A?

(b) Prospector B: "From my base camp I went 1 mile north; then I went 1 mile east. I next went 1 mile south and, finally, I went 1 mile west and arrived precisely at my base camp:" What are the possible locations for base camp B?

(c) Prospector C: "From my base camp I went 1 mile north; then I went 1 mile east. I next went 1 mile south and, finally, I went 1 mile west and arrived at a point the most distance from my base camp under these conditions." What are the possible locations for base camp C and how far from base camp C does the prospector end up?

Chapter 9 is devoted in its entirety to an enormous number of variations on a single puzzle:

Jeeps in the Desert The problems in this chapter deal with fleets of jeeps in the desert initially located at point A where there is a fuel depot with unlimited fuel supply. All jeeps end up at either point A or at a delivery point B, as far from point A as possible. The jeeps are all identical, can go a unit distance on a tank of fuel and consume fuel at a constant rate per mile. Jeeps may not tow each other or carry more than a tankful of fuel.

One-Way Trip with a Single Jeep Your fleet consists of one jeep, which is trying to get to point B as far away as possible from the depot and finish at point B. It is permitted to cache fuel unattended in the desert for later use.

(a) How far can you get if you may use only 2 tanks of fuel?
(b) How far can you get if you may use only 1.9 tanks of fuel?
(c) How much fuel is required to go 1.33 units of distance?
(d) How far can you get if you may use only 3 tanks of fuel?
(e) How far can you get if you may use only 2.5 tanks of fuel?
(f) How much fuel is required to go 1.5 units of distance?
(g) How much fuel is required to go 2 units of distance?

These are followed with subsections Round trip with a single jeep, One One-Way Trip with Two Jeeps, and so on. The chapter is stretched over five full pages of questions. There are 10 chapters in all: Playful puzzles, Geometric Puzzles, Digital Puzzles, Logical Puzzles, Probability Puzzles, Analytical Puzzles, Physical Puzzles, Trapezoid Puzzles, Jeeps in the Desert, and MathDice Puzzles.

Among the "Analytical puzzles" one caught my eye. Rate Race:

Three cats and a rat are confined to the edges of a tetrahedron. The cats are blind but catch the rat if any cat meets the rat. One cat can travel 1% faster than the rat's top speed and the other two cats can travel 1% faster than half the rat's speed. Devise a strategy for cats to catch the rat.

The essential point in the cats being blind is of course their inability to detect the location of the mouse. Thus, when solving the problem, the reader should assume that the cats also have dysfunctional olfactory and hearing faculties.

The book is titled after Problem 6 The Population Explosion, in the first Chapter:

In March 2015 the estimated population of the earth reached 7.3 billion people. The average pewrson is estimated to occupy a volume of 0.063 m3, s the volume ov the total population is 0.4599 km3.

(a) Model the earth as a sphere with a radius of 6,371 km and spread the volume of people over the surface of the earth in a shell of constant thickness. How thick is the shell?

(b) The population currently grows geometrically at 1.14% a year. How long will it take at this rate for the population to fill a shell one meter thick covering the earth? What will the population be then?

(c) At the 1.14% geometric rate how long will it take and what will the population be to occupy a sphere whose radius is expanding at the speed of light (= 9.4605284 x 1012 km/yr)? Ignore relativistic effects.

The framework of the question is rather unexpected and funny, although I'd prefer comparing the total volume of the population to that of the Grand Canyon than to smearing the people all over the surface of the Earth.

The book is small but offers a rich collection of interesting problems - puzzles, if you will - not requiring math knowledge beyond high, and many middle, school level.

15 Feb

A Problem in Complex Numbers Sets 3 Aside

Kunihiko Chikaya‎ has posted an elegant problem on a facebook page which is a simple exercise in complex numbers that also submits - due to an insightful observation - to a solution with a very little computational effort.

The problem is

Let a,b be complex numbers that satisfy \displaystyle\frac{a}{b}+\frac{b}{a}+1=0.
Find the value of the expression \displaystyle\frac{a^{2016}}{b^{2016}}+\frac{b^{2016}}{a^{2016}}+1.

Denoting \displaystyle x=\frac{a}{b} leads to a quadratic equation x^2+x+1=0, with roots \displaystyle x_{1,2}=-\frac{1}{2}\pm i\frac{\sqrt{3}}{2}=\cos 120^{\circ}\pm i\sin 120^{\circ}. It is now hard to miss the fact that, according to De Moivre's formula, \displaystyle x_{1,2}^3=\cos 360^{\circ}\pm i\sin 360^{\circ}=1. From here, since 2016=3\times 672, \displaystyle\frac{a^{2016}}{b^{2016}}+\frac{b^{2016}}{a^{2016}}+1=1+1+1=3.

However, one solution - submitted by Rozeta Atanasova - obtained the same result without so much as even writing the quadratic equation, let alone solving it. Rozeta Atanasova just observed that (x-1)(x^2+x+1)=x^3-1, immediately implying x^3=1.

This led to the inquiry of answering Kunihiko Chikaya question without solving any equation. Here's one such method. I'd be curious to learn of any other. Algebraically, it takes more steps than that of Rozeta Atanasova, but is still based on a simple insight into the implied properties of the original condition. Let's rewrite it as \displaystyle\frac{a}{b}+\frac{b}{a}=-1. Squaring gives \displaystyle\left(\frac{a}{b}\right)^2+2+\left(\frac{b}{a}\right)^2=1, or \displaystyle\frac{a^2}{b^2}+\frac{b^2}{a^2}=-1. Next,

\displaystyle(-1)(-1)=\left(\frac{a^2}{b^2}+\frac{b^2}{a^2}\right)\left(\frac{a}{b}+\frac{b}{a}\right)=\left(\frac{a^3}{b^3}+\frac{b^3}{a^3}\right)+\left(\frac{a}{b}+\frac{b}{a}\right)=\left(\frac{a^3}{b^3}+\frac{b^3}{a^3}\right)-1, so that \displaystyle\frac{a^3}{b^3}+\frac{b^3}{a^3}=2. The same way, \displaystyle\left(\frac{a^3}{b^3}+\frac{b^3}{a^3}\right)\left(\frac{a^3}{b^3}+\frac{b^3}{a^3}\right)=\left(\frac{a^6}{b^6}+\frac{b^6}{a^6}\right)+\left(\frac{a^3}{b^3}+\frac{b^3}{a^3}\right)=\left(\frac{a^6}{b^6}+\frac{b^6}{a^6}\right)+2=4. Thus \displaystyle\frac{a^6}{b^6}+\frac{b^6}{a^6}=2, and, by induction, \displaystyle\frac{a^{3n}}{b^{3n}}+\frac{b^{3n}}{a^{3n}}=2. It follows that \displaystyle\frac{a^{2016}}{b^{2016}}+\frac{b^{2016}}{a^{2016}}=2, implying 3 as the answer to Kunihiko Chikaya's question.

With other exponents the situation is more involved. For example,

\displaystyle\frac{a^2}{b^2}+\frac{b^2}{a^2}=-1, \displaystyle\frac{a^4}{b^4}+\frac{b^4}{a^4}=-1, \displaystyle\frac{a^6}{b^6}+\frac{b^6}{a^6}=2, \displaystyle\frac{a^8}{b^8}+\frac{b^8}{a^8}=-1, \displaystyle\frac{a^{10}}{b^{10}}+\frac{b^{10}}{a^{10}}=-1, \displaystyle\frac{a^{12}}{b^{12}}+\frac{b^{12}}{a^{12}}=2, etc.

The same behavior is observed for the factors of 5 and 7:

\displaystyle\frac{a^{5n}}{b^{5n}}+\frac{b^{5n}}{a^{5n}}=2, if n is divisible by 3, and \displaystyle\frac{a^{5n}}{b^{5n}}+\frac{b^{5n}}{a^{5n}}=-1, otherwise. And

\displaystyle\frac{a^{7n}}{b^{7n}}+\frac{b^{7n}}{a^{7n}}=2, if n is divisible by 3, and \displaystyle\frac{a^{7n}}{b^{7n}}+\frac{b^{7n}}{a^{7n}}=-1, otherwise. The latter confirms the answer to the original problem.

In general,

x^n+1/x^n=2 or -1, depending on whether n is divisible by 3 or not

Which clearly makes 3 to stand out.

26 May

The Jeweler’s Observation, a look back

Paul Brown, an Australian math teacher and author of Proof, a book that I may characterize as a well-written guided introduction into that most fundamental activity, has brought to my attention a recent post at the Futility Closet blog, The Jeweler’s Observation, which I fully reproduce below:

the-jewelers-observation

Prove that every convex polyhedron has at least two faces with the same number of sides.

The solution is initially hidden but becomes available on a button click:

Consider the face with the largest number of sides. If that face has m sides, then it’s surrounded by m faces. Any face must have at least 3 sides. So altogether in this group we have m + 1 faces, and each face must have between 3 and m sides. At least two faces must have the same number of sides.

From Arthur Engel’s Problem-Solving Strategies, Springer Verlag, 1999.

This example provides nice references to two powerful tools in the arsenal of mathematical problem solving: the Extremal and Pigeonhole Principles. However, that was not the reason I decided to write this blog. One of the most (if not the most) important strategy in problem solving, namely, G. Polya's Looking Back step.

So, looking back at the quote from A. Engel's book, what has been actually proved? From the proof we can extract a stronger assertion than that claimed in the problem. This can be formulated in a couple of equivalent ways. But first note that the convexity of the polyhedron was not absolutely essential and that condition can be weakened. For example, the argument appears to work for any polyhedron in which two faces may only share an entire edge (I am not sure even this is necessary). Thus, thinking of such polyhedrons, the original problem can be so generalized:

  • Every polyhedron has a face with two adjacent faces that have the same number of edges.
  • Every polyhedron has two faces with the same number of edges adjacent to the same face.

On a second look back, what is essential for the proof is the requirement that all faces of the polyhedron be convex polygons. If that condition is not satisfied, there are 3D objects with a "skeleton" formed by straight line segments, and "faces" bounded by these edges, with no two faces having the same number of edges. Can you give an example? (That would be a counterexample to the original claim.) I can think of a 3D object that consists of four pieces that have 3,4,5, and 6- sided faces, the ones with 4 and 5 sides not being convex, or even flat.

01 May

A wrapping surprise

Jim Henle's book "The Proof and the Pudding" that I have recently reviewed contains a good deal of surprises. Across several chapters of the book the author looks into the billiard problem (that is very much like the Two Pails puzzle) and its modifications. One of these involves wrapping a ribbon around a 3D box. Start at a corner and move within one of the faces along the diagonal of that corner. When you hit an edge, just bend the ribbon around the edge to the adjacent face, keeping the same angle (45^{\circ}). Here's an example with an incredible box of dimensions \sqrt{2}\times e\times\pi:

Capture

Can you figure out how that path will proceed? In a 2D billiard with the crazy dimensions like \sqrt{2} or \pi, the path will circle without end. Most likely, this is what your intuition may suggest happens in the 3D case at hand. My intuition did. So here comes the first surprise:

Capture

The path that consists of five legs ends up right at the corner where it started. There is an easy explanation why this is so. As in the study of the regular billiard, we may - instead of bending around an edge - flatten two adjacent faces of the cube and let the path pass on a straight line:

Capture

The sequence of five successive face traversals snugly fit into a square of size \sqrt{2}+e+\pi, with the (image of the) path going from one corner of the square to its opposite along the diagonal. Note one face outside the square not touched by the path.

Now, that you may think that you understand and can explain why the path returns to the starting corner, consider wrapping exactly same box but starting in a different face. Before, our first leg lay in a \sqrt{2}\times\pi face. Now, let's start within a \sqrt{2}\times e face. Can you predict what will happen to the path?

Capture

As you may surmise, the path will behave - if I may say so - in a more rational way. Given the incommensurate dimensions of the box it was rational to expect an endless path. This is what you get on the second attempt. But there remains a question to ponder: Why was the first path so short? Jim Henle leaves it to his readers to find the answer. So do I, though I'd like to suggest also starting the wrapping in the e\times\pi face.

02 Apr

An impossible building, at least this is how it looks

I had very little time driving through Newark, NJ when I caught the sight of the Panasonic building:

Small

It absolutely appears an impossible structure that reminded me of an old applet Structural Constellation one example of which you can see below:

StructuralConstellation

I'll have to visit this place again to learn what creates the illusion.

© 2016 CTK Insights | Entries (RSS) and Comments (RSS)

Powered by Wordpress, design by Web4 Sudoku, based on Pinkline by GPS Gazette