-2
$\begingroup$

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.

Additional rule

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?

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

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @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. $\endgroup$
    – Set Big O
    Feb 13, 2015 at 16:56
  • $\begingroup$ 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. $\endgroup$
    – Matthew Read
    Feb 13, 2015 at 16:59
  • $\begingroup$ That was fast ! $\endgroup$
    – ghosts_in_the_code
    Feb 14, 2015 at 10:35
2
$\begingroup$

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. enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 . $\endgroup$
    – Abr001am
    Feb 14, 2015 at 22:34

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.