2
$\begingroup$

Given $k, n > 0$, how many ordered lists $a_1, a_2, \dots, a_k$ are there such that $a_i \geq 0$ for all $i$, such that $\sum_i a_i = n$ and $\oplus_i a_i = 0$, where the latter operation denotes bitwise xor (i.e. $15 \oplus 3 = 12$).

It is likely there is no closed-form expression, in that case a reasonably fast algorithm would also be interesting.

EDIT: Context: this is the number of losing starting positions in a game of Nim with $k$ initial piles containing a total of $n$ stones.

$\endgroup$
3
  • 2
    $\begingroup$ See section 5 of Tanya Khovanova and Joshua Xiong, "Nim Fractals", arxiv.org/abs/1405.5942, in particular Theorem 27. $\endgroup$
    – Michael Lugo
    Commented Jan 10, 2019 at 20:22
  • $\begingroup$ @MichaelLugo Thanks, that's pretty good. It only gives $n$ even though. $\endgroup$
    – Timon Knigge
    Commented Jan 10, 2019 at 21:32
  • 1
    $\begingroup$ Aha, but if $n \equiv 1 \mod 2$ then there is an odd number of odd sized piles and the nim sum is never $0$. $\endgroup$
    – Timon Knigge
    Commented Jan 10, 2019 at 21:36

1 Answer 1

Reset to default
1
$\begingroup$

Let $F(n,k,x)$ denote the amount of ordered lists $a_1,...,a_k$ such that $a_i\geq0$, $\sum a_i=n$ and $\oplus a_i=x$. Then considering all possible values of $a_k$ we find the recursive formula $$F(n,k,x)=\sum_{i=0}^nF(n-i,k-1,x\oplus i).$$ This gives us an $\mathcal{O}(n^3k)$ time algorithm. Not very fast, but at least polynomial in $n$ and $k$.

$\endgroup$
1
  • 1
    $\begingroup$ One can use binary doubling (as in squaring by exponentiation) to get this to $O(n^3 \log k)$. Still very slow though. $\endgroup$
    – Timon Knigge
    Commented Jan 10, 2019 at 20:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .