3
$\begingroup$

I have been researching this variant of Nim. I have been unable to prove the following claim. What is annoying is that I feel I am missing something really obvious. Does anyone have any ideas on how to solve this:

Let's first say that one position dominates another if all its corresponding pile sizes are at least as great. Note that the positions must be distinct. For example, $(1,2,4)$ dominates $(0,1,4)$ whereas $(5,8,7)$ does not dominate $(4,2,8)$.

Here is the actual problem. Let $m$ be a positive odd integer and $\oplus$ denote the bitwise xor. Let $a,b,c$ be non-negative integers with the following conditions:

  1. $a \oplus b \geq m$
  2. $0 < a < \frac{m}{2} \leq b < m \leq c$

Show that for all integers $0 \leq i < m$, there exists a position $(a^\prime,b^\prime,c^\prime)$ dominated by $(a,b,c)$ such that:

  1. $a^\prime + b^\prime + c^\prime = 2i$
  2. $a^\prime \oplus b^\prime \oplus c^\prime = 0$
$\endgroup$
14
  • 1
    $\begingroup$ Note that $c'=a'\oplus b'$ yields $a'+b'+c'=a'+b'+(a'\oplus b')=2(a'\cdot b')=2i$, so $(a',b',c')$ is $(a',b',a'\oplus b')$ with $a'\cdot b'=i$ (where $\cdot$ denotes bitwise or). $\endgroup$
    – joriki
    Commented Jul 3, 2015 at 5:25
  • 1
    $\begingroup$ Are you saying that the dominance of $c$ over $c'=a'\oplus b'$ would then be guaranteed? That's not obvious to me. $\endgroup$
    – joriki
    Commented Jul 3, 2015 at 5:35
  • 1
    $\begingroup$ That seems right; I think it should be $c\ge m$ and $a+b+c\ge 2m$, but the conclusion remains valid. This means that $(a',b')$ doesn't have to be strictly dominated by $(a,b)$; we can allow $(a',b')=(a,b)$, since $c$ strictly dominates $c'$. $\endgroup$
    – joriki
    Commented Jul 3, 2015 at 5:48
  • 1
    $\begingroup$ Since $a'\oplus b'\oplus c'=0$ says that either $0$ or $2$ bits in $a',b',c'$ are set in each position and $a'\cdot b'=i$ says that $0$ bits in $a',b'$ at a position are set iff the corresponding bit of $i$ is not set, we can view the bits set in $i$ as specifying the positions in which $a',b',c'$ have $2$ bits set. $\endgroup$
    – joriki
    Commented Jul 3, 2015 at 5:51
  • 1
    $\begingroup$ So if $i'\cdot i=i'$, a solution for $i'$ yields a solution for $i$ (by clearing the corresponding bits in $a',b',c'$). So we only need to check the $i$ values that don't have such an $i'\neq i$. $\endgroup$
    – joriki
    Commented Jul 3, 2015 at 5:56

1 Answer 1

Reset to default
1
$\begingroup$

Choose $c'=a'+b'=a'\oplus b'=i$. Then at each position, exactly $0$ or $1$ bits are set in $a'$ and $b'$ depending on whether the corresponding bit in $i$ is set. It remains to be decided how to distribute the set bits in $i$ over $a'$ and $b'$. Obtain $a',b'$ from $a,b$ as follows: Clear all bits that are cleared in $i$. Since $a\oplus b\ge m\gt i$, the most significant bit change from $a\oplus b$ to $i$ is $1\to0$, and that bit was set and gets cleared in one of $a'$ and $b'$, say, $a'$. Change all bits in $a'$ that are set in $i$ but not in $a\oplus b$.

Since the most significant changed bit is worth more than all less significant changes added together, we have $a'\le a$ and $b'\le b$, and also $c'=i\lt m\lt c$, so $(a',b',c')$ thus constructed is dominated by $(a,b,c)$. Note that $a\lt\frac m2\le b\lt m$ hasn't been used.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you so much. I really appreciate it. $\endgroup$
    – Halbort
    Commented Jul 3, 2015 at 13:57

You must log in to answer this question.

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