Decimal functions in binary

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

Decimal functions in binary

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India TST 2023 Day 3 P1

The post below has been deleted. Click to close.

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

35 posts

#1 h Jul 9, 2023, 6:21 AM • 4 Y

Y by GeoKing, CahitArf, Supercali, Siddharth03

Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(x) + y$ and $f(y) + x$ have the same number of $1$ 's in their binary representations, for any $x,y \in \mathbb{N}$ .

This post has been edited 2 times. Last edited by Pranav1056, Jul 9, 2023, 6:22 AM

Z K Y

The post below has been deleted. Click to close.

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

1263 posts

#2 h Jul 27, 2023, 7:43 AM • 2 Y

Y by Om245, thepassionatepotato

A story about this problem: It was originally meant to be D3 P3 (basically the hardest problem in the TSTs), but a few days before the test, some of us found an easier solution while trying. Hence the problem had to be demoted to D3 P1. D4 P3 at that time, which was a very hard geo, was shifted to D3 P3 (I think it was more suitable for that position anyway), and we had to use the shortlist for D4 P3. Anyway, I think this is a very cute problem.

Here is the solution that we found:

For $n\in\mathbb N$ , let $d(n)$ denote the number of $1$ 's in the binary representation of $n$ . Let $P(x,y)$ denote the statement that $f(x)+y$ and $f(y)+x$ have the same number of $1$ 's in their binary representation.

Claim 1: For any $y,n \in \mathbb{N}$ with $2^n>f(y)$ , $f(2^n-f(y))+y$ is a power of two.
Proof: $P(2^n-f(y),y)$ gives us that $2^n$ and $f(2^n-f(y))+y$ have the same number of $1$ 's, and the former has exactly one $1$ , so $f(2^n-f(y))+y$ has exactly one $1$ , from which the claim follows. $\blacksquare$

Claim 2: $f(y+2^k)-f(y)$ is a power of two for any $k \geq 0$ and $y \geq 2^k$ .
Proof: Choose an $n$ such that $n>1000+\log_2(10+|f(y+2^k)-f(y)|)$ . By Claim 1, $f(2^n-f(y))=2^t-y >0$ for some $t$ with $t \geq k+1$ . Therefore $P(2^n-f(y),y+2^k)$ gives $d(2^n-f(y)+f(y+2^k))=d(2^t+2^k)=2$ since $t \geq k+1$ . If $f(y)=f(y+2^k)$ , then LHS is $d(2^n)=1$ , contradiction! If $f(y)>f(y+2^k)$ , and $f(y)-f(y+2^k)$ has $m<\log_2(10+|f(y+2^k)-f(y)|)$ digits, then $d(2^n-f(y)+f(y+2^k)) \geq n-m-1 \geq 999>2$ since $2^n-f(y)+f(y+2^k)$ starts with at least $n-m-1$ ones, contradiction! Therefore $f(y+2^k)>f(y)$ , and since $n$ is bigger that the number of digits in $f(y+2^k)-f(y)$ , there is no carry-over, so
$2=d(2^n-f(y)+f(y+2^k))=1+d(f(y+2^k)-f(y))$ which gives us $f(y+2^k)-f(y)$ is a power of $2$ , as required. $\blacksquare$

Claim 2 gives us $f(y+1)-f(y)=2^{t(y)}$ for some $t(y)$ , for all $y$ . But for $y \geq 2$ , $f(y+2)-f(y)$ is also a power of two $\implies$ $2^{t(y)}+2^{t(y+1)}$ is a power of two, which is only possible if $t(y)=t(y+1)$ for all $y \geq 2$ . Therefore $f(y+1)-f(y)$ is a constant power of two for all $y \geq 2$ , say $2^k$ . This gives us $f(y)=2^ky+c$ for some constant $c$ , for all $y \geq 2$ . Putting this in Claim 1, we get
$2^{k+n}-(2^{2k}-1)y-(2^k-1)c$ is a power of two for any $y \geq 2$ and any sufficiently large $n$ . This is only possible if, for all $y \geq 2$ ,
$(2^{2k}-1)y+(2^k-1)c=0$ $\iff (2^k-1)((2^k+1)y+c)=0$ which can only hold for all $y \geq 2$ if $2^k=1$ , i.e., $f(y)=y+c$ for all $y \geq 2$ . But Claim 1 for $y=1$ and large $n$ gives
$2^n-f(1)+1+c$ is a power of two for all sufficiently large $n$ , which is only possible if $f(1)=1+c$ . Therefore the only solutions are
$\boxed{f(x)=x+c \ \ \forall x \in \mathbb{N}}$ where $c$ is a non-negative integer.

This post has been edited 3 times. Last edited by Supercali, Jul 27, 2023, 7:50 AM

Z K Y

The post below has been deleted. Click to close.

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

1351 posts

i3435

#3 h Aug 3, 2023, 12:57 PM • 2 Y

Y by GeoKing, Om245

$P(2^n-f(x),x)$ means $x=2^k-f(2^n-f(x))$ for some $k$ , for all $x,n$ . $P(2^a+2^k-f(x),x)$ means that $f(2^a+2^k-f(x))+x$ is of the form $2^c+2^d$ , where $c\neq d$ when $a\neq k$ and $c=d$ when $a=k$ . Replacing $x$ in the previous equation with $2^n-f(x)$ , $f(2^a+x)+2^n-f(x)$ either has one or two ones in its binary representation. If you make $n$ large, we get that $f(2^a+x)-f(x)$ is a power of two for all $a,x$ . In the same manner as the previous post, you can get $f(x)=2^kx+c$ for some $k,c$ . $P(x,2^kx)$ means $2^{k+1}x+c$ and $(2^{2k}+1)x+c$ have the same number of $1$ 's in their binary representation. If $x$ is a large power of $2$ , then the second one will have one more $1$ than the first one unless $k=0$ . Thus $k=0$ and $f(x)=x+c$ , which works.

Z K Y

The post below has been deleted. Click to close.

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

273 posts

#4 h May 23, 2025, 3:27 PM

Y by

Let $P(x,y)$ denote the assertion. Call $2$ such numbers quirky.

$P(2^n-f(y),y)$ gives us $f(2^n-f(y))+y=2^{g(n,y)}$ for any $n>f(y)$ where $g: \mathbb{N}^2 \to \mathbb N$ is a function. See that $g(n,y)$ is unbounded.

Claim: $f(x+2^\ell)-f(x)$ is a power of $2$ for any $\ell \ge 0$ and $x \ge 2^\ell$ .
Proof: $P(x+2^\ell,2^n-f(x))$ gives us that $f(x+2^\ell)+2^n-f(x)$ and $2^{g(n,x)}+2^\ell$ are quirky.

Now $2^{g(n,x)}>2^\ell$ so $f(x+2^\ell)+2^n-f(x)=2^{g_1(n,x,\ell)}+2^{g_2(n,x,\ell)}$ where $g_1$ , $g_2: \mathbb{N}^3 \to \mathbb Z _{\ge 0}$ and $g_1(n,x,\ell) \neq g_2(n,x,\ell)$ . Fix $x$ and $\ell$ and we will abuse some notation by letting $g_i(n,x,\ell)=g_i(n)$ because I am lazy. So we have $\begin{align*} & 2^{g_1(n)}+2^{g_2(n)}-2^n \text{ is constant} \\ \implies & 2^{g_1(n)}+2^{g_2(n)}+2^m=2^{g_1(m)}+2^{g_2(m)}+2^n \end{align*}$ Say $m>ng_1(n)g_2(n)$ and $g_1(n)$ , $g_2(n)$ , $m$ are all distinct and so is $g_1(m)$ , $g_2(m)$ . If $n=g_2(m)$ then LHS have $3$ $1$ 's in their binary representation but RHS has atmost $2$ .

Now as $n \neq m$ so $n \in \{g_1(n),g_2(n)\}$ and hence we get that $2^{g_1(n)}+2^{g_2(n)}-2^n$ is a power of $2$ and so we are done. $\square$

Choose $\ell=0$ and $1$ and easily get that $f(x+1)-f(x)$ is a constant power of $2$ for $x \ge 2$ . By a bit case bash we get that that must be $1$ . And similarly we get that $f(2)-f(1)=1$ as well.

Hence the only solution is $\boxed{f(x) \equiv x+c \text{ } \forall \text{ }x \in \mathbb{N}}$ where $c \ge 0$ ; which obviously works.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a