11 Nov

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.

The problem has a mechanical solution. Imagine a physical configuration which is the polygon with a mass placed at the selected point. If the projection of the point on every side falls outside the polygon, the polygon will rotate in sequence around its vertices - a regular perpetuum mobile - which would be an unthinkable phenomenon. This would go beyond the extreme and is not the reason I gave that example. Here's another solution.

Let point be P, AB the nearest (the extreme!) to P the side of the polygon, C the projection of P on AB. Since P is inside while C outside the polygon, CP crosses a side, say DE, of the polygon in, say, point F. Then CP < CF while, in turn, CF is less than the distance from P to DE. The contradiction proves the assertion.

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 is an impulse to treat this problem as the previous one. But this would not work. First the numbers are real with no smallest element and, besides, there is no "average condition". Nothing could be done about tye latter point. But the former one could be treated if we restrict the consideration to a finite portion of the grid.

Consider a 4×4 square with the corner cells removed. Within this figure, any cell has at least four 8-neighbors. All one needs to solve the problem is to choose the smallest number included in the shape.

2 Responses to “Thought Provokers to Start a Class With, III”

1. 1
Alexey Vorobyov Says:

Maybe I don't correctly understand the problem:
"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."
but I think this statement is wrong.
If you consider g(x, y) = C - A*x^2 - B*y^2 with positive integers A and B, then you can show that
g(x, y) > 1/4*(g(x-1,y) + g(x+1,y)+ g(x,y-1) + g(x,y+1)) = C - A*x^2 - B*y^2 - A/2 - B/2 for all x and y.
I think mistake in your proof is that you forgot to consider cases where m - lies on the border of your subset, so not all of its neighbors are part of the subset.

2. 2