42
$\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?

Improve this question
$\endgroup$
8
  • 7
    $\begingroup$ "Dominck Badguy?" "Bad-gee, it's French." "He seems like a nice person!" $\endgroup$
    – corsiKa
    May 9, 2016 at 19:43
  • 6
    $\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, 2016 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, 2016 at 3:47
  • $\begingroup$ RIP Shirley.... $\endgroup$
    – Lightness Races in Orbit
    May 10, 2016 at 12:04
  • $\begingroup$ As a convention to avoid needless duplication in answers: WLOG let the top left square be 1. (if not, rotate and flip the board to get the smallest corner value to the top left, then add/subtract arbitrary constant to the entire board to meke the top left ==1). And WLOG since we chose 1 to be the top left and be the smallest, then the inter-edge difference must be +1 (not -1), hence the 2nd diagonal must be all-2s, 3rd diagonal must be all-3's etc. $\endgroup$
    – smci
    Apr 26, 2021 at 5:10

4 Answers 4

Reset to default
30
$\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.

Improve this answer
$\endgroup$
3
  • 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, 2016 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, 2016 at 1:13
  • 5
    $\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, 2016 at 1:41
3
$\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.

Improve this answer
$\endgroup$
3
  • 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, 2016 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, 2016 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, 2016 at 21:02
-1
$\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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I don't understand why you need a non-decreasing sequence. Can you explain in a few words? $\endgroup$
    – Marius
    May 9, 2016 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, 2016 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, 2016 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, 2016 at 19:54
-2
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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