Difference between revisions of "Extreme principle"
(→Problems) |
m (of -> or) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | The extreme principle (or extremal principle) is a problem-solving technique that involves looking at objects with extreme properties, such as the largest or smallest element. | + | The '''extreme principle''' (or extremal principle) is a problem-solving technique that involves looking at objects with extreme properties, such as the largest or smallest element. |
For example, consider the following problem: | For example, consider the following problem: | ||
| − | + | ''Example:'' Imagine an infinite chessboard that contains a positive integer in each square. If the value in each square is equal to the average of its four neighbors to the north, south, west, and east, prove the values in all the squares are equal. | |
| − | + | ''Solution:'' Consider the square containing the minimal value. Then its four neighbors must all have this minimal value. Similarly, their neighbors must also have this minimal value, and so on ad infinitum. | |
Thus, every square in the chessboard has the same value. | Thus, every square in the chessboard has the same value. | ||
==Problems== | ==Problems== | ||
| − | # Suppose you are given a finite set of coins in the plane, all with different diameters. Show that one of the coins is tangent to at most five of the others. ([[Extreme principle/ | + | # Suppose you are given a finite set of coins in the plane, all with different diameters. Show that one of the coins is tangent to at most five of the others. ([[Extreme principle/solutions |Solution]]) |
| − | # A palindrome is a number | + | # A palindrome is a number or word that is the same when read forward and backward, for example, "176671" and "civic." Can the number obtained by writing the numbers from 1 to <math>n</math> in order (for some <math>n > 1</math>) be a palindrome? (Russia, 1996) |
# Place the integers <math>1, 2, 3, \hdots, n^2</math> (without duplication) in any order onto an <math>n \times n</math> chessboard, with one integer per square. Show that there exist two adjacent entries whose difference is at least <math>n + 1</math>. (Adjacent means horizontally or vertically or diagonally adjacent.) | # Place the integers <math>1, 2, 3, \hdots, n^2</math> (without duplication) in any order onto an <math>n \times n</math> chessboard, with one integer per square. Show that there exist two adjacent entries whose difference is at least <math>n + 1</math>. (Adjacent means horizontally or vertically or diagonally adjacent.) | ||
# There are <math>n</math> points in the plane, not all collinear. Prove that there exists a line passing through exactly <math>2</math> points. | # There are <math>n</math> points in the plane, not all collinear. Prove that there exists a line passing through exactly <math>2</math> points. | ||
Latest revision as of 08:58, 3 January 2018
The extreme principle (or extremal principle) is a problem-solving technique that involves looking at objects with extreme properties, such as the largest or smallest element. For example, consider the following problem:
Example: Imagine an infinite chessboard that contains a positive integer in each square. If the value in each square is equal to the average of its four neighbors to the north, south, west, and east, prove the values in all the squares are equal.
Solution: Consider the square containing the minimal value. Then its four neighbors must all have this minimal value. Similarly, their neighbors must also have this minimal value, and so on ad infinitum.
Thus, every square in the chessboard has the same value.
Problems
- Suppose you are given a finite set of coins in the plane, all with different diameters. Show that one of the coins is tangent to at most five of the others. (Solution)
- A palindrome is a number or word that is the same when read forward and backward, for example, "176671" and "civic." Can the number obtained by writing the numbers from 1 to
in order (for some 
) be a palindrome? (Russia, 1996) - Place the integers
(without duplication) in any order onto an 
chessboard, with one integer per square. Show that there exist two adjacent entries whose difference is at least 
. (Adjacent means horizontally or vertically or diagonally adjacent.) - There are points in the plane, not all collinear. Prove that there exists a line passing through exactly
points. - There are blue points and red points in the plane (no 3 are collinear). Prove that there are non-intersecting line segments, each connecting a red point to a blue point (each point is on 1 segment).
- There is a set
of points in the plane with the property that any triangle with vertices in has area at most 1. Prove that there exists a triangle with area 4 containing all the points in . (Korea, 1995) - We are given an
array of real numbers. An operation consists of changing the sign (positive to negative, and vice versa) of all the entries in any row or column. Prove that we can perform a number of such operations such that in the resulting array, the sum of the entries in each row and in each column is nonnegative.
in order (for some 
) be a palindrome? (Russia, 1996)
(without duplication) in any order onto an 
chessboard, with one integer per square. Show that there exist two adjacent entries whose difference is at least 
. (Adjacent means horizontally or vertically or diagonally adjacent.)
points.
of points in the plane with the property that any triangle with vertices in 
array of real numbers. An operation consists of changing the sign (positive to negative, and vice versa) of all the entries in any row or column. Prove that we can perform a number of such operations such that in the resulting array, the sum of the entries in each row and in each column is nonnegative.
