As I stated, we’ll start with something easy:
We put in a grid. Call two squares adjacent if they touch either on a corner or on a side. Show that there are two adjacent numbers which differ by at least .
Proof and analysis:
Look at 1 and n^2. They differ by at most n-1 steps (where a ‘step’ is a chess King-move), which means their average gap is (n^2 – 1) / (n-1) = n+1 – so at least one step must actually take this value or more.
The concepts are simple – the pigeonhole principle and the “strip away irrelevant information” metatechnique. Being “adjacent” is a weird thing to quantify, but an idea of “distance” is not – so we turn things to “distance.”
I saw the first problem a really long time ago (elementary/middle school?) when I was practicing problem-solving, so I don’t remember exactly where it was from. So I was delighted to see the second problem in Bela Bollobas’s The Art of Mathematics:
We put in a grid. Call two squares adjacent if they touch on a side. Show that there are two adjacent numbers which differ by at least .
Proof and analysis:
For each row and column of n elements, there is a maximum element. Find the smallest of these (possibly overlapping) maximum elements, and call it k. Note that for each other row, there is at least one ‘small’ number less than k (namely the element in its column) but at least one ‘big’ number greater than k (namely the maximal element in that row). Since every number is one of these two types, there exists at least two adjacent numbers in that row where one is ‘small’ and the other is ‘big’.
Since there are n-1 of these pairs, at least one of the pairs must differ by n (this is because at least one number must be less than or equal to (k-n+1), and the smallest ‘big’ number it can pair with is (k+1), which already gives the difference n), so we are done.
This is very elegant, surprisingly nonconstructive, but shows the cool things you can do with seemingly arbitrary combinatorial constructions. Okay, I admit I cheated, since this problem is not “strictly harder” than the first one (it would if we changed “n+1” to “n” in the first problem, which loosens it and doesn’t really change it much). But whatever, let’s stop being picky mathematicians.