4
$\begingroup$

You are playing a game with your friend on a $7$x$7$ grid board. In every turn, you begin by putting a $0$ (zero) on any empty square on the board, and then your friend puts a $1$ (one) on a different empty square.

The game ends when there is no empty square left i.e. all squares are marked with either a zero or a one. After that, the sum of the numbers in each row is noted. The score is built as follows:

  1. The odd sum values go to you.
  2. The even values go to your friend.

So, if a row has 0110100 then this row will give you 3 points and the friend would get none. Similarly, if a row was 1101010, then your opponent gets 4 points and you get none.

Both players add their points. The player who has the most points will win the game.Assume that your friend plays optimally.

Question 1: Can you win this game every time ?

Question 2: What is the maximum number of points that you can score?

The question above is a variant of this question. The only difference is is that the original question takes both, the rows and the columns into account. Whereas the question above only considers rows.

$\endgroup$
3
  • 1
    $\begingroup$ I'll ask the same question as I did about the previous one: Do you know the answer? I ask because this is the sort of thing that might turn out to be very difficult to determine rigorously, but if you know the answer that may indicate that there's something clever one can do to figure it out. $\endgroup$
    – Gareth McCaughan
    Jun 3 at 15:34
  • $\begingroup$ @GarethMcCaughan , I tried the question above but couldn't come up with a satisfactory enough answer. $\endgroup$ Jun 17 at 12:14
  • $\begingroup$ Here is another very similar question : puzzling.stackexchange.com/questions/9626/… $\endgroup$ Jul 7 at 18:40
4
$\begingroup$

If both players play optimally then I think that

The game always ends in a draw

Reasoning

Label the $j$th cell of row $i$ as $(i,j)$.
Then you, as first player, can guarantee $12$ points with the following strategy,

First place a $0$ in cell $(4,4)$.
After that, if your friend places a $1$ in cell $(i,j)$ then
(i) Place a $0$ in cell $(i, 8-j)$ if $j \neq 4$.
(ii) Place a $0$ in cell $(8-i, j)$ if $j=4$.

After this game, there will be four rows with three $1$s and three rows with four $1$s making the score $12$ each.

On the other hand, your friend, as second player can guarantee $12$ points with the following strategy,

Partition the $49$ cells of the grid into $24$ pairs and a singleton as follows:
- For $j \neq 4$ cell $(i,j)$ is paired with $(i,8-j)$.
- For $i \neq 4$ cell $(i,4)$ is paired with $(8-i,4)$.
- The cell at $(4,4)$ is a singleton.

Then whenever the first player puts a $0$ in cell $(i,j)$,
(i) If $(i,j)$ is part of a pair and its partner is unoccupied, put a $1$ in the partnered cell.
(ii) Otherwise, find a pair for which both cells are empty and place a $1$ in one of them (such a pair is always guaranteed to exist when following the strategy).

At the end of such a game, the score will again be $12$ points each.

Hence, since both players can guarantee to get at least $12$ points, the score must always be $12-12$ if both players play optimally.

$\endgroup$
9
  • $\begingroup$ You had posted an answer earlier, but then you realised that you had misunderstood the question. May I ask what you had thought the question was ? Secondly, nobody has been able to solve the original question : puzzling.stackexchange.com/questions/36455/even-and-odd-game . Do consider giving it a try as well. $\endgroup$ Jun 3 at 14:37
  • $\begingroup$ @HemantAgarwal I thought that the scoring was 1 point for each odd row for player 1 and 1 point for each even row for player 2 (instead of 3 and 4). I just didn't read the question properly. $\endgroup$
    – hexomino
    Jun 3 at 14:40
  • $\begingroup$ I would like to read that answer as well ...Can you please add it to your answer above ? $\endgroup$ Jun 3 at 14:46
  • $\begingroup$ I think that in that case, you can go through the same argument to find that player 1 can guarantee a 4-3 win but the strategies I have in mind are exactly as above so I don't know if this would be worth adding in. $\endgroup$
    – hexomino
    Jun 3 at 14:49
  • $\begingroup$ This is very elegant. I can (via computer brute-forcing) confirm that the answer is correct. $\endgroup$
    – Gareth McCaughan
    Jun 3 at 16:30
1
$\begingroup$

hexomino's answer nicely resolves the question as asked (and, Hemant, if you're in any doubt as to which answer you should accept I think it should be hexomino's). I did some computer brute-forcing which suggests a general pattern. Suppose there are $r$ rows and $c$ columns; then the final score with best play is:

When $c$ is even: $(-1)^{(c+2)/2}rc/2$.
When $c$ is odd and $r$ is even: $(-1)^{(c-1)/2}r/2$.
When $c$ is odd and $r$ is odd: $(-1)^{(c-1)/2}(r-c)/2$.

Let's prove this. The approach will be similar to hexomino's, and I am confident that if you'd said to hexomino "hey, does that generalize" they'd quickly have come up with the same generalizations as me; I'm not claiming to have done anything very clever, and if you like this answer you should upvote hexomino's because it contains all the actual insight that's in this one :-). We'll do it one case at a time, but first let's explain the idea that all cases have in common.

We will divide the spaces on the board, or all but one of them, into pairs. This ensures that either player, should they so choose, can guarantee that exactly one space in each pair contains a 1. (If there is a leftover space it contains a 0, because Zero is the one who gets an extra turn.) Proof: whichever player is trying to achieve this always plays in the leftover space if available, else in whichever pair their opponent just played in if possible, else in an empty pair. It's easy to see that this always achieves the goal. Call it "Strategy P". Now (I'll provide a separate argument for this in each case) any final configuration in which this has been achieved will have the same score -- which will be the score listed above. If so, this means that this must be the score when both players do their best: if we suppose that either can do better, we just imagine the other following Strategy P and thwarting them.

So that's the overall framework. Now let's fill in the details, case by case.

Let's begin with the (odd,odd) case. Pair up all but one of the rows, and pair up all but one of the spaces in the remaining row. The score if either player follows Strategy P, putting one 1 in each pair, is found as follows: there are $(r+1)/2$ rows with $(c-1)/2$ 1s and $(r-1)/2$ rows with $(c+1)/2$ 1s, and a bit of easy algebra shows that the score is as I claimed.

OK, that's the first case, generalizing hexomino's answer. Now let's look at the other cases above. First, the first one:

... an even number of columns. This time we'll pair off spaces in each row. Now when Strategy P is applied, every row contains $c/2$ 1s, which means the score is $\pm c/2$ for each row, the sign depending on the parity of $c/2$, as claimed.

And then the second:

... an even number of rows, but an odd number of columns. This time we'll pair off all but one of the spaces in each row, and then pair off all the remaining spaces. Now when Strategy P is followed, half the rows have $(c+1)/2$ 1s and the other half have $(c-1)/2$, so each pair of rows scores $+1$ if $(c+1)/2$ is odd and $-1$ otherwise.

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