23
$\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 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 and column are noted. The score is built as follows:

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

Both players add their points. The player who has the most will win the game.

Assuming that your friend plays a perfect strategy, what is the maximum point you can get?

Improve this question
$\endgroup$
8
  • $\begingroup$ Might as well use the tag game and chessboard $\endgroup$
    – Red-Jeweled
    Jun 22, 2016 at 12:00
  • 1
    $\begingroup$ If both are experts, then none can get the maximum possible score. Do you want us to note the fact that the friend will play his best to win, or do you want us to tell you the maximum possible score, like playing with a newbie? $\endgroup$
    – dryairship
    Jun 22, 2016 at 12:08
  • $\begingroup$ Also, saying that you is an expert is probably irrelevant, since any of your mistakes will lower your score and implicitly makes the related solution invalid. $\endgroup$
    – Red-Jeweled
    Jun 22, 2016 at 12:50
  • 6
    $\begingroup$ @rasim, do you know the answer to this question? (I'm just trying to get a handle on how much reason we have to think there is an accessible answer.) $\endgroup$
    – Gareth McCaughan ♦
    Jun 22, 2016 at 16:21
  • 1
    $\begingroup$ Seemed like in your rules a row or column counted “as one point” for one player or the otherr. So there are 14 points to be won not 48. But that’s not the way that anyone has interpreted it. Please clarify, thanks. $\endgroup$
    – Laska
    Oct 18, 2017 at 19:37

4 Answers 4

Reset to default
4
$\begingroup$

I guess the answer is that

with best play on both sides the scores are equal (for any value of 7)

but I don't have anything resembling a proof. Here are some very partial results.

For a $1\times n$ board,

the scores (player 0 minus player 1) go 0,2,2,0,0,6,6,0,0,10,10,0,0,14,14, etc. (This is pure calculation; all games are equivalent.)

For a $2\times n$ board,

the scores go 2,0,2,0,2,4,6, ... (by computer calculation) and I'm not sure what the pattern is. These scores are always non-negative, because player 0 has the following strategy that guarantees getting both rows: play in the less-full row until at least one row has only one space left; if that row has an odd number of 1s, play in that row; otherwise, play only in the other row from then on (which player 0 can always do because when it's her turn the number of spaces in the other row is odd and hence nonzero).

For other small board sizes,

3x3 and 3x4 are both draws (by computer calculation) and I haven't gone any further than that.

When either dimension of the board is a multiple of 4,

player One can be sure of at least drawing: suppose e.g. the horizontal dimension is a multiple of 4, then when player 0 plays at (x,y) player 1 plays at (x XOR 1, y) ensuring that every row contains exactly as many 0 as 1, hence an even number of both, so all the rows score for player 1, so player 1 at least draws.

I have not found any case

where One scores more than Zero (i.e., where the scores I've been reporting above are negative)

and suspect there are no such cases but have no proof. (I briefly thought I had a strategy that lets player 0 ensure that all rows have odd sum, which would certainly do it, but obviously there cannot be such a strategy unless the total number of 1s is odd, which e.g. it is not on any square board.)

Improve this answer
$\endgroup$
11
  • $\begingroup$ I'm pretty sure 3x3 isn't a draw. Let's say player 2 follows the strategy of aiming to control 2 corners on a side (e.g. top left and top right or bottomleft / bottomright etc but not topleft/bottomright). Clearly there's no way for p1 to stop this. after move 2 (aka 4-ply, 2 ones and 2 zeros on the board), p2 will have his 2 corners. By symmetry, without loss of generality, say it's topleft/ topright. At this point, no matter where p1's zeros are, p2 will be able to win with a score 6-2 or better $\endgroup$
    – astralfenix
    Aug 26, 2016 at 16:11
  • $\begingroup$ Maybe you're right but I think I need more details. So suppose One plays at top left and top right and Zero plays in the two spaces below those; then it's Zero's turn and s/he plays at bottom left. How does One play so as to win by 6-2 or better? $\endgroup$
    – Gareth McCaughan ♦
    Aug 26, 2016 at 16:23
  • $\begingroup$ My question stands. In position [1,-,1 ; 0,-,0 ; 0,-,-] with One to play, how does One guarantee a win? I'm not saying it can't be done, though for what it's worth my program says this position is a draw with best play on both sides. But I'd like to know why you say it's a win. $\endgroup$
    – Gareth McCaughan ♦
    Aug 26, 2016 at 16:27
  • $\begingroup$ Huh. There was another comment by astralfenix there a moment ago, to which my last comment is a reply. (It said, roughly, "oops, not 6-2, but certainly 4-2 or better".) $\endgroup$
    – Gareth McCaughan ♦
    Aug 26, 2016 at 16:28
  • $\begingroup$ ah, I may have miscalculated. in your example it seems to be 4-4 $\endgroup$
    – astralfenix
    Aug 26, 2016 at 16:28
3
$\begingroup$

The maximum of 48 is possible:

There are 24 ones.

You'd like to get the only even columns to be 0. So can we get 24 ones into a partition of 6 odd numbers?

Yes: 5 3 5 3 5 3

Can we play out the ones that way?

Just laying them down:

1 | 1 | 1 | 1 | 1 | 0 | 0 = 5
0 | 1 | 0 | 1 | 0 | 1 | 0 = 3
1 | 1 | 1 | 1 | 1 | 0 | 0 = 5
0 | 1 | 0 | 1 | 0 | 1 | 0 = 3
1 | 1 | 1 | 1 | 1 | 0 | 0 = 5
0 | 1 | 0 | 1 | 0 | 1 | 0 = 3
0 | 0 | 0 | 0 | 0 | 0 | 0 = 0
= = = = = = = = = =
3 | 6 | 3 | 6 | 3 | 3 | 0

Adjusting:

1 | 1 | 1 | 1 | 1 | 0 | 0 = 5
0 | 1 | 0 | 1 | 0 | 1 | 0 = 3
0 | 1 | 1 | 1 | 1 | 1 | 0 = 5
1 | 0 | 0 | 1 | 0 | 1 | 0 = 3
0 | 1 | 1 | 1 | 1 | 1 | 0 = 5
1 | 1 | 0 | 0 | 0 | 1 | 0 = 3
0 | 0 | 0 | 0 | 0 | 0 | 0 = 0
= = = = = = = = = =
3 | 5 | 3 | 5 | 3 | 5 | 0

And that gives the maximum 6x5+6x3=48 score.

For completeness, the maximum evens score of 48 is also possible; just invert all but the bottom right number:

0 | 0 | 0 | 0 | 0 | 1 | 1 = 2
1 | 0 | 1 | 0 | 1 | 0 | 1 = 4
1 | 0 | 0 | 0 | 0 | 0 | 1 = 2
0 | 1 | 1 | 0 | 1 | 0 | 1 = 4
1 | 0 | 0 | 0 | 0 | 0 | 1 = 2
0 | 0 | 1 | 1 | 1 | 0 | 1 = 4
1 | 1 | 1 | 1 | 1 | 1 | 0 = 6
= = = = = = = = = =
4 | 2 | 4 | 2 | 4 | 2 | 6

giving an odds score of zero, and an evens score of 2x6+6x4+6x2=48.

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ Why would this happen with your friend "playing a perfect strategy"? (I take it that means he's trying to win rather than trying to help you win.) $\endgroup$
    – Gareth McCaughan ♦
    Jun 22, 2016 at 17:06
  • $\begingroup$ @GarethMcCaughan Yes, I agree that is the "better" question to answer, but given Hackerdarshi's answer, I gave this solution. $\endgroup$
    – Mark Hurd
    Jun 22, 2016 at 17:14
  • $\begingroup$ Is there a logical way to come to the above answer ( namely that the score of 48 is possible ) ? Or is trial and error the only method to reach this conclusion ? $\endgroup$
    – Hemant Agarwal
    Jun 3, 2021 at 12:43
0
$\begingroup$

44

And the board would look like:

1 | 1 | 1 | 1 | 1 | 0 | 0 |=5
1 | 1 | 1 | 0 | 0 | 1 | 0 |=4(not counted for you)
1 | 1 | 1 | 0 | 0 | 0 | 0 |=3
1 | 1 | 1 | 0 | 0 | 0 | 0 |=3
1 | 1 | 1 | 0 | 0 | 0 | 0 |=3
1 | 1 | 1 | 0 | 0 | 0 | 0 |=3
1 | 1 | 1 | 0 | 0 | 0 | 0 |=3
--------------------------
7 | 7 | 7 | 1 | 1 | 1 | 0 |

So Your score = (3*5)+(7*3)+(3*1) + 5 = 15 + 21 + 3 + 5 = 44.
Friend's score = 4

Improve this answer
$\endgroup$
8
  • 5
    $\begingroup$ I'm not the downvoter, but how do you prove that this is the best result your opponent can get? Remember: you and your friend play the game without any mistake/fault (i.e. both are expert on this game). $\endgroup$
    – Sphinxxx
    Jun 22, 2016 at 12:30
  • 3
    $\begingroup$ I didn't downvote, but I can give you an explanation. Since both players play the optimal strategy the second player would not let this happen. $\endgroup$
    – Marius
    Jun 22, 2016 at 12:31
  • 7
    $\begingroup$ This answer is accurate for the way the question is stated (though we all know it is stated incorrectly). "Your friend" played perfectly and allowed "You" to get the maximal score. $\endgroup$
    – LeppyR64
    Jun 22, 2016 at 12:40
  • 2
    $\begingroup$ You can move one of those single '1's down, and you would get a score of 44 $\endgroup$
    – Kruga
    Jun 22, 2016 at 12:43
  • 2
    $\begingroup$ I think you can make 46 points: move the (3,3) in (2,4), and the (4,3) in (4,4). your opponent will have only 2 points left $\endgroup$
    – Sechiro
    Jun 22, 2016 at 14:10
0
$\begingroup$

My first attempt:

With a board of 7x7, there are 49 grids. With me going first and my friend going second on each turn, there will be 25 of [0] and 24 of [1] on the board when the game ends. Assuming my friend plays a perfect strategy, the maximum point my friend can get is:

enter image description here

Where the max point I can get is zero, consider the integer 0 is even.

Improve this answer
$\endgroup$

Your Answer

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

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