f((x XOR f(y)) + y) = (f(x) XOR y) + y

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

f((x XOR f(y)) + y) = (f(x) XOR y) + y

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Janson MO 5 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

the_universe6626

56 posts

the_universe6626

#1 h Feb 21, 2025, 1:23 PM • 1 Y

Y by MathIQ.

Find all functions $f:\mathbb{Z}_{\ge0}\rightarrow\mathbb{Z}_{\ge0}$ such that
$f((x\oplus f(y))+y)=(f(x)\oplus y)+y$ Note: $\oplus$ denotes the bitwise XOR operation. For example, $1001_2 \oplus 101_2 = 1100_2$ .

(Proposed by ja.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5603 posts

#2 h Feb 22, 2025, 3:00 AM

Y by

Does this even work? it feels a bit simple, given that I really only used one thing about xor

The only solution is the identity, which clearly works.

First note that $x \oplus x = 0$ for all nonnegative integers $x$ and that the $\oplus$ operation is commutative.

Now, setting $x = f(y)$ gives that $f(y) = (f(f(y)) \oplus y) + y$ , so $f(f(x)) \oplus x = f(x) - x$ for all nonnegative integers $x$ . Note that this implies $f(x) \ge x$ for all $x$ .

Now, setting $y = f(x)$ gives that $f((f(x) - x) + f(x)) = f(x)$ , so $f(2f(x) - x) = f(x)$ . Thus, $f(x) = f(2f(x) - x) \ge 2f(x) - x$ , so $x \ge f(x)$ , meaning $f(x) = x$ .

This post has been edited 2 times. Last edited by megarnie, Feb 22, 2025, 5:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#3 h Feb 22, 2025, 4:05 AM • 1 Y

Y by teomihai

Solution from Twitch Solves ISL:

The answer is $f$ the identity, which obviously works.
Let $P(x,y)$ denote the given statement.
Claim: $f(t) \ge t$ for every $t$ .
Proof. Note $P(f(t), t)$ gives $f(t) = f(f(t)) \oplus t + t \ge t$ . $\blacksquare$

Claim: $f(0) = 0$ .
Proof. Note that $P(0,y) \implies y \oplus f(0) + y = f(f(y) + y) \ge f(y) + y \ge 2y.$ Hence $y \oplus f(0) \ge y$ for all integers $y \ge 0$ . This forces $f(0) = 0$ (e.g.\ by taking $y = f(0)$ ). $\blacksquare$
Now, we find that $P(0,y) \implies 2y = f(y+f(y)).$ If $f(y) > y$ for any $y$ , that RHS is at least $2y$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11281 posts

#4 h Apr 3, 2025, 2:13 AM

Y by

Let $P(x,y)$ be the assertion $f((x\oplus f(y))+y)=(f(x)\oplus y)+y$ .
$P(f(x),x)\Rightarrow f(f(x))\oplus x=f(x)-x\Rightarrow f(x)\ge x$
$P(x,f(x))\Rightarrow f(x)=f(2f(x)-x)\ge2f(x)-x\Rightarrow f(x)\le x$
So $\boxed{f(x)=x}$ which fits.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a