Maths Olympiad Prep

Library / /2 of 37

Algebra Difficulty 7.3 National olympiad, round 2 Find the answer

Let \lfloor \bullet \rfloor denote the floor function. For nonnegative integers aa and bb, their [i]bitwise xor[/i], denoted aba \oplus b, is the unique nonnegative integer such that a2k+b2kab2k \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 k0k \ge 0. Find all positive integers aa such that for any integers x>y0x>y\ge 0, we have xaxyay. x\oplus ax \neq y \oplus ay.

[i]Carl Schildkraut[/i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let \lfloor \bullet \rfloor denote the floor function. For nonnegative integers aa and bb, their bitwise xor, denoted aba \oplus b, is the unique nonnegative integer such that
a2k+b2kab2k \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 k0k \ge 0. We aim to find all positive integers aa such that for any integers x>y0x > y \ge 0, we have
xaxyay. x \oplus ax \neq y \oplus ay.

To solve this, we consider two cases based on the parity of aa:

1. **Case 1: aa is even**

Suppose aa is even. Then a=2ma = 2m for some integer mm. Consider xx and yy such that x>y0x > y \ge 0. We have:
xax=x2mx x \oplus ax = x \oplus 2mx
yay=y2my y \oplus ay = y \oplus 2my

Since aa is even, 2m2m is also even. The bitwise xor operation with an even number does not change the parity of the number of 1's in the binary representation. Therefore, x2mxx \oplus 2mx and y2myy \oplus 2my will have the same parity, leading to a contradiction. Hence, for aa even, it is not possible to satisfy the given condition.

2. **Case 2: aa is odd**

Suppose aa is odd. Then a=2m+1a = 2m + 1 for some integer mm. Consider x=2k1x = 2^k - 1 and y=2k+1y = 2^k + 1 for sufficiently large kk. We have:
xax=(2k1)(2m+1)(2k1) x \oplus ax = (2^k - 1) \oplus (2m + 1)(2^k - 1)
yay=(2k+1)(2m+1)(2k+1) y \oplus ay = (2^k + 1) \oplus (2m + 1)(2^k + 1)

Since aa is odd, the bitwise xor operation with an odd number will change the parity of the number of 1's in the binary representation. Therefore, xaxx \oplus ax and yayy \oplus ay will not have the same parity, satisfying the given condition.

Thus, the only positive integers aa that satisfy the given condition are the odd integers.

The answer is: \boxed{\text{All odd positive integers}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.