12
$\begingroup$

Each square of an 8x8 chessboard is marked with a positive integer. The integers can be changed according to the following two rules:
(1) all integers in a row are doubled
(2) all integers in a column are reduced by 1

Is it possible to transform to a "zero" board, i.e. the number 0 shows up 64-times on the board?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Possible to know the source of this puzzle ? $\endgroup$
    – Hemant Agarwal
    Commented Jul 2, 2021 at 17:16

1 Answer 1

Reset to default
18
$\begingroup$

This is

possible

Proof:

Let's concentrate on a single column first, ignoring the rest of the board. All the numbers in a column start off being positive, so non-zero. If any cell in the column contains a 1, then double that row turning it into a 2. Once there are no more ones, decrement the column. Keep repeating this procedure. Note that any number that is not 1 will be reduced, so eventually all the cells of the column become 1 at the same time. As a final step, this column can then be reduced to zero.

The above method for zeroing a column will not introduce any zeroes elsewhere on the board (it may double them several times, but never decreases them), so the only zeroes it produces is when the whole column goes to zero at once.

Once a column contains only zeroes, we can keep it that way while solving the rest of the board. This is because row doublings will not affect it, nor will decrementing any other column. Therefore we can make each column zero individually until the whole board is zero.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I'm a bit confused: What do we get if we decrement 0? I expected -1 since OP only stated that the setup is entirely built by positive integers so I didn't see a different specification of reduced by 1. Maybe there is some convention on puzzling SE I just don't know (being very new to the site). Thanks in advance for clarification. $\endgroup$
    – Wolf
    Commented Jul 2, 2021 at 7:30
  • 2
    $\begingroup$ @Wolf In my solution that never happens. That is why all the ones are doubled before decrementing. Only when a whole column is 1, then the whole column is decremented to zero and stays that way. There are no zeroes at the start, so the only time zeroes appear is when a whole column is set to zero at once. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 2, 2021 at 7:44
  • 2
    $\begingroup$ Jaap's method never decrements a zero. At the start there are no zeroes, and everything is positive, and if there's ever a danger of getting a zero, that row gets doubled by the algorithm. Only when the entire column is ones, they get decremented to zero, after which nothing affects them. $\endgroup$
    – Bass
    Commented Jul 2, 2021 at 7:44
  • $\begingroup$ Thanks again for your helpful comments. However, the first sentence in Proof had a very misleading effect on me. I read it as a kind of introduction, while it is already part of the algorithm, which is the core of the proof. $\endgroup$
    – Wolf
    Commented Jul 2, 2021 at 8:57
  • 2
    $\begingroup$ @TKoL My method is not very efficient, which becomes very obvious when played in your implementation. Some simple improvements can be made, such as doubling not just the ones in a column but doubling any value that is no more than half the largest number in the column, i.e. do any doublings that won't increase the column's maximum value. Of course, efficiency is not relevant to the proof in my answer. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 2, 2021 at 17:03

Your Answer

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

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