6
$\begingroup$

You are given a $9\times9$ grid board.

You have 40 "$1$"s and 41 "$0$"s. You can put these numbers wherever you want on the board.

After that, you will take the sum of the numbers in each row and column and as a result there will be $18$ sums at the end.

  1. Is it possible to have 9 even sums and 9 odd sums at the end? If so, give an example.

  2. what is the maximum number of even sums?

$\endgroup$
7
$\begingroup$

Part 1:

Adding together an odd number of odd numbers, you will get an odd number (because odd*odd=odd). So if you partition an even number like 40 by spreading the 1s over the rows of the board, the number of odd rows is even. The same goes for the columns, so the total number of odd rows and columns is even.

Part 2:

$40 = 4*10 = 4*6+4*4$. Arrange the forty 1s into a 4x6 rectangle and a 4x4 square. These fit side by side on the 9x9 board. The dimensions of these are all even, so all 18 rows and columns are even. It could look as follows:

 xxxx.xxxx
 xxxx.xxxx
 xxxx.xxxx
 xxxx.xxxx
 xxxx.....
 xxxx.....
 .........
 .........
 .........

$\endgroup$
6
$\begingroup$

It's

impossible

Explanation:

The sum of all rows will be 40. This must involve an even number of odd sums. Same for columns, therefore we always have an even number of odd sums.

$\endgroup$
6
$\begingroup$

Not possible.
The sum of all sums will be 80 ($2 \times 40$) because we will add each 1 twice. Once for the column that it is in and one for the row.
So the sum of sums needs to be even.
If there were 9 even sums and 9 odd sums we would have the sums like this:
$ 9 \times 2 \times n + 9 \times (2 \times m + 1)$ which is an odd number.
$ 9 \times 2 \times n + 9 \times (2 \times m + 1) = $
$2 \times (9 \times n) + 2 \times (9 \times m + 4) + 1 = $
$2 \times x + 2 \times y + 1 = $
$2 \times (x + y) + 1$

$\endgroup$
  • 1
    $\begingroup$ +1. The logic used here can be used to prove the answer to question #1 for a board of any size (square or not) filled with any numbers (not just 0's and 1's). $\endgroup$ – Michael Seifert Oct 20 '17 at 20:03
1
$\begingroup$

The sum of all rows will always be 40. The sum of all columns will always be 40. If you have 40 1's how can you have any other result? You cannot possibly have 9 odd sums and end up with 40 (an even number), so, no! Impossible!

$\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.