40
$\begingroup$

Professor Veryevil pointed the gun at Shirley Knowsalot. "And why shouldn't I just kill you now?" asked the professor.

"What about your shtick where you always give the hero a math puzzle that they can solve for their freedom?" responded Shirley.

"Oh yeah, I forgot about that. Let's see ... " The professor wished there was some sort of puzzling website he could call upon right now, but didn't know of one so he instead had to think fast. Looking around the room, and he eventually spotted a marker and a chessboard. "I challenge you to write an integer in every square of this chessboard so that

  • the positive difference between any two squares that share an edge is at most $1$, and
  • no integer appears more than seven times."

"What if I think that's impossible?" asked Shirley.

"Umm, well ... give me a proof of impossibility then. But it better be correct ... or else!" (awkward pause) "To clarify, the 'or else' means I'll shoot you with my gun."

"Could you be quiet and let me think?" responded Shirley.

How should Shirley respond to the professor's challenge?

$\endgroup$
  • 6
    $\begingroup$ "Dominck Badguy?" "Bad-gee, it's French." "He seems like a nice person!" $\endgroup$ – corsiKa May 9 '16 at 19:43
  • 5
    $\begingroup$ "The professor wished there was some sort of puzzling website he could call upon right now" I like the reference ( ͡° ͜ʖ ͡°) $\endgroup$ – fi12 May 9 '16 at 20:24
  • 1
    $\begingroup$ The fact that he specified no more than 7 times and the chessboard is 8 across is basically a giveaway that the problem is impossible. $\endgroup$ – Loren Pechtel May 10 '16 at 3:47
  • $\begingroup$ RIP Shirley.... $\endgroup$ – Lightness Races in Orbit May 10 '16 at 12:04
26
$\begingroup$

Suppose that we have a chessboard with the desired properties.

  1. Find the greatest number in each row. Out of these numbers, let the smallest be $m_i$ in row $i$.
  2. Find the smallest number in each row. Out of these numbers, let the largest be $n_j$ in row $j$.

Note the following:

  • Row $i$ contains only numbers that are at most $m_i$.
  • Row $j$ contains only numbers that are at least $n_j$.
  • Every row contains a number greater than or equal to $m_i$.
  • Every row contains a number less than or equal to $n_j$.
  • If a row or column contains numbers $x$ and $y$, it must contain all the numbers between $x$ and $y$.

If $m_i\ge n_j$: Every row contains a number at least $m_i$ and a number at most $n_j$, so it must contain $m_i$, $n_j$, and every number in between. They appear at least eight times, a contradiction.

If $m_i<n_j$: Consider what happens in each column as you move from row $i$ to row $j$. You must pass from a number that is at most $m_i$ to a number that is at least $n_j$, so these two numbers (and every number between them) must occur in every column. Therefore these numbers appear at least eight times, again a contradiction.

Therefore no such board exists.

$\endgroup$
  • 4
    $\begingroup$ This appears to be the most complete proof, but it's a little more difficult to understand exactly why your two contradictions are true without rereading the previous statements several times (at least for me). $\endgroup$ – Dan Henderson May 9 '16 at 23:18
  • $\begingroup$ I didn't follow through the whole thing, so this may or may not make a difference to the correctness of the proof, but you do seem to have an untested assumption: that row i and row j are distinct. I don't see why they have to be. $\endgroup$ – Wildcard May 10 '16 at 1:13
  • 4
    $\begingroup$ @Wildcard If row $i$ and row $j$ are the same, then $m_i<n_j$ is impossible (it can't be the case that all numbers in that row are at most $m_i$ but also at least $n_j$). The proof for the case where $m_i\ge n_j$ does not require $i$ and $j$ to be distinct. $\endgroup$ – f'' May 10 '16 at 1:41
4
$\begingroup$

Not sure how to properly explain it, but it's impossible.

Let's say we start with a 1 in one of the corners. Then we either have a 0 or 2 in the two adjacent cells because of the first rule (let's say we fill in 2s). Then adjacent to those we need to fill in 3 (or 1 again); etc. It continues as in the picture below:
enter image description here

The middle diagonal is always 8 times the same number, so we cannot comply to the second rule:

no integer appears more than seven times.

If we start with another number instead of 1, and first decrease and later on increase, we still have 8 times the same number at the middle diagonal (and in addition also more than 7 times the same number when we increase again):
enter image description here


How should Shirley respond to the professor's challenge?

Since there are 8 x 8 cells on a chessboard, and I'm disallowed to have a difference more than 1 for each adjacent cell (your first rule), the middle diagonal will always have 8 times the same number, which breaks your second rule.

$\endgroup$
  • 10
    $\begingroup$ It's ok to have adjacent squares be the same value, so other patterns besides diagonal stripes are possible, e.g, label all squares in first column 1, second column 2, ... last column 8. Not saying your answer is incorrect, just that your proof doesn't account for all possibilities. $\endgroup$ – Mike Earnest May 9 '16 at 17:36
  • 3
    $\begingroup$ Also, the real reason the second example fails is because you've doubled the amount of non-zero numbers. The "zero" problem is trivial to fix if you just change one of the corner zeros to 2. $\endgroup$ – Patrick M May 9 '16 at 18:30
  • $\begingroup$ @MikeEarnest Ah, you're indeed right. I misread the first rule of the question. In that case my answer does indeed only cover the diagonal cases. $\endgroup$ – Kevin Cruijssen May 9 '16 at 21:02
0
$\begingroup$

I believe it is impossible.

In two simple scenarios, we can see why this creates an impossibility.
Start from a corner, then have each diagonal outward be an increasing number. At the main diagonal (8 squares) we reach the impossibility.
Another scenario is to fill in the first column with 1's, up to 7x. The next column will have 2's (7x), but that leaves the square below the first column unfilled. It can only be 0 or 2, but since we have 7x 2's that's out, and a 0 means that below the 2's we need an eighth 1. Hence an impossibility.

$\endgroup$
  • 3
    $\begingroup$ I don't understand why you need a non-decreasing sequence. Can you explain in a few words? $\endgroup$ – Marius May 9 '16 at 17:01
  • $\begingroup$ @Marius Well non-decreasing is relative for this problem since 1-8 could technically be considered 8-1 and make no difference in the logic of the problem. I think what he meant was you need a set of 8 consecutive integers, but I'm not the answerer so I can't be 100% sure $\endgroup$ – Gordon Allocman May 9 '16 at 17:37
  • 1
    $\begingroup$ You could easily have a row of 0 1 2 1 0 1 2 1 and still be valid. It is impossible but this isn't why. $\endgroup$ – corsiKa May 9 '16 at 19:49
  • $\begingroup$ @GordonAllocman I was going for a strictly increasing idea (00111123) that allowed repeats, but it didn't hold up, even for a "diagonals only" scenario that didn't start in a corner. $\endgroup$ – JonTheMon May 9 '16 at 19:54
-1
$\begingroup$

It's impossible because there are 8 square across, 8 squares down, and 8 squares diagonally. Therefore even if, for any square, none of the adjacent squares contained the same number, you would require at least 8 instances of at least one number, therefore there is no solution.

$\endgroup$

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.