7
$\begingroup$

Suppose we have ${N}\times{N}$ chessboard such that two squares are adjacent if they share a common side. Populate all squares with integer numbers so that numbers in adjacent squares differ by $1, 0$ or $-1$. Prove that some number appears at least N times.

$\endgroup$
  • $\begingroup$ Can we get some context? Where is the question coming form, and how do you know that this statement is true? $\endgroup$ – goblin Apr 27 '17 at 13:16
  • 2
    $\begingroup$ My son (15 years) is preparing for a national math competition :) He has downloaded some training material from the website of the best math school in our country. Most problems in combinatorics are copied from some international competition of juniors with proper comment (city and year of competition). But this problem does not mention its true source. I am 100% sure that the problem is genuine because it was published by highly reputable and most trusted institution. In dozens of other problems that we downloaded from the same location (and solved!) we could not find a single mistake. $\endgroup$ – Oldboy Apr 27 '17 at 13:44
9
$\begingroup$

For any valid $n$ by $n$ grid, let's consider some set $S_k$ that contains any cell whose value is $\leq k$ for some given $k$. If we set $k$ to the maximum value of the cells (call this $m$) in the entire grid, then $S_k$ will contain every cell in the grid (this is our base case).

We can decrease $k$ to the smallest possible value for which $S_k$ still contains at least one cell from every row or every column. This condition holds for $k=m$, and possibly holds for some $k<m$, but what matters is that this minimal $k$ exists.

After finding this minimal $k$, let's rotate the grid such that we are looking at a scenario for which $S_k$ (at least) contains a cell from every row.

Let's focus on an arbitrary row. In this row, there exists some cell with value $a$ such that $a \leq k$ (this cell would be in $S_k$ by definition), and there also exists some cell with value $b \geq k$ (since $k$ is minimal across all rows and columns).

Some more detail on the $b$ cell: Since $k$ is minimal, we know this $b \geq k$ cell always exists. Let's assume it didn't and that every cell in the row had value $k-1$ instead (i.e. something $<k$). Then we could rotate the grid and say that each row (previously column) contains a cell with value $\leq k-1$, which contradicts our condition that $k$ was minimal to begin with.

Adjacent cells can only differ by at most $1$ in terms of absolute magnitude, which means that in each row there exists some contiguous / horizontal pathway from $a$ to $b$ that must eventually encounter a cell with value $k$.

Since this condition is true for all $n$ rows, we see that $k$ must occur at least $n$ times.

$\endgroup$
  • 1
    $\begingroup$ "there also exists some cell with value $b≥k$ (since $k$ is minimal across all rows)": This may be true, but I don't see why. Can you explain this step more fully please? $\endgroup$ – TonyK Apr 27 '17 at 16:40
  • $\begingroup$ @TonyK Added some explanation. Does that clarify? $\endgroup$ – Marcus Andrews Apr 27 '17 at 16:46
  • 1
    $\begingroup$ @TonyK Added more explanation using your $k-1$ example. $\endgroup$ – Marcus Andrews Apr 27 '17 at 17:31
  • 1
    $\begingroup$ Now it makes sense. Thank you! $\endgroup$ – TonyK Apr 27 '17 at 17:46
  • 1
    $\begingroup$ Very elegant proof, well done Marcus! I would have certainly asked the same question as TonyK if I had read the proof before him :) Now, it's all crystal clear, many thanks! I'm accepting this answer now. $\endgroup$ – Oldboy Apr 27 '17 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.