Prove that there is a number that appears at least N times

Question

An $N \times N$ table is filled with integers such that numbers in cells that share a side differ by at most 1. Prove that there is some number that appears in the table at least N times.

An example:

In the example the numbers 1 and 2 both appear at least 5 times.

I think this has something to do with the pigeon-hole principle. If you set one of the center most cells to 0.

In odd $N$ cases, the integers in all the other cells can vary between $[-n+1,+n-1]$.

In even $N$ cases, the integers in all the other cells can vary between $[-n,n]$.

In either case you can only show that some number appears at least $n/2$ times. It might also be induction, but I don't really know how to apply induction to this problem.

Answer 1

This question was also asked on Puzzling Stack Exchange: link. This answer is paraphrased from the top answer there.

The adjacency condition implies that the set of numbers appearing in each row is a contiguous interval of integers, $\{a,a+1,a+2,\dots,b\}$. Let $[a_i,b_i]$ be the interval of numbers appearing in the $i^{th}$ row. Furthermore, let $a_{\max}$ be the maximum value of the $a_i$'s, and let $b_{\min}$ be the minimum of the $b_i$'s.

• If $a_{\max}\le b_{\min}$, then every row contains a number less than or equal to $a_{\max}$, and every row contains a number greater than or equal to $a_\max$, so every row contains $a_\max$.

• If $a_{\max}>b_\min$, then suppose row $i$ is one for which $a_i=a_\max$, and row $j$ is one for which $b_j=b_\min$. Imagine starting in row $i$ in the $k^{th}$ column, and moving vertically to row $j$ in the $k^{th}$ column. You start at a value greater than or equal to $a_\max$, end at a value less than or equal to $b_\min$, so less than $a_\max$, and hit every value in between. Therefore, the $k^{th}$ column contains $a_\max$, so all columns contain $a_\max$.