4
$\begingroup$

Let $ \mathbb{N}$ denote the set of all positive integers. Find all real numbers $c$ for which there exists a function $f : \mathbb{N} → \mathbb{N}$ satisfying:

  • for any $x, a ∈ \mathbb{N}$, the quantity $\frac{f(x+a)-f(x)}{a} $ is an integer if and only if $a = 1$;
  • for all $x ∈ \mathbb{N}$, we have $|f(x) − cx| < 2023$.

I don't know why but I'm getting feelings that,

  • $f(x+a)-f(x)≡a-1 \pmod {a}$
  • $f(x+a)-f(x) =ax+a-1$

Which gives $$f(x) = \frac{x(x-1)}{2}+c$$

At $a=1$

But that's not the solution. Could someone help me figure it out.

$\endgroup$
1
  • 1
    $\begingroup$ This is a problem from the Indian National Math Olympiad, and there are some solutions at this link. I also tried to post a more detailed solution below. $\endgroup$ Commented Jan 16, 2023 at 19:29

1 Answer 1

3
$\begingroup$

First of all, note that we must have $c \geq 0$. Otherwise $f$ would take negative values, which is impossible.

Now, assume for a $c>1$ there is a function, say $f(x)$, which satisfies both of the two conditions above.

Take $h(x)=f(x)-x$; then $h(x)$ satisfies the first condition, and clearly $|h(x)-(c-1)x|<2023.$ To make sure that $h(x)$ is a function from natural numbers into natural numbers, we add a sufficiently large constant $M$ to $h(x)$; in other words we re-define $h(x)$ as $h(x)=f(x)-x+M$. Observe that such an $M$ definitely exists since $f(x)-x$ is eventually positive because of $|f(x)-cx|<2023$ and $c>1$.

Now, for $c-1$, $h(x)=f(x)-x+M$ satisfies the first condition, and $|h(x)-(c-1)x|<2023+M$.

Therefore, WLOG, we may assume that $0\leq c \leq 1$, and we are looking for a function $f$ such that it satisfies the first condition and $|f(x)-cx|$ is bounded.

Now, having the assumption above, by the same reasoning, we may assume, moreover, that $0\leq c\leq\frac{1}{2}$. To clarify more, if $f(x)$ works for $c$, then $x-f(x)+M$ works for $1-c$, where $M$ is a sufficiently large constant which definitely exists ($M$ is added to make sure that $x-f(x)+M$ is into natural numbers).

On the other hand, if $0 \leq c <\frac{1}{2}$, such an $f$ does not exist. If such an $f$ existed; as $|f(x)-cx|< K$ (bounded), consider $f(1), f(2), ..., f(N)$ which lay inside $[1,cN+K]$. Since $0\leq c<\frac{1}{2}$, for a sufficiently large $N$, at least three of $f(1), f(2), ..., f(N)$ would be the same which violates the first condition (the generated integer would be zero).

Therefore, $c$ should be $\frac{1}{2}.$ For $c=\frac{1}{2}$, take $f=[\frac{x}{2}]+1.$

Hence, all possible values are $n+\frac{1}{2}$, where $n$ is a natural number.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .