# Binary manipulation game

I made a (for now, 2 player) game once that deals with manipulating binary numbers on a single list. Here are the rules.

## Rules

For now, take $n=5$. If possible, provide a solution for generalized $n$.

Player 1 is called the lead, and has a (supposed) advantage over the other one. He starts by declaring a (decimal) number $k$. He also writes an $n$-bit binary number at the top of a list.

Player 2 copies down this number twice. In one copy, he changes a single $0$ into a $1$. In the other copy, he replaces a single $1$ with a $0$. For example, if the number is $10011$, two possible numbers following it could be $00011$ (remove $1$) and $11011$ (remove $0$).

After this, on each turn, a player picks up (at his will) either of the $2$ numbers written by the opponent. He makes $2$ copies, and switches a $0$ in one, and a $1$ in the other, similar to player 2's first move.

At any point in time, only the last $k$ numbers remain on the list, all previous numbers are deleted. A player can not write a number that is on the list again. However, if it is being deleted with his move entering, then it is allowed.

A player loses when he is unable to provide $2$ numbers. The winner wins $k$ points.

## Question

If both players use optimal strategies, who wins? If player 1 wins, what value of $k$ will he choose.

What if $00000$ and $11111$ were banned for the first move? Then it would become a more proper game. What would the answer be, then?

• I don't thin i understand the purpose of k – kaine Feb 13 '15 at 16:52
• I think the game might be broken... Geobits has an answer that seems to work. – mdc32 Feb 13 '15 at 17:18
• @mdc32 Yes, his answer is right, and it is a sort-of trick question. – ghosts_in_the_code Feb 14 '15 at 10:36
• @mdc32 If you insist on a proper one, here it is. – ghosts_in_the_code Feb 14 '15 at 10:36

Player one should choose 11111 or 00000 as his initial number. Player two cannot form two numbers by switching a 1 and 0. Game over. This generalizes to an $n$-bit number quite well.

$k$ can be however many points player one desires.

• @MatthewRead It doesn't matter. The rules say player two has to form a number by switching a 1, and a number by switching a 0. You can't switch a 0 from 11111 at all; it doesn't have any. I don't see any option to not switch something. – Set Big O Feb 13 '15 at 16:56
• You're right, I misunderstood the rules. I assumed the second changed number was being derived from the first changed number rather than from the original. – Matthew Read Feb 13 '15 at 16:59
• That was fast ! – ghosts_in_the_code Feb 14 '15 at 10:35

First off .... if the problem is unknowingly formed , it means it is open for variety of solutions where this one takes part .

We must know before that if k is small at some point of 2 or 3 or even bigger the game would be endless .

k will be chosen according to how far we can advance in tree-expanding ....

Starting by 00001 - this option forces each level to be less developped by the opponent in order to restrict his choices .... but i found out that the opponent will be tending to win the game whatever the first player s choice is

So i began with 00011 to see where it leads ... and i concluded that if k supposed to be sufficiently big , k= 21 or 17 , this choice is defeating !

the following figure illustrates my solution:

We represent binary sequence by positions of 1 digits in the number ex: 00001 = 1 , 00101 = 31

Red colored numbers mean this choice isnt developable , green numbers means this choice is developable but not used (yet) in tree expanding.

• if this is attempt is favorable and well estimated i ll struggle with a piece of code in order to verify a general rule with any initial number containing two 1s . – Abr001am Feb 14 '15 at 22:34