3
$\begingroup$

A 4×4 table has 18 lines, consisting of the 4 rows, the 4 columns, 5 diagonals running from southwest to northeast, and 5 diagonals running from northwest to southeast. A diagonal may have 2, 3 or 4 squares. Ten counters are to be placed, one in each of ten of the sixteen cells. Each line which contains an even number of counters scores a point. What is the largest possible score?

I drew a table with 4 rows and 4 columns and 10 diagonals as described above, and I placed the counters in the boxes. I got the score of 6.

Diagram for above problem

$\endgroup$
4
$\begingroup$

I used a computer to find the best solution. It is unique up to rotation/reflection.

Only 1 of the 18 lines is odd, for a score of 17:
enter image description here

$\endgroup$
  • $\begingroup$ Thank You for the solution. ... but, with the arrangement above; I am getting only score of 16 ... am I missing a line? $\endgroup$ – Math Tise Jun 18 '18 at 6:08
  • 2
    $\begingroup$ @Math Tise You might have overlooked the line from the second row first column to first row second column contains zero markers, which is even. $\endgroup$ – phenomist Jun 18 '18 at 6:12
  • $\begingroup$ ohhhh.... got it... Thanks again @Jaap Scherphuis ! :-) $\endgroup$ – Math Tise Jun 18 '18 at 6:15
  • $\begingroup$ I've just checked that even if you don't count empty lines in your score, this solution is still the unique optimal one, i.e. there are no solutions with 16 filled even lines and 2 odd lines. $\endgroup$ – Jaap Scherphuis Jun 18 '18 at 6:25
0
$\begingroup$

Here is a sketch of an argument that 17 is maximal.

If 18 is possible, then every row and column must have an even number of filled cells, as if one row/column is odd, then so is another, hence at most 16.

For the diagonals, both unused corners must be of the same parity, otherwise we can use the same argument as above.

The rest of the argument comes from examining the three possibilities this creates, and determining that they are all impossible, and so by demonstration, 17 is the maximum.

With all 4 corners unfilled, we must place all 10 counters in the middle cells, but this creates either 2 odd rows or columns (imagine filling all 12 and removing 2).

With only 2 filled, each edge contains exactly one more counter, hence the four inner cells must be filled, which leaves either 3 in a row/column, or an odd 2-diagonal.

With all 4 corners filled, each edge has 0 or 2 more. We can then break this down into 3 edges full, 2 edges full or one edge filled, so that at least one of the 2-length diagonals will be odd.

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