Bounding the Answer
Idea · Intermediate
Problem Solving
When finding a minimum, maximum, or extremal value, think of the answer as lying in a range.
Proof → establish a bound.
Example → attain a bound.
Improve both bounds until they become equal.
What is the maximum number of integers that can be selected from
such that no two selected integers differ by 8?
Group the numbers
From each group we can select at most one element, so
We need to find a good example.
This example has 8 + 8 = 16 elements, so
By (1), (2)
On an 8 × 8 grid, some squares are marked, with no square marked more than once. What is the greatest possible number of marked squares if each row, each column, and each of the two main diagonals contains at most 5 marked squares?
Let N be the number of marked squares.
Since each of the 8 rows contains at most 5 marked squares,
It remains to show that 40 can actually be attained.
Therefore,
By (1), (2)