# Optimal Strategy for a 2 player game

• 2 players A & B are playing a game involving a number n
• Player A makes the first move & both players play alternately.
• In each move the player takes the number n,chooses a number i such that 2^i < n and replaces n with k = n - 2^i iff the number of 1s in the binary representation of k is greater than or equal to the number of 1s in the binary representation of n
• Game ends when no player can make a move, ie there does not exist such an i

For example:

````n = 13 = b1101
````

Only possible i=1

````k = n - 2^i = 11 = b1011
````

Again,only possible i = 2

````k = n - 2^i = 7 = b111
````

Since Player A cant make any more moves, Player B wins

I've deduced that at any step,we can only choose an i,such that there is a 0 at the corresponding position in the binary representation of n.

For Example: if n=1010010,then i can only be {0,2,3,5}.

But I cant move any further.A minimax algorithm isnt exactly striking me.I would appreciate any help.Thanks in advance

-

## 1 Answer

It’s a disguised version of Nim. Each block of consecutive $0$’s in the binary representation of $n$ is a pile. For example, from $10000_2$ you can subtract $8$ to get $1000_2$; $4$ to get $1100_2$; $2$ to get $111_2$; or $1$ to get $1111_2$. These moves correspond to reducing a pile of $4$ stones to $3$, $2$, $1$, or $0$ stones, respectively. I’ll leave it to you to fill in the details. You probably already know the strategy for Nim.

(This is a cute variant; I’d not seen it before.)

-

This doesn't seem right, since the removal of zeroes from one block will create new zeroes in the next block to the left. The value of $1010_2$, for instance, is $*$, not $0$, even there are two equal "piles" of zeroes in that number. – Théophile Sep 24 '12 at 23:50
@Théophile: You’re right: I was concentrating so much on the case of adjacent $1$’s that I forgot that the piles get amalgamated in the basic case! – Brian M. Scott Sep 25 '12 at 0:03
I’ll revise this when I get back. – Brian M. Scott Sep 25 '12 at 0:10
It seems that every position has value $0$, $*$, or $*2$. – Théophile Sep 25 '12 at 0:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9214154481887817, "perplexity_flag": "middle"}