I came across a problem which is somewhat like this.

Given an array containing odd number of 1 and any number of 0, two players are choosing a number in turn. When there are no more numbers to choose from, the player with odd number of 1 will win the game. If both player plays optimally who will win the game? And if first player wins, what should be his first move?

What I think after a lot of observations is that if number of 1 in the array is of the form 4k + 1, then the first player would win, and he should choose a 1 as his first move.

arr = {1 1 1 1 1 0 0 0 0}, winner = first player, first move = 1

If the number of 1 in the array is of the form 4k + 3 then the first player would win if length of array is even and the second one will win if length of array is odd.

arr = {1 1 1 0 0 0}, winner = first player, first move = 0

arr = {1 1 1 0 0}, winner = second player

But the solution I reached to may or may not be correct. I can not seem to figure out a proof for this. So what I would like to know is whether my solution is correct and how to create proofs for this kind of questions.

And I'm not so sure about the tags. If an expert would add the proper tags that would be great.

Thanks in advance.


I suggest that you write down an abstraction of your game as follow:

The set of states is $\{A,B\}\times\{E,O\}\times\{E,O\}\times\{E,O,0\}\times\{E,O,0\}$

A state $(A,E,O,E,O)$ represent all concrete states where:

  • it is player $A$ turn
  • $A$ have gathered en Even number of 1
  • $B$ an Odd number
  • there are an even number of 1 left
  • there are an odd number of 0 left

You have a finite number of such state. You can draw the transition between them. Given the obtained graph it is easy to compute the concrete states that are wining in an abstract state (start from the state where there are no $0$ or no $1$ left, then the other). You will see that the winning states are almost what you suggested (but not that because $11111$ is wining for the first player whereas $111110$ is wining for the second player).


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.