Let $\lfloor \bullet \rfloor$ denote the floor function. For nonnegative integers $a$ and $b$, their bitwise xor, denoted $a \oplus b$, is the unique nonnegative integer such that $$ \left \lfloor \frac{a}{2^k} \right \rfloor+ \left\lfloor\frac{b}{2^k} \right\rfloor - \left\lfloor \frac{a\oplus b}{2^k}\right\rfloor$$is even for every $k \ge 0$. Find all positive integers $a$ such that for any integers $x>y\ge 0$, we have \[ x\oplus ax \neq y \oplus ay. \] Carl Schildkraut
Problem
Source: USA Team Selection Test for IMO 2023, Problem 4
Tags: floor function, algebra, function, USA TST, USA TST 2023
16.01.2023 20:03
Solved with megarnie The answer is all even $a$. Let $f(a,b) = a\oplus b$ and $g(a)$ denote the binary representation of $a$. First we show that all odd $a$ fail. Claim: $f(2^n - 1, (2^n - 1)(4n - 7)) =(2^n + 1)(4n-8)$ and $f(2^n - 1, (2^n - 1)(4n-9)) = (2^n +1)(4n-10)$ for any positive integer $n\ge 3$. Proof: Notice that the binary representation $f(2^n - 1,x)$ for any $x$ changes all the last $n$ digits of $g(x)$ and keeps the rest the same. If we can write $x = a\cdot 2^n + b$, where $0\le b < 2^n$, we have $f(2^n - 1,x) = a \cdot 2^n + (2^n - 1) - b$. Thus, we have $(2^n - 1)(4n-7) = 2^n(4n - 8) + 2^n - 4n + 7$, which implies \begin{align*} f(2^n - 1, (2^n - 1)(4n-7)) \\ = 2^n(4n-8) + (2^n - 1)- (2^n - 4n + 7) \\ = (2^n + 1)(4n-8) \\ \end{align*} Similarly, we have \begin{align*} f(2^n - 1, (2^n - 1)(4n-9)) \\ = 2^n(4n-10) + (2^n - 1)- (2^n - 4n + 9) \\ = (2^n + 1)(4n-10) ,\\ \end{align*}as desired. Claim: $f(2^n + 1, (2^n + 1)(4n-7)) = (2^n + 1)(4n-8)$ and $f(2^n + 1, (2^n + 1)(4n-9)) = (2^n + 1)(4n-10)$ for all $n\ge 3$. Proof: Notice that the binary representation $f(2^n - 1, x)$ for $x$ with at least $n+1$ digits changes the last digit and digit in the $2^n$th place of $g(x)$. If we can write $x = a\cdot 2^n + b$ for odd $a,b$, we have $f(2^n - 1,x) = a\cdot 2^n + b - 2^n - 1$. Thus, we get $(2^n + 1)(4n-7) = 2^n(4n-7) + 4n-7$, so \begin{align*} f(2^n + 1, (2^n +1)(4n-7)) \\ = 2^n(4n-7) + 4n-7 - 2^n - 1 \\ = (2^n + 1)(4n-8) \\ \end{align*} Similarly, we can find that $f(2^n + 1, (2^n + 1)(4n-9)) = (2^n + 1)(4n-10)$. Thus, $f(2^n - 1, (2^n - 1)(4n-7)) = f(2^n +1, (2^n + 1)(4n-7))$ and $f(2^n -1, (2^n - 1)(4n-9)) = f(2^n + 1, (2^n + 1)(4n-9))$, which implies that all odd $a>1$ fail. To see that $a=1$ fails, note that $f(x,x) = 0$ for all $x$. Next we show that all even $a$ work. Let $a = 2t$. Claim: If $f(x,2tx) = f(y,2ty) = m $, then $x\equiv y\pmod{2^n}$ for any positive integer $n$. Proof: We induct on $n$. The base case $n=1$ is obvious by taking $\pmod 2$. Suppose we have $x\equiv y\pmod{2^k}$. Then we note that $2tx - 2ty = 2t(x-y)$, so $2tx\equiv 2ty\pmod{2^{k+1}}$. This means the last $k+1$ digits in $g(2tx)$ and $g(2ty)$ are the same. Since the last $k+1$ digits in $g(m)$ are fixed, we know the last $k+1$ digits in $g(x)$ and $g(y)$ must be the same, so $x\equiv y\pmod{2^{k+1}}$, which completes the induction. For any $x,y$ satisfying $f(x,ax) = f(y,ax)$, we have $x-y$ has infinitely many divisors, so $x=y$, contradiction. Thus, all even $a$ work and we are done.
16.01.2023 20:03
We claim the answer is all even integers $a$. If $a$ is odd, let $k=1+\lfloor\log_2 a\rfloor$ and consider the numbers $x,y=2^k\pm 1$. We claim that \[x\oplus y=ax\oplus ay\]Indeed, if we consider the natural map from $\mathbb Z_{2^\infty}\to\mathbb F_2^\infty$, we have \[f(a\oplus b)=f(a)+f(b)\]In particular, \[f(2^k-1)=(\underbrace{1,1,\ldots,1}_{k~1\text{'s}},0,\ldots)\]\[f(2^k+1)=(1,\underbrace{0,\ldots,0}_{k-1~0\text{'s}},0,\ldots)\]so \[f((2^k-1)\oplus(2^k+1))=f(2^k-1)+f(2^k+1)=(0,\underbrace{1,1,\ldots,1}_{k~1\text{'s}},0,\ldots)\]Now, let $a=\overline{a_ka_{k-1}\ldots a_0}_2$ in binary (note $a_0=1$), then we know in binary \[(2^k+1)a=\overline{a_ka_{k-1}\ldots a_0a_ka_{k-1}\ldots a_0}\]\[(2^k-1)a=\overline{a_ka_{k-1}\ldots a_1(a_0-1)(1-a_k)(1-a_{k-1})\ldots (1-a_1)a_0}\]Thus, \[f(a(2^k-1)\oplus a(2^k+1))=f(a(2^k-1))+f(a(2^k+1))=(0,\underbrace{1,1,\ldots,1}_{k~1\text{'s}},0,\ldots)\]as desired. Now, if $a=2b$ is even, we claim this is impossible. In particular, assume that $k$ is the smallest integers such that $f(x)[k]\neq f(y)[k]$. Then, we know that $f(x\oplus y)[k]=f(x)[k]+f(y)[k]=1$, and for all $0\leq j<k$, $f(x\oplus y)[j]=f(x)[j]+f(y)[j]=0$. However, as the last $k$ digits of $bx$ and $by$ only depend on the last $k$ digits of $x$ and $y$, we know \[f(bx)[k-1]=f(by)[k-1]\]However, this means $f(ax)[k]=f(ay)[k]$, so $f(ax\oplus ay)[k]=f(ax)[k]+f(ay)[k]=0$, so \[x\oplus y\neq ax\oplus ay\]
16.01.2023 20:15
17.01.2023 04:09
We omit proofs of well-known properties of the bitwise xor. The answer is even $a$ only. We first provide a construction for odd $a$. Pick some massive $n\gg a$, and consider $(x,y)=(2^n+1,2^n-1)$. Write the binary representation of $a$ as $\overline{b_k\ldots b_1}$. Note that $k \ll n$ and $b_1=1$. Then the binary representation of $ax$ is $$\overline{b_k\ldots b_1\underbrace{0\ldots 0}_{n-k\text{ zeroes}}b_k\ldots b_1}=\overline{b_k\ldots 1\underbrace{0\ldots 0}_{n-k\text{ zeroes}}b_k\ldots 1},$$and the bitwise xor of this with $x$ is then $$\overline{b_k\ldots 0\underbrace{0\ldots 0}_{n-k\text{ zeroes}}b_k\ldots 0}.$$The binary representation of $ay$ is slightly more complicated. First, the binary representation of $a(y+1)$ is simply $$\overline{b_k\ldots b_1\underbrace{0\ldots 0}_{n\text{ zeroes}}}.$$We wish to subtract $a$ from this. To do so, simply borrow a digit and put it back: \begin{align*} ay=a(y+1)-a&=\overline{b_k\ldots 1\underbrace{0\ldots 0}_{n\text{ zeroes}}}-\overline{b_k\ldots b_1}\\ &=\overline{b_k\ldots 0\underbrace{1\ldots 1}_{n\text{ ones}}}+1-\overline{b_k\ldots b_1}\\ &=\overline{b_k\ldots 0\underbrace{1\ldots 1}_{n-k\text{ ones}}b_k'\ldots b_1'}+1\\ &=\overline{b_k\ldots 0\underbrace{1\ldots 1}_{n-k\text{ ones}}b_k'\ldots 1}, \end{align*}where $b_i'=1-b_i=1 \oplus b_i$ is the negation of the bit $b_i$, so $b_1'=0$ which gives us the last equality. The bitwise xor of this with $y$ is then $$\overline{b_k\ldots 0\underbrace{0\ldots 0}_{n-k\text{ zeroes}}b_k\ldots 0},$$since $1 \oplus b_i'=b_i$. This concludes the construction. We now prove that all even $a$ fail by inducting on the key claim that if $x \oplus ax=y \oplus ay$ for $a$ even, then $x \equiv y \pmod{2^k}$; that is, the rightmost $k$ bits in $x$ and $y$ are the same. The base case of $k=1$ is clear, since the rightmost bit in $x \oplus ax$ is simply the rightmost bit in $x$, and likewise for $y$. Now if the rightmost $k$ bits of $x$ and $y$ are equal, the rightmost $k+1$ bits of $ax$ and $ay$ are equal, since $a$ is even. Since the $k+1$-th bits—from the right—of $x \oplus ax$ and $y \oplus ay$ are also the same (since they're the same number), it follows that the $k+1$-th bits of $x$ and $y$ are equal, completing the inductive step. The claim then implies that $x=y$: contradiction. We are done. $\blacksquare$
24.01.2023 09:09
Oops, this is just dotted's solution. We claim that the answer is all even $a$ only. We will work mostly in binary. First, we'll show that $x\oplus ax \neq y\oplus ay$ for any $x> y\geq 0$ when $a$ is even. Write $a = 2^i\cdot a'$ where $a'$ is odd and $i>0$, and suppose for the sake of contradiction that $x\oplus ax = y\oplus ay$. This implies that \[x\oplus y = (a'x\oplus a'y \text{ concatenated with $i$ zeroes}).\]Let $2^k$ be the largest power of two dividing $x-y$ (and also the largest power of two dividing $a'x \oplus a'y$). It is then clear that $x\oplus y$ and $a'x\oplus a'y$ end in exactly $k$ zeroes, but this is a contradiction since $i>0$. Now, for odd $a$, let $k$ be the length of $a$ in binary; we will use $x=2^k-1$ and $y= 2^k+1$. Write $a=(d_1d_2 \cdots d_k)_2$ in binary. Since $a$ is odd, $d_k=1$. We have \[ax = \overline{d_1d_2 \cdots d_k \underbrace{0\cdots 0}_k} - \overline{d_1d_2 \cdots d_k} = \overline{d_1d_2 \cdots d_{k-1} 0(1-d_1)(1-d_2)\cdots (1-d_{k-1}) d_k},\]so \[ax\oplus \overline{\underbrace{1\cdots 1}_k} = \overline{d_1d_2\cdots d_{k-1}0d_1d_2\cdots d_{k-1}0}.\]The other value, $y\oplus ay$, is easier: \[ay = \overline{d_1d_2 \cdots d_k\underbrace{0\cdots 0}_k} + \overline{d_1d_2 \cdots d_k} = \overline{d_1d_2 \cdots d_kd_1d_2 \cdots d_k},\]so \[ay \oplus \overline{1\underbrace{0\cdots 0}_{k-1} 1}= \overline{d_1d_2 \cdots d_{k-1}0d_1d_2\cdots d_{k-1}0}.\] Indeed, $x\oplus ax = y\oplus ay$, so odd $a$ do not satisfy the condition.
17.03.2024 11:14
This is pretty cool. Note that we may write $x \oplus ax = y \oplus ay$ as $x \oplus y = ax \oplus ay$ by moving stuff around on both sides. Claim: $\nu_2(m \oplus n) = \nu_2(m-n)$ for all $m,n \in \mathbb{N}$. Note that $\nu_2(x)$ is the smallest integer $k$ where the $k$'th bit from the left in the binary expansion of $x$ is $1$. The fact above becomes clear when you look at the base-2 expansions of both $m \oplus n$ and $m-n$. $\square$ Thus, \[ \nu_2(x-y) = \nu_2(x \oplus y) = \nu_2(ax \oplus ay) = \nu_2(ax-ay) = \nu_2(a) + \nu_2(x-y) \]\[ \implies \nu_2(a)=0. \]So, $a$ is odd. For construction, it is easy to see by just expanding that $x=2^N-1$ and $y=2^N+1$ works for all large $N$.
14.11.2024 11:12
Wow what a problem. The answer is $a$ even. First I show neccessity We rewrite the condition $x \oplus ax = y \oplus ay$ as $x \oplus y = ax \oplus ay$ as we can repeateadly apply the following fact: $a\oplus b=c\iff b\oplus c=a$ Claim: $\nu_2(m \oplus n) = \nu_2(m-n)$ for all $m,n \in \mathbb{N}$. Proof Sketch. We have that $\nu_2(x)$ is the smallest integer $k$ where the $k$th bit from the left in the binary expansion of $x$ is $1$. After this, the claim becomes clear after comparing the binary expansions of $m-n$ and $m\oplus n$. $\blacksquare$ Now from the claim, we get: \begin{align*} \nu_2(x-y)=\nu_2(x\oplus y)&=\nu_2(ax\oplus ay)\\ &=\nu_2(ax-ay)\\ &=\nu_2(x-y)+\nu_2(a)\\ &\implies \nu_2(a)=0 \end{align*}and thus we get that the function $f(x)=x\oplus a$ is only injective when $a$ is even For the construction when $a$ is odd, we can check that $x=2^N-1$ and $y=2^N+1$ works for large enough $N$, which finishes!!!!!!!!!!!!!!!!