Thought Provokers to Start a Class With, IV
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.
Let f(n) is the year the brochure #n saw the light of day. E.g., f(1) = f(2) = 2005, f(3) = 2006. Clearly, at the beginning, i.e., for small values of n, n - f(n) < 0. Since, the year count grows by 1 while the brochure count by 2 or 3 a year, sooner or later the brochure count will overtake the year, making the difference n - f(n) positive. The idea is to make sure that the difference may not change from negative to positive without passing (the narrow place of) zero. But, with a publication of a single brochure, the difference changes exactly by 1 - neither more nor less.
The change is not necessarily monotone. The difference n - f(n) grows within any year but decreases by 1 at the beginning of every new year. One needs to convince oneself that this does not invalidate the above argument. The difference n - f(n) is "discretely continuous", meaning that while changing from one of its values to another, it takes up all the intermediate values.
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?
Adjoining 100 to the set makes all the difference in the world. The problem is now solvable as 50 acquires a neighbor - 100. Since it has only 1 neighbor, a possible arrangement of the numbers either starts or ends with 50. What stands at the other end? 51! For, this is the only other number with a single neighbor - 1.
If we start with 50, 100 will have to come next, but what then? The choices seem to be from 49 down; but in fact 49 is the only possibility because it has just two neighbors - 100 and 99 - and, therefore has to be placed between the two. Choosing anything but 49 to follow 100 would prevent 49 from appearing anywhere (remember that, since we started with 50, 51 has to come at the end.)
Thus we have the beginning of the arrangement: 50, 100, 49, 99. The neighborhood of 99 goes from 49 down. 49 having been used, 48 remains the only choice, because its neighborhood now contains only 1 so far unused integer: 98. Thus we continue: 50, 100, 49, 99, 48, 98. The same argument forces the continuation: ...48, 98, 47, 97, 46, 96, ..., 2, 52, 1, 51.
The sequence can be read either forward or backward, showing there are just two solutions to the problem.
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?
Where is the bottleneck? It's the number 13 itself. Had there been 12 numbers the problem would have been solved easily. The 12 numbers are split into four triples with positive sums, making the total also positive.
We may try to avoid the bottleneck by choosing 12 out of 13 numbers that are made of successive triples. This is possible by dropping numbers in positions 1, 4, 7, 10, or 13. Assume the problem is solvable and that in these 5 positions there is a negative number -x while in other positions there is a positive number y. Then we have 8y - 5x < 0 (the total negative) while 2y - x > 0 (the sum of any successive three is positive). This is equivalent to
1.6y < x < 2y.
So, for example, we may take y = 3 and x = 5, or y = 4 and x = 7, etc. Even such solution (with two groups of equal numbers) is far from unique. But the answer to the problem is positive.
Is there an equilateral triangle with vertices at the nodes of a square grid?
What use can be made of a square grid? It is clear that the sides of any grid triangle could be seen to be the hypotenuses of right triangles with the legs on the grid lines. Their length could be found from the Pythagorean theorem. The length could be rational or irrational. Short of attempting to solve the equations resulting of the comparison of the side lengths, little can be said about their simultaneous rationality or irrationality, let along the equality of their lengths. On the other hand, the area of any grid triangle is either integer or an integer and a half. This follows from Pick's theorem or directory via the same model where a grid triangle is obtained from a rectangle by removing right triangles with legs on the grid lines.
On the other hand, the area of an equilateral triangle with side a is √3a²/4. And, since, by the Pythagorean theorem a = √k, for some integer k, such an area is always an irrational number. The are serves an insurmountable bottleneck for the construction.
Related posts: