Kvant Math Problem 2876

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 10m12s
Source on kvant.digital

Problem

Let $f_{a,b}(x)=[ax+b]$. For which pairs of real $a\gt0$ and $b$ do there exist real $c\gt0$ and $d$ such that for all natural $n$ the equality $f_{c,d}\big(f_{a,b}(n)\big)=n$ holds?

I. Dorofeev

Southern Mathematical Tournament (XX)

Exploration

We study functions of the form $f_{a,b}(n)=\lfloor an+b\rfloor$ with $a>0$ acting on $\mathbb{N}$.

The condition

$$f_{c,d}(f_{a,b}(n))=n \quad \text{for all } n\in\mathbb{N}$$

implies that $f_{a,b}$ is injective on $\mathbb{N}$ and $f_{c,d}$ is its inverse on $\mathbb{N}$. Hence $f_{a,b}$ must be a bijection $\mathbb{N}\to\mathbb{N}$.

Thus the problem reduces to classifying affine floor maps that permute $\mathbb{N}$ and whose inverse is again of the same form.

The main tension is between growth and discreteness. If $a>1$, values grow too quickly and leave gaps. If $0<a<1$, values repeat and destroy injectivity. The only viable candidate is $a=1$, where $f(n)=\lfloor n+b\rfloor$, which behaves like a shift. The subtle point is whether a non-integer shift can still be bijective in disguise, or whether integer shifts other than zero can be compatible with an inverse of the same form.

The decisive step is proving that bijectivity forces both injectivity and surjectivity simultaneously, eliminating all nontrivial shifts.

Problem Understanding

This is a Type A problem. We must determine all pairs $(a,b)$ for which there exist $c>0$ and $d$ such that

$$\lfloor c\lfloor an+b\rfloor + d\rfloor = n \quad \text{for all } n\in\mathbb{N}.$$

The composition condition forces $f_{a,b}$ to be a bijection of $\mathbb{N}$ with inverse also of affine-floor type. The key difficulty is classifying when a floor-linear map can permute all natural numbers without gaps or repetitions.

The expected conclusion is that only the identity map survives these rigidity constraints.

Proof Architecture

The first lemma asserts that the existence of $c,d$ implies $f_{a,b}$ is bijective on $\mathbb{N}$, since it has a two-sided inverse given by another function.

The second lemma proves that if $f_{a,b}(n)=\lfloor an+b\rfloor$ is injective on $\mathbb{N}$, then $a\le 1$, since $a>1$ forces strict expansion and creates gaps, while $a<1$ forces repetitions.

The third lemma shows that if $a=1$, then $f(n)=\lfloor n+b\rfloor$ is bijective only when $b=0$, since any nonzero shift destroys surjectivity onto $\mathbb{N}$.

The hardest step is ruling out exotic cancellations where $a\ne 1$ but flooring might artificially restore bijectivity.

Solution

Assume there exist $c>0$ and $d\in\mathbb{R}$ such that for all $n\in\mathbb{N}$,

$$\lfloor c\lfloor an+b\rfloor + d\rfloor = n.$$

Denote $f(n)=\lfloor an+b\rfloor$ and $g(x)=\lfloor cx+d\rfloor$. Then the condition is $g(f(n))=n$ for all $n\in\mathbb{N}$.

Step 1: Bijectivity of $f$ on $\mathbb{N}$

For every $n$, the value $n$ lies in the image of $g$ restricted to $f(\mathbb{N})$. Since $g$ is a function defined on all integers, the identity $g(f(n))=n$ implies that $f(n_1)=f(n_2)$ would yield

$$n_1=g(f(n_1))=g(f(n_2))=n_2,$$

so $f$ is injective on $\mathbb{N}$.

For surjectivity, for every $n$ there exists $m=f(n)$ such that $g(m)=n$. Thus every $n$ is in the image of $g\circ f$, and since $g$ is defined on integers, this forces $f(\mathbb{N})$ to contain exactly one preimage under $g$ for each $n$, so $f$ must map $\mathbb{N}$ onto an infinite subset on which $g$ is injective and covers all $\mathbb{N}$. In particular, $f$ is a bijection between $\mathbb{N}$ and $f(\mathbb{N})$, and $g$ restricts to its inverse. Hence $f$ is a bijection $\mathbb{N}\to\mathbb{N}$.

Thus $f$ is a permutation of $\mathbb{N}$.

Step 2: Excluding $a>1$

If $a>1$, then

$$f(n+1)-f(n)\ge \lfloor a(n+1)+b\rfloor - (a n + b -1)$$

implies asymptotic growth at least $a$, so increments are at least $1$ frequently and eventually strictly greater than $1$ infinitely often. More directly, for any $n$,

$$f(n+1)\ge a(n+1)+b-1 = an+b + (a-1).$$

Since $a-1>0$, for all sufficiently large $n$,

$$f(n+1)\ge f(n)+1,$$

and in fact strict growth occurs with gaps. Thus the image omits infinitely many integers, contradicting surjectivity of a permutation of $\mathbb{N}$. Hence $a\le 1$.

Step 3: Excluding $0<a<1$

If $0<a<1$, then for all $n$,

$$an+b \le a(n+1)+b < an+b+1.$$

Hence $\lfloor an+b\rfloor$ is either constant or repeats values over arbitrarily long intervals, so $f(n)=f(n+1)$ for infinitely many $n$, contradicting injectivity. Hence $a\ge 1$.

From Steps 2 and 3, we conclude $a=1$.

Step 4: Determining $b$

Now $f(n)=\lfloor n+b\rfloor$. Write $b=k+\varepsilon$ with $k\in\mathbb{Z}$ and $\varepsilon\in[0,1)$.

Then

$$f(n)=\lfloor n+k+\varepsilon\rfloor = n+k.$$

If $k\ne 0$, then $f(\mathbb{N})=\mathbb{N}+k$, which is either missing the first $k$ positive integers when $k>0$ or contains nonpositive integers when $k<0$, so it is not a permutation of $\mathbb{N}$. Since $f$ must be a bijection of $\mathbb{N}$, we obtain $k=0$, hence $b=0$.

Thus $f(n)=n$.

Step 5: Existence of $c,d$

If $f(n)=n$, then choosing $c=1$ and $d=0$ gives

$$\lfloor c\lfloor n\rfloor + d\rfloor = n,$$

so the condition is satisfied.

Therefore the only admissible pair is $(a,b)=(1,0)$.

$$\boxed{(a,b)=(1,0)}$$

Verification of Key Steps

The exclusion of $a>1$ relies on the growth estimate $f(n+1)\ge f(n)+1$ eventually, which forces unbounded gaps in the image; any such gap contradicts surjectivity of a permutation of $\mathbb{N}$.

The exclusion of $0<a<1$ rests on the inequality $an+b< a(n+1)+b<an+b+1$, which guarantees that two consecutive integers share the same floor value infinitely often, contradicting injectivity.

The reduction from $b=k+\varepsilon$ to $f(n)=n+k$ uses the fact that adding a fractional part does not affect the floor when applied to integers.

Alternative Approaches

One can instead argue via density: the asymptotic density of ${\lfloor an+b\rfloor}$ equals $1/a$. Since a permutation of $\mathbb{N}$ must have density $1$, this forces $a=1$, after which integer shift analysis yields $b=0$. Another approach uses Beatty sequence theory to show that any nontrivial scaling produces complementary partitions rather than permutations, again isolating the identity as the only possibility.