5
$\begingroup$

Anna and Boris play a game on a 9x9 chessboard. Anna goes first and turns alternate thereafter. In each move, Anna puts a red counter on a vacant square while Boris puts a blue counter on a vacant square. When the board is completely filled, a row with more red counters than blue counters is called a red row, and a blue row otherwise. Red and blue columns are similarly defined. The score for Anna is the sum of the numbers of red rows and red columns while that for Boris is the sum of the numbers of blue rows and blue columns. What is the highest possible score for Anna?

Clarification example: After all the squares have been filled, if there are 7 red rows and 3 red columns then Anna’s score is 7+3=10.

2nd clarification: We are not assuming that Boris is playing well. We need to consider all possible games including games in which Boris is trying to help Anna.


This puzzle came from a Leningrad Mathematical Olympiad.

$\endgroup$
0

1 Answer 1

11
$\begingroup$

Best score for Anna is 16 points. Anna places 41 counters. She must place at least 5 counters in a row to claim it, so she gets at most $\lfloor41/5\rfloor=8$ points from rows. Similarly she gains at most 8 points from columns. Therefore her score is at most 16.

That score is attainable with:

\begin{matrix} R&R&R&.&.&.&R&R&. \\ R&R&R&R&.&.&.&R&. \\ R&R&R&R&R&.&.&.&. \\ .&R&R&R&R&R&.&.&. \\ .&.&R&R&R&R&R&.&. \\ .&.&.&R&R&R&R&R&. \\ R&.&.&.&R&R&R&R&. \\ R&R&.&.&.&R&R&R&. \\ .&.&.&.&.&.&.&.&R \\ \end{matrix}

$\endgroup$
3
  • 2
    $\begingroup$ It is interesting that the player who goes second can obtain the same score. $\endgroup$ Feb 19 at 0:59
  • 1
    $\begingroup$ If Boris tries to hinder Anna then Anna scores only 10. WLOG assume Anna starts in the centre. If Anna mirrors Boris's moves then Anna always scores 10. But if Boris concedes r5 and c5 and applies a strategy stealing argument to every other row/column then Boris scores at least 8. QED $\endgroup$
    – happystar
    Feb 19 at 8:22
  • 1
    $\begingroup$ There's a certain elegance to determining the (upper) bound using theory, and then finding a concrete example where it is attained. :) How did you go about finding that attainable configuration? $\endgroup$
    – Greg
    Feb 19 at 17:42

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.