China MO 2021 P6

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

China MO 2021 P6

G H J

Reveal topic tags

G H BBookmark kLocked kLocked NReply

Source: CMO 2021 P6

The post below has been deleted. Click to close.

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

NTssu

21 posts

NTssu

#1 h Nov 25, 2020, 5:07 AM • 10 Y

Y by A-Thought-Of-God, centslordm, megarnie, gvole, ImSh95, jrsbr, Cookierookie, MathLuis, LNHM, Lale12345

Find $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$ , such that for any $x,y \in \mathbb{Z}_+$ , $f(f(x)+y)\mid x+f(y).$

Z K Y

The post below has been deleted. Click to close.

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

Idio-logy

206 posts

Idio-logy

#2 h Nov 25, 2020, 7:21 AM • 3 Y

Y by Modesti, centslordm, ImSh95

Solution

@post 5

This post has been edited 3 times. Last edited by Idio-logy, Nov 25, 2020, 3:19 PM

Z K Y

The post below has been deleted. Click to close.

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

P1kachu

119 posts

P1kachu

#3 h Nov 25, 2020, 7:31 AM • 2 Y

Y by centslordm, ImSh95

Solution

EDIT: Thanks for pointing that out, @TheUltimate123 !

This post has been edited 6 times. Last edited by P1kachu, Nov 26, 2020, 11:19 AM
Reason: Corrected a mistake, as pointed out below.

Z K Y

The post below has been deleted. Click to close.

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

TheUltimate123

1739 posts

TheUltimate123

#5 h Nov 25, 2020, 10:38 AM • 10 Y

Y by FAA2533, chrono223, Aryan-23, ProblemSolver2048, Mathematicsislovely, mijail, centslordm, ImSh95, SerdarBozdag, math_comb01

Excellent problem! Solved with nukelauncher.

Let $P(x,y)$ denote the assertion. The answers are

$f(x)=x$ for all $x$ ;
$f(x)=1$ for all $x\ge2$ ;
$f(x)\equiv x\pmod2$ for all $x$ , and $f(x)\in\{1,2\}$ for $x\ge2$ .

Claim: $f$ is either injective or bounded

Proof. If $f(a)=f(b)$ but $a<b$ , then by $P(a,y)$ and $P(b,y)$ we know $f(y+f(a))$ divides both $a+f(y)$ and $b+f(y)$ ; hence it divides $b-a$ . It follows that $f(y+f(a))\le b-a$ , so $f$ is bounded. $\blacksquare$

\bigskip

Proof for $f$ injective: This case collapses after proving $f(1)=1$ . Let $a=f(1)$ be larger than 1 for contradiction.

Claim: $f(x+a)=f(x)+1$ for all $x$

Proof. By $P(1,x)$ , $f(x+a)\le f(x)+1$ . Evidently $f(x+a)\ne f(x)$ by injectivity. If instead $f(x+a)<f(x)$ , we will show via induction on $n$ that $f(x+na)<f(x)$ .

If $f(x+na)<f(x)$ then by $P(1,x+na)$ , $f(x+(n+1)a)\le f(x+na)+1\le f(x)$ , but by injectivity $f(x+(n+1)a)\ne f(x)$ , so the inductive step follows.

But $f(x+na)<f(x)$ contradicts injectivity, as desired. $\blacksquare$

Now $f(x+na)=f(x)+n$ for all $x$ , $n$ . Then $f(1+f(2)a)=f(1)+f(2)=f(2+f(1)a)$ , so $1+f(2)a=2+f(1)a$ so $a=1$ .

Finally I claim by induction that $f(n)=n$ for all $n$ . If $f(i)=i$ for all $i\le n$ , then from $P(1,n)$ , $f(n+1)\le f(n)+1=n+1.$ But by injectivity $f(n+1)\notin\{1,\ldots,n\}$ , so $f(n+1)=n+1$ , completing the induction.

\bigskip

Proof for $f$ bounded: Recall from the proof of the claim that if $f(a)=f(b)$ then $f(y+f(a))\mid b-a$ for all $y$ . Call this property $(*)$ .

Claim: $f(x)\in\{1,2\}$ for $x\ge3$ .

Proof. Over $t\ge2$ , let $f(t)$ be maximal. Then for $p\ge\max f$ , by $P(p-f(t-1),t-1)$ we have $f(f(p-f(t-1))+t-1)=1$ . then by $(*)$ , for primes $p,q\ge\max f$ , $f(t)\mid f(q-f(t-1))-f(p-f(t-1)).$ But $f(t)$ is larger than both terms on the right, so $f(p-f(t-1))=f(q-f(t-1))$ .

It follows that $f(p-f(t-1))$ is constant over all prime $p\ge\max f$ ; let this constant value be $C$ . Then by $(*)$ again, $f(y+C)\mid q-p.$ Then for each odd prime $r$ , we can select $p$ , $q$ with $r\nmid q-p$ by Dirichlet, so $f(y+C)\in\{1,2\}$ . In particular, $C\le2$ , so $f(x)\in\{1,2\}$ for $x\ge3$ . $\blacksquare$

Now we examine two cases:

If $f(x)=1$ for $x\ge3$ , then by $P(a,1)$ for $a\ge3$ , $f(2)\mid a+f(1)$ , so $f(2)=1$ .
Otherwise, assume $f(x)=2$ for some $x\ge3$ . If for $a,b\ge3$ , $f(a)=f(b)$ but $b-a$ is odd, then by $(*)$ , $f(y+f(a))\mid b-a$ , so $f(y+f(a))=1$ for all $y$ , contradiction.

If $f(3)=f(5)=\cdots=2$ and $f(4)=f(6)=\cdots=1$ then by $P(3,3)$ , $2\mid5$ , absurd.

Thus $f(3)=f(5)=\cdots=1$ and $f(4)=f(6)=\cdots=2$ . By $P(1,4)$ , $f(f(1)+4)\mid3$ , so $f(1)$ is odd. For odd $a\ge3$ , by $P(a,1)$ , we have $f(2)\mid a+f(1)$ , so $f(2)\mid2$ . But by $P(2,3)$ , $f(f(2)+3)\mid3$ , so $f(2)$ is even.

In both cases, we are done.

Comments

This post has been edited 1 time. Last edited by TheUltimate123, Nov 25, 2020, 10:41 AM

Z K Y

The post below has been deleted. Click to close.

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

mathaddiction

308 posts

mathaddiction

#6 h Nov 27, 2020, 8:43 AM • 2 Y

Y by centslordm, ImSh95

My solution during the contest which uses the bounded gaps between prime numbers.

The answer is $f(x)=x$ ,
$f(x)=\begin{cases}\text{arbitrary}&\text{if } x=1\\ 1&\text{if } x\geq 2\end{cases}$ and $f(x)=\begin{cases}\text{arbitrary}&\text{if } x=1\\ 1&\text{if } x \text{ is odd and greater than 1 }\\2&\text{if } x\text{ is even }\end{cases}$ It is straightforward to show that all three classes of function satisfies the divisibility, we now show that they are the only ones.
We will divide into two cases:

Case I: $f$ is bounded. Suppose $f\leq M$ .
We will use the fact that there exists infinitely many pairs of primes $(p,q)$ such that $0<p-q\leq 246$
Define
$S=\{(a,b):f(a)=f(b):a>b\}$ $D=\{a-b:(a,b)\in S\}$ Let $m=\min{D}$ .
CLAIM 1. If $n>M$ then
$f(n)\leq m$ Proof. Since $m\in D$ suppose $m=a-b$ . Then for any positive integer $y$ ,
$\begin{align*} f(f(a)+y)&|a+f(y)\\ f(f(b)+y)&|b+f(y)\\ \end{align*}$ Hence $f(f(a)+y)|a-b$ and therefore, for all $n>M$ we have $n-f(a)>0$ , hence
$f(n)=f(f(a)+(n-f(a)))\leq a-b=m$ $\blacksquare$
CLAIM 2. There exists infinitely many integers $a$ such that
$f(a)=1$ Proof.
Pick a sufficiently large prime $p$ with $p>2M$ , then
$f(f(p-f(y))+y)|p$ For all integers $y$ . Notice that left hand side is at most $M$ , hence we must have $f(f(p-f(y))+y)=1$ Therefore, it suffices to take $a=f(p-f(y))+y$ , since $y$ is arbitrary we are done. $\blacksquare$

CLAIM 3. $m\leq 246$
Proof.
Pick two sufficiently large primes $p,q$ such that $0<p-q<246$ , then
similar to the way in claim 2 we must have
$f(f(p-f(y))+y)=1=f(f(q-f(y))+y)$ Now suppose on the contrary that $f(p-f(y))\neq f(q-f(y))$ , then $(f(p-f(y))+y,f(q-f(y))+y)\in S$ , meanwhile, there difference
$|f(p-f(y))-f(q-f(y))|$ is less than $m$ since each of them is at most $m$ from Claim 1. This contradicts the minimality of $m$ . Therefore,
$f(p-f(y))=f(q-f(y))$ Hence $m\leq p-f(y)-(q-f(y))=p-q\leq 246$ . $\blacksquare$

CLAIM 4. If $n> 246$ then $f(n)\leq 246$ .
Proof.
Take the same $p,q$ as in Claim 3. Let $x_1=p-f(y)$ , $x_2=q-f(y)$ . Then from the proof of Claim 3 we have $f(x_1)=f(x_2)$ . Therefore,
$\begin{align*} f(f(x_1)+y)&|x_1+f(y)\\ f(f(x_2)+y)&|x_2+f(y)\\ \end{align*}$ This implies $f(f(x_1)+y)|x_1-x_2\leq 246$ , since $f(x_1)\leq m\leq 246$ by Claim 1 and Claim 3 we are done. $\blacksquare$

Corollary 1. Define
$S_1=\{(a,b):f(a)=f(b):a>b>246\}$ $D_1=\{a-b:(a,b)\in S_1\}$ Let $m_1=\min D_1$ , then if $n>246$ we have
$f(n)\leq m_1$ Proof.
Similar to Claim 1, let $m_1=a-b$ .
Then for any positive integer $y$ ,
$\begin{align*} f(f(a)+y)&|a+f(y)\\ f(f(b)+y)&|b+f(y)\\ \end{align*}$ Hence $f(f(a)+y)|a-b$ . From Claim 4 we have $f(a)\leq246$ , therefore, for all $n>246$ we have $n-f(a)>0$ , hence
$f(n)=f(f(a)+(n-f(a)))\leq a-b=m_1$
Corollary 2. $m\leq 2$ .
Proof.
Notice that $269,271$ is a pair of twin prime. From Claim 2 we can pick arbitrary large integer $a$ such that $f(a)=1$ . Then we have
$f(f(269-f(a))+a)|269$ Since $f(269-f(a))+a\geq 246$ , by Claim 4, $f(f(269-f(a))+a)<246$ , hence it can only be $1$ , that is
$f(f(268)+a)=f(f(269-f(a))+a)=1$ Similarly $f(f(270)+a)=f(f(271-f(a))+a)=1$ Now if $f(268)\neq f(270)$ then $(f(268)+a,f(270)+a)\in S_1$ hence
$|f(270)-f(268)|\in D_1$ However, from Corollary $1$ each of them is at most $m_1$ , therefore
$|f(270)-f(268)|<m_1$ This contradicts the minimality of $m_1$ ,
Therefore we must have $f(268)=f(270)$ , which implies $(268,270)\in S$ . hence $m\leq 2$ .

Now either $m=1$ or $m=2$ , in both case it is easy (using the same method as in Claim 1) to show that the only solutions are the second and third one as claimed.

Case II: f is unbounded.
Notice that $f$ is injective, otherwise from Claim 1 we have $f$ is bounded, contradiction. Let $f(1)=c$ , then
$f(y+c)|1+f(y)$ hence $f(y+c)\leq 1+f(y)$ Using induction we have
$f(ac+b)\leq a+f(b)$ Define
$M=\max\{f(1),f(2),...,f(c)\}$ Now for a fixed natural number $d$ and all $x\leq cd$ , $x=ac+b$ where $a\leq d-1$ and $1\leq b\leq c$
Hence $f(x)\leq a+f(b)\leq d-1+M$ However, from injectivity we have that
$f(1),f(2),...,f(cd)$ are all distinct numbers, therefore,
$cd\leq d-1+M$ This can't hold for large $d$ if $c>1$ . Therefore $c=1$ , as a result,
$f(y+1)\leq 1+f(y)$ Hence $f(y)=y$ by injectivity.

Z K Y

The post below has been deleted. Click to close.

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

CANBANKAN

1301 posts

CANBANKAN

#8 h Dec 7, 2020, 5:49 PM • 2 Y

Y by centslordm, ImSh95

For the bounded case, here is a completely elementary solution (I am pretty sure dirichlet and bounded gaps are not elementary, but bounded gaps may be proven with elementary methods, for example, $(2n)^{\pi(2n)}>\binom{2n}{n}>2^n$ .) Let $d_m$ be the minimal number such that there exists $x$ such that $f(x)=f(x+d_m)$

Then $P(x,y), P(x+d_m,y)$ yields $f(f(x)+y)\mid d_m$ for all $y\in \mathbb{Z}^+$ (1). Then consider $f(f(x)),f(f(x)+1),\cdots,f(f(x)+\tau(d_m))$ . Two of them must be equal because there are $\tau(d_m)+1$ terms but $\tau(d_m)$ options for these terms, so it follows $d_m\le \tau(d_m)$ , which implies $d_m\in \{1,2\}$ .

Subcase 1: $d_m=1$ . Comparing $P(l,y), P(l+1,y)$ yields $f(y)=1\forall y\ge 2$ . There are no restrictions on $f(1)$ .

Subcase 2: $d_m=2$ . We can see for some $l$ , $f(l+2q)=1\forall q\ge 0, f(l+2q+1)=2\forall q\ge 0$ . This is true because $f(x)\ne f(x+1)$ for any $x$ .

I claim $l$ is odd. If $l$ is even, $f(l)+l$ is odd but $f(f(l)+l)$ is even so $P(l,l)$ gives a contradiction.

Comparing $P(l,y), P(l+2,y)$ yields $f(f(l)+y)\mid 2$ . Pick $f(l)=1$ , so we can see $f(y)=\gcd(2,y)\forall y\ge 2$ .

This post has been edited 1 time. Last edited by CANBANKAN, Dec 7, 2020, 5:50 PM

Z K Y

The post below has been deleted. Click to close.

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

Mop2018

169 posts

Mop2018

#9 h Dec 10, 2020, 3:17 PM • 2 Y

Y by centslordm, ImSh95

I have a question.
At my solution, I thought that If there are infinite positive integers there is a gcd.
Is it correct?

Z K Y

The post below has been deleted. Click to close.

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

Mop2018

169 posts

Mop2018

#10 h Dec 10, 2020, 3:22 PM • 5 Y

Y by centslordm, ImSh95, Mango247, Mango247, Mango247

Anybody?

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9027 posts

Tintarn

#11 h Dec 10, 2020, 3:26 PM • 2 Y

Y by centslordm, ImSh95

Mop2018 wrote:

Anybody?

Please don't bump so quickly. Towards your question: Of course for any set of positive integers, there is a greatest common divisor, just the maximal number dividing all of them.
For example, the gcd of the set of all positive integers is just $1$ .

Z K Y

The post below has been deleted. Click to close.

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

Mop2018

169 posts

Mop2018

#12 h Dec 10, 2020, 3:34 PM • 3 Y

Y by centslordm, ImSh95, Mango247

Thanks.
I was quick. sorry for that

Z K Y

The post below has been deleted. Click to close.

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

Supercali

1260 posts

Supercali

#13 h Jan 2, 2021, 6:04 PM • 4 Y

Y by A-Thought-Of-God, centslordm, ImSh95, Mango247

Let $P(x,y)$ denote the original proposition.

We split the problem into two cases:

Case I: $f$ is unbounded.

In this case, we get that $f$ is injective. Indeed if $f(x_1)=f(x_2)$ then comparing $P(x_1,y)$ and $P(x_2,y)$ gives us $f(f(x_1)+y) \mid x_1-x_2$ which gives $x_1=x_2$ since $f$ is unbounded.

Let $f(1)=k$ . $P(1,x)$ gives $f(x+k) \mid f(x)+1$ $\implies f(x+k) \leq f(x)+1$ Call the above $Q(x)$ . Now if $f(a)<f(b)$ for some $a>b$ then $Q(a)$ $\implies$ $f(a+k) \leq f(a)+1 \leq f(b)$ $\implies$ $f(a+k)<f(b)$ by injectivity $\implies$ $f(a+nk) < f(b)$ for all positive integers $n$ , which contradicts injectivity. Therefore $f$ is non-decreasing, in fact strictly increasing due to injectivity. Hence $Q(x)$ gives $f(x+k) = f(x)+1$ for all $x$ . If $k>1$ get $f(x) < f(x+k-1) < f(x+k) =f(x)+1$ Contradiction! So $k=1$ , and by easy induction we get the solution $\boxed{f(x)=x \ \ \forall x \in \mathbb{N}}$
Case II: $f$ is bounded.

Let $M= \limsup\limits_{t \rightarrow \infty} f(t)$ .

Claim: $f(x_1)=f(x_2)$ $\implies$ $M \mid x_1-x_2$
Proof: Follows from comparing $P(x_1,y)$ and $P(x_2,y)$ for a $y$ such that $f(f(x_1)+y)=M$ . $\blacksquare$

If $M=1$ then $f(x)=1$ for all large $x$ . Comparing $P(x,y)$ and $P(x+1,y)$ for a large $x$ gives us $f(y+1)=1$ for all $y$ . Hence we get the solution $\boxed{f(x)=1 \ \text{for} \ x>1 \ \text{and} \ f(1) \ \text{arbitrary}}$ Now suppose $M \geq 3$ . Let $n$ be a large positive integer such that $n \equiv -1 \pmod p$ for all primes $p \leq M$ . Note that the only number not exceeding $M$ which divides either $n$ or $n+2$ is $1$ . Therefore $P(n-f(x),x)$ and $P(n+2-f(x),x)$ for some large $x$ give $f(f(n-f(x))+x)=f(f(n+2-f(x))+x)=1$ $\implies M \mid f(n+2-f(x))-f(n-f(x))$ For large values, $f$ is bounded above by $M$ , so the only way the above divisibility holds is $f(n+2-f(x))=f(n-f(x))$ $\implies M \mid 2$ , contradiction!

Finally assume $M=2$ . Therefore $f(x) \in \{ 1,2 \}$ for all large $x$ and by the claim, $f(x+1) \neq f(x)$ for all $x$ . Hence for all large $x$ , either $f(x)$ and $x$ have same parity, or opposite parity. In the second case, take $x,y$ to be large even integers; then $x+f(y)$ is odd while $f(f(x)+y)$ is even, contradiction! So $f(x) \equiv x \pmod 2$ for all large $x$ .

Now taking $t$ to be a large odd integer and comparing $P(t,y)$ and $P(t+2,y)$ we get $f(y+1) \mid 2$ $\implies$ $f(x) \leq 2$ for all $x>1$ . So the previous paragraph in fact holds for all $x>1$ . It is also easy to see that $f(1)$ must be odd (for instance from $P(2021,1)$ ). Therefore we get the solution $\boxed{ f(x) = 2 + x -2 \left \lceil \frac{x}{2} \right \rceil \ \text{for} \ x>1 \ \text{and} \ f(1) \ \text{arbitrary but odd}}$

This post has been edited 2 times. Last edited by Supercali, Jan 2, 2021, 8:34 PM

Z K Y

The post below has been deleted. Click to close.

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

Rg230403

222 posts

Rg230403

#14 h Apr 8, 2021, 6:36 AM • 2 Y

Y by centslordm, ImSh95

We do it in two cases. $f$ is bounded and $f$ is unbounded. Let's handle the unbounded case first. Observe that if $f(a)=f(b)=k$ then we have $f(y+k)|a-b$ but now due to unboundedness of $f$ , we have that $f$ is injective. Now, let $m$ , be the smallest number in the range of $f$ and let $f(a_0)=m$ .

Now, we claim that if $a_i=a_0+if(1)$ then $f(a_i)=m+i$ . We prove this by induction on the assertion $P(a_{i},1)$ . Result is true for base case $i=0$ by our assumption.

Observe that $f(a_0+if(1))=f(a_0+(i-1)f(1)+f(1))|1+f(a_0+(i-1)f(1))=1+m+i-1=m+i\implies f(a_0+if(1))\le m+1$ but since $f$ is injective and does not take the values from $1$ to $m-1$ and $f(a_0),\cdots f(a_{i-1})$ takes the value $m,m+1,\cdots m+i-1$ , we have $f(a_0+if(1))=m+i$ .

But, now if $f(1)\ne 1$ then we have that $f(a_0+1)$ cannot take any value which is absurd. Now, if $f(1)=1$ , we have $m=a_0=1$ and thus $f(n)=n$ .

Now, if $f$ is bounded. This means that $f$ takes finitely many values. Let $S$ be the set of values which $f$ takes on infinitely often and $|S|=s$ . Now, for all large enough $n$ , $f$ only takes values in $S$ . So, consider $f(n),f(n+1),\cdots f(n+s)$ . By PHP, atleast $2$ of these take the same value and gap at most $s$ . Let these values be $a,b$ then $f(f(a)+y)|a-b$ but $a-b$ is at most $s$ but we have that $f(f(a)+y)$ takes all $s$ values in $S$ so some number less than $s+1$ has atleast $s$ divisors. Thus, $a-b=s\in\{1,2\}$ . If $s=1$ , then we have $f(1+y)|1\implies f(y+1)=1$ and thus, all values except $1$ go to $1$ . Observe that $f(1)=n, f(1+y)=1\forall y\ge 1$ works.

Now, $s=2$ , thus, $f(f(a)+y)|2$ and thus $f$ takes values $1,2$ . Observe that two consecutive numbers must go to different values and all large enough values alternately go to $1,2$ . But now consider when $f(a)=1$ . Thus, $f(y+1)|2$ . Thus, from $2$ itself values alternately go to $1,2$ . If $f(2)=1$ , then $(x,y)=(2,2)\implies f(1+2)|3\implies 2|3$ which is absurd. Thus, $f(2)=2$ . Now, $(3,1)\implies f(2)|3+f(1)\implies 2|3+f(1)\implies f(1)\equiv 1 \pmod{2}$ . But its easy to check $f(1)$ is odd and $f(n)\equiv n\pmod{2}$ and $f(n)\in \{1,2\}$ .

Thus, only these solutions work-

$f(x)=x$
$f(x)=1 \forall x\ge 2$
$f(x)\equiv x\pmod{2} \forall x\ge 1$ and $f(x)\in \{1,2\}\forall x\ge 2$ and $f(1)$

Z K Y

The post below has been deleted. Click to close.

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

L567

1184 posts

L567

#15 h May 23, 2021, 6:00 PM • 2 Y

Y by centslordm, ImSh95

Really nice problem! Solved with Pujnk

Let $P(x,y)$ denote the given assertion. Consider two cases:

Case 1: $f$ is unbounded

Suppose $f(a) = f(b)$ . $P(a,y)$ gives that $f(f(a)+y) | a + f(y)$ and $P(b,y)$ gives $f(f(b)+y) | a+f(y)$ , this means $f(f(a)+y) | a-b$ . Since $f$ is unbounded, the LHS takes on arbitrarily large values and so this is impossible unless $a-b = 0 \implies a=b$ and so $f$ is injective.

Let $f(1) = c$ . Now, $P(1,y)$ gives that $f(y+c) | f(y) + 1$ . This means that $f(y+c) \le f(y) + 1$ . Suppose for some $y$ , we have $f(y+c) < f(y) + 1$ , then since for every increase in $c$ , the value of $f(y)$ increases by at most $1$ , we can easily see that injectivity is contradicted. So, we have that $f(y+c) = f(y) + 1$ for all $y$

$P(p-f(y), y)$ gives that $f(f(p-f(y))+y) | p$ and so $f(f(p-f(y))+y) = 1$ or $p$ but since $f$ is injective, it can be equal to $1$ at most once, so we have that $f(f(p-f(y))+y) = p$ . Also since $f$ is injective, we have that $f(p-f(y))+y$ is constant for all $y$ , which gives that $f(p-f(y)) = p-y$

Now, $P(x,p-f(x))$ gives that $f(p) | p$ but since $f$ is injective, this forces $f(p) = p$ for all primes except at most $1$

Since we had $f(y+c) = f(y) + 1$ , we get that $f(kc+1) = k+1$ . But by dirichlet, we have infinitely many primes $p = kc + 1$ and so pick some such prime. We then have that $p = f(p) = f(kc+1) = k+1$ and so we get that $k = p-1 \implies k = kc-1 \implies c = 1$ and so $f(1)= 1$ .

So, we have that $f(k+1) = k+1$ for all $k \ge 1$ and so this means $f(n) = n$ for all $n \in \mathbb{N}$ is the only solution in this case

Case 2: (The harder case) $f$ is bounded

Let $S := \{n \mid f(n) = 1\}$ . Observe that $P(p-f(y), y)$ gives that $f(f(p-f(y))+y) | p$ but since $f$ is bounded, this means for all sufficiently large primes $p$ , we have that $f(f(p-f(y))+y) = 1$ and so $f(p-f(y))+y \in S$ for all big primes $p$ and all $y \in \mathbb{N}$ , so this means there is at least $1$ element in $S$

Suppose $z \in S$ , then $P(p-1, z)$ for some big enough prime gives that $f(z+f(p-1)) = 1$ and so $z + f(p-1) \in S$ . In particular, this means that there are infinite elements in $S$

From $P(z,n)$ and $P(z+f(p-1),n)$ , we get that $f(n+1) | f(p-1)$ for all big enough primes $p$ .

So suppose $f(p-1) < f(q-1)$ for big primes $p,q$ , but then taking $n=q-2$ , we get that $f(q-1) | f(p-1)$ , which is impossible, so we get that $f(p-1)$ is constant for all big enough primes $p$ . Since $f(\text{anything else})$ divides this, we know that $f(p-1)$ is also equal to the maximum value of $f$ , call it $M$

But from the unbounded case, we have that if $f(a) = f(b)$ , then $f(x+f(a)) | b-a$ for all $x$ , so putting $a = p-1, b = q-1$ , we get that $f(y+M) | q-p$ . Now, for each odd prime that divides $f(y+M)$ , we can find a $q$ such that $q - p \neq 0 \pmod r$ . Then, by CRT, we combine these into one thing and we can still find a prime $q$ by dirichlet. So, we can ensure that $f(y+M)$ can only take on powers of two.

But we can do better than this! Add to the conditions for selecting $q$ , the fact that $q \equiv p+2 \pmod 4$ so that $v_2$ of the RHS becomes $2$ . This forces $f(y+M) | 2$ and so for big enough numbers, $f$ is just $1$ and $2$ . But since $f(p-1) = M$ for big enough $p$ , we get that $M = 1$ or $2$ as well. So $f(x)$ only takes the values $1$ and $2$ for all $x \ge 3$

If $f(x) = 1$ for all $x \ge 3$ , from $P(3,1)$ , we get that $f(2) | n+f(1)$ for all $n$ , which forces $f(2) = 1$ . Then, $f(1)$ can be chosen arbitrarily because it doesnt really matter for the FE to work. So this is one solution, $f(1)$ arbitrary and $f(n) = 1$ for $n > 1$

Now suppose $f(x) = 2$ for some value $x \ge 3$ . Then, we know that $f(p-1) = 2$ for all primes $\ge 3$ . In particular, $p = 3$ gives that $f(2) = 2$ . We know that if $f(a) = f(b)$ , then $f(x+f(a)) | a-b$ , we can pick some $x$ such that LHS becomes $2$ and so we have $2 | a-b$ and so we get that $f(x) = 2$ for any even $x$ .

We know that if $f(x) = 1$ , then $f(x+f(p-1)) = 1$ and so we get $f(x+2) = 1$ . So we get that all sufficiently large odd numbers map to $1$ . Now, suppose $f(x) = 2$ where $x$ is an odd number $\ge 3$ , then we get that all numbers greater than $x$ also map to $2$ , which is impossible. So, we have that all even numbers map to $2$ and all odd numbers (except 1) map to $1$ .

Now, consider what the value of $c = f(1)$ can be. $P(x,1)$ gives that $f(f(x)+1) | x+c$ . If $c$ is odd, then picking an even number $x$ , we get that $2 | x+c$ , which is impossible since $x+c$ is odd. So, $c$ must be even, and this obviously will work.

So, finally, after all of that, the solutions are:

1. $f(x) = x$ for all $x \in \mathbb{N}$

2. $f(x) = \begin{cases} c & \text{if } x=1 \\ 1 & \text{if } x>1 \end{cases}$ for arbitrary $c$ , and

3. $f(x) = \begin{cases} 2c-1 & \text{if } x=1 \\ 1 & \text{if } x>1 \text{ is odd} \\ 2 & \text{if } x \text{ is even.} \end{cases}$ for arbitrary $c$

which finishes the problem.

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5532 posts

megarnie

#16 h Apr 23, 2022, 3:01 AM • 5 Y

Y by ImSh95, jrsbr, David-Vieta, SatisfiedMagma, Mango247

When your first China MO solve is a P6

Ok time for the writeup.

Find all functions $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$ , such that for any $x,y \in \mathbb{Z}_+$ , $f(f(x)+y)\mid x+f(y).$
The only solutions are $\boxed{f(x)=x}$ $\boxed{f(x)=\begin{cases} c & \text{ if }x=1 \\ 1 &\text{ if } x>1 \\ \end{cases}},$ where $c$ is any positive integer constant, and $\boxed{f(x)=\begin{cases} d & \text{ if }x=1 \\ 1 & \text{ if } x>1 \text{ and }x \text{ is odd } \\ 2 & \text{ if }x \text{ is even } \\\end{cases}},$ where $d$ is any odd positive integer constant.

First we will verify that they work.

The first solution is trivial because $f(f(x)+y)=x+f(y)=x+y$ .

For the second solution, we note that $f(x)+y>1$ , so $f(f(x)+y)=1$ , and we are done because $1$ divides all positive integers.

For the third solution, we note that $f(x)\equiv x\pmod 2$ and also $f(x)+y>1$ .

If $x+y$ is even, then $f(f(x)+y)$ is even, so it is $2$ . Now, $x+f(y)$ is also even, so $2\mid x+f(y)$ .

If $x+y$ is odd, then $f(f(x)+y)$ is odd, so it is $1$ . Now, $1$ divides every positive integer, so $1\mid x+f(y)$ .

Thus, all of these solutions work. We now prove they are the only ones.

Let $P(x,y)$ denote the given assertion.

We start with the following lemma:

Lemma: $f$ is either injective or bounded above.
Proof: Suppose FTSOC $f$ was not injective and unbounded.

Let $a>b$ satisfy $f(a)=f(b)$ .

$P(a,x): f(f(a)+x)\mid a+f(x)$ .

$P(b,x): f(f(b)+x)\mid b+f(x)$ , so $f(f(a)+x)\mid b+f(x)$ .

Now that $f(f(a)+x)$ divides both $a+f(x)$ , and $b+f(x)$ , it must divide $\gcd(a+f(x),b+f(x)),$ which divides $a+f(x)-(b+f(x))=a-b$ .

So $f(f(a)+x)\le a-b$ for each positive integer $x$ . If this were true, then $f$ would be bounded, a contradiction. $\blacksquare$

Now, we split into two cases, based on whether $f$ is injective or not.

Case 1: $f$ is injective.
Set $f(1)=c$ .

Claim 1.1: For each nonnegative integer $n$ , $f(nc+1)\le n+c$ .
Proof: We prove the result by induction.

Base cases: We will show that both $n=0$ and $n=1$ work.

Clearly $n=0$ works since $f(1)=c$ .

$P(1,1): f(c+1)\mid c+1$ , so $f(c+1)\le c+1$ , so $n=1$ also works.

Inductive step: We will show that if $f(nc+1)\le n+c$ , then $f((n+1)c+1)\le n+c+1$
$P(1,n): f(n+c)\mid f(n)+1$ , so $f(n+c)\le f(n)+1$ .

This implies that $\begin{align*} f((n+1)c+1) \\ =f(nc+1+c) \\ \le f(nc+1)+1 \\ \le n+c+1, \\ \end{align*}$ as desired. $\blacksquare$

Claim 1.2: For each positive integer $x>1$ , $f(x)>c$ .
Proof: Clearly $f(x)\ne c$ as $f$ is injective. Suppose FTSOC $f(a)<c$ for some $a>1$ .

We will show that $f(a+nc)< c$ for each nonnegative integer $n$ by induction on $n$ .

Base cases: Clearly $n=0$ works.

$P(1,a): f(a+c)\le f(a)+1<c+1$ , so $f(a+c)\le c$ . However, due to injectivity, $f(a+c)\ne c$ , so $f(a+c)<c$ .

Inductive step: We will show that if $f(a+nc)<c$ , then $f(a+(n+1)c)<c$
$P(1,x): f(x+c)\le f(x)+1$ .

So $\begin{align*} f(a+(n+1)c) \\ =f((a+nc)+c) \\ \le f(a+nc)+1 \\ < c+1 \\ \end{align*}$
However, since $f$ is injective, $f(a+(n+1)c)\ne c$ , so $f(a+(n+1)c)<c,$ as desired.

Thus, $f(a+nc)<c$ .

Consider the set $\{f(a),f(a+c),\ldots, f(a+(c-1)c)\}$ .

Clearly every element in this set must be less than $c$ . Now that there are $c$ elements, two of them must be equal, which contradicts injectivity. $\blacksquare$

Now let $S_n=\{f(1),f(c+1),f(2c+1),\ldots,f(nc+1)\}$
Clearly each element in $S_n$ is in the interval $[c,n+c]$ . There are $n+1$ elements in this interval, so $S_n$ takes on each value from $c$ to $n+c$ .

Thus, all $x\ge c$ are in the infinite set $S=\{f(1),f(c+1),f(2c+1),\ldots,\}$
If $c>1$ , then the set $T=\{f(2),f(c+2),f(2c+2),\ldots,\}$ contains no elements in common with $S$ .

Since $f$ is injective, all elements in $T$ are less than $c$ . However, this is a contradiction since all the elements of $T$ are distinct.

This implies $c=1$ .

Now we prove $f(n)=n$ for each positive integer $n$ by induction on $n$ .

Base case: Clearly $f(1)=1$ .

Inductive step: Suppose $f(x)=x$ for all $x<n$ . We will show $f(n)=n$ .

$P(n-1,1): f(n)\le n$ . But if $f(n)=a<n$ , then $f(n)=f(a)$ , a contradiction. So $f(n)=n$ , as desired. $\blacksquare$

Case 2: $f$ is not injective, and thus bounded.
Since $f$ isn't injective, let $a>b$ satisfy $f(a)=f(b)$ .

Now similarly to our Lemma at the beginning, we find that $f(f(a)+x)\mid a-b$ for any positive integer $x$ .

Let $n$ denote the gcd of all possible values of $a-b$ , where $a>b$ , and $f(a)=f(b)$ .

Note that $f(k)\mid n$ for all sufficiently large $k$ .

Also, if $f(a+x)=f(a)$ for a positive integer $x$ , then $x\ge n$ . Call this fact 1

Let $M$ be some sufficiently large positive integer.

Consider the set with $n$ elements $\{f(M),f(M+1),\ldots,f(M+n-1)\}$ . By fact 1, all elements of this set must be distinct.

However, since $M,M+1,\ldots,M+n-1$ are all sufficiently large, all elements of the set divide $n$ .

Thus, there are at least $n$ distinct divisors of $n$ , which implies $n\in \{1,2\}$ .

Subcase 2.1: $n=1$ .
Then $f(k)=1$ for all sufficiently large $k$ . We prove the following claim:

Claim: 2.1.1: $f(x)=1$ for all positive integers $x>2$ .
Proof: Let $x>2$ be some positive integer greater than $1$ and $C$ be some sufficiently large positive integer.

$P(C,x-1): f(x)\mid C+f(x-1)$ .

$P(C+1,x-1): f(x)\mid C+1+f(x-1)$ .

Thus, $f(x)\mid \gcd(C+f(x-1),C+1+f(x-1))=1$ , so $f(x)=1$ . $\blacksquare$

Now $f(1)$ can be any positive integer, so this gives the second solution $\boxed{f(x)=\begin{cases} c & \text{ if }x=1 \\ 1 &\text{ if } x>1 \\ \end{cases}}$ .

Subcase 2.2: $n=2$ .
Then $f(k)\in \{1,2\}$ for any sufficiently large $k$ . Since $n=2$ , $f(a)\ne f(a+1)$ for any $a$ .

Claim: 2.2.1: $f(x)\in \{1,2\}$ for all positive integers $x>1$ .
Proof: Let $x$ be a positive integer greater than $1$ and $M$ be a sufficiently large positive integer with $f(M)=1$ .

Note that $f(M+1)\ne f(M)$ , so $f(M+1)=2$ , and $f(M+2)\ne f(M+1)$ , so $f(M+2)=1$ .

$P(M,x-1): f(x)\mid M+f(x-1)$ .

$P(M+2,x-1): f(x)\mid M+2+f(x-1)$ .

Thus, $f(x)\mid \gcd(M+f(x-1),M+2+f(x-1))\mid 2$ , as desired. $\blacksquare$

For $m>1$ , note that $f(m)\ne f(m+1)$ , and $f(m+1)\ne f(m+2)$ , so $f(m)=f(m+2)$ .

If $f(2)=1$ , then $P(2,2): f(3)\mid 3$ . However, $f(3)\ne f(2)$ , so $f(3)=2$ , a contradiction as $2\nmid 3$ .

Thus, $f(2)=2$ . This implies $f(x)=2$ for all even $x$ , and $f(x)=1$ for all odd $x>1$ .

To arrive at the solution $\boxed{f(x)=\begin{cases} d & \text{ if }x=1 \\ 1 & \text{ if } x>1 \text{ and }x \text{ is odd } \\ 2 & \text{ if }x \text{ is even } \\\end{cases}}$ , we have to show $f(1)$ is odd.

$P(1,3): f(f(1)+2)\mid 3$ . If $f(1)$ was even, then $f(1)+2$ is even, so $f(f(1)+2)$ is even, a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#18 h Jul 4, 2022, 5:45 AM

Y by

Denote the assertion by $P(x,y).$ If $f(u)=f(v)$ then $P(u,x)$ and $P(v,x)$ gives $f(f(u)+f(v)+x)$ $\mid u-v.$ So either $u=v$ or $f$ is bounded.

If $f$ is injective, then $P(1,x)$ gives $f(x+f(1))$ $\mid f(x)+1.$ If $f(x+f(1))$ $<f(x).$ Then by induction, $f(x+kf(1))<f(x)$ a contradiction with injectivity. So $f(x+kf(1))=f(x)+k$ and by injectivity $f(1)=1.$ Now by induction $f$ is the identity, which works.

If $f$ is bounded, then let $\gamma$ be the maximum of $f.$ So $u-v\leq \gamma.$ And thus $\tau (\gamma)\geq \gamma$ iff $\gamma=1,2.$ If $\gamma =1$ then $P(x,y)$ and $P(x+1,y)$ gives $f(x)=1$ for $x>1$ and this works. If $\gamma=2$ then it's not hard to get $2\mid f(x)-x$ and $f(x)=1,2$ for all $x>1.$ This works.

This post has been edited 2 times. Last edited by ZETA_in_olympiad, Jul 4, 2022, 5:48 AM

Z K Y

The post below has been deleted. Click to close.

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

jrsbr

63 posts

jrsbr

#19 h Jul 31, 2022, 11:11 PM • 1 Y

Y by ihavealotofquestions

We prove that all such functions are $f(x)=x$ for all $x\in\mathbb{Z}_{>0}$ ,
$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\text{ is odd;}\\2\text{ if }x\text{ is even.}\end{cases}$ and
$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\ne1.\end{cases}.$ Let $P(x,y)$ be the proposition $f(f(x)+y)\mid x+f(y)$ . We have that, if $f(a)=f(b)=c$ :
$P(a,x): f(c+x)\mid a+f(x),$ $P(b,x): f(c+x)\mid b+f(x)$ $\implies f(c+x)\leq|a-b|,$ and we conclude that $f$ is injective or bounded.
$\textbf{Case 1:}$ If $f$ is injective, let $x_0$ be such that $f(x_0)=m$ is minimun.
$P(1,x_0): f(f(1)+x_0)\mid1+f(x_0)\implies f(f(1)+x_0)\leq1+f(x_0).$ If $f(f(1)+x_0)<1+f(x_0)$ , then $f(f(1)+x_0)=f(x_0)$ , a contradiction since $f$ is injective.
Therefore, we have $f(f(1)+x_0)=1+f(x_0)$ .
We prove by induction that $f(nf(1)+x_0)=n+f(x_0), n\in\mathbb{Z}_{\geq0}$ .
Suppose that for all $n_0\leq n$ we have the desired property. Then:
$P(1,nf(1)+x_0): f(f(1)+nf(1)+x_0)\mid 1+f(nf(1)+x_0)$ $\implies f((n+1)f(1)+x_0)\leq n+1+f(x_0).$ If we don't have the inequality, we must have $f((n+1)f(1)+x_0)=f(x_0)+k=f(kf(1)+x_0)$ , for some $k<n+1$ , which implies $f(1)=0$ from $f$ injective, a contradiction.
From this, since $x+f(x_0)$ goes through every element from $f$ 's image, and since $f$ is injective, we must have that $nf(1)+x_0$ goes though every element of $\mathbb{Z}_{>0}$ , from where we conclude that $f(1)=1=x_0$ , and thus $f(x)=x$ for all $x\in\mathbb{Z}_{>0}$ .
$\textbf{Case 2:}$ If $f$ is bounded, see that if $C=min\{|a-b|\}$ , where $f(a)=f(b)$ , then $f(x)\mid C$ , for all sufficiently large $x$ .
This implies that all elements from the set $A=\{f(x),f(x+1),\dots,f(x+C-1)\}$ are distinct. But, for $x>>0$ we have that all elements from $A$ divide $C$ , and thus we conclude that $C\in\{1,2\}$ and, therefore, $f(x)\in\{1,2\}$ for $x>>0$ .
Suppose that we have $f(x)=2$ for some $x$ sufficiently large. Then:
$P(x,x-2): f(f(x)+x-2)\mid x+f(x-2)\implies2\mid x+f(x-2)$ $\implies x\equiv f(x-2)(mod\text{ }2).$ $P(x-1,x-2): f(f(x-1)+x-2)\mid x-1+f(x-2)\equiv1(mod\text{ }2)\implies f(x-1)=1.$ From this, we conclude that $f(x+1)=1$ . If $f(x+2)=1$ , then:
$P(x+2,x-1): f(f(x+2)+x-1)\mid x+2+f(x-1)$ $\implies 2\mid x+3,$ and
$P(x+1,x-1): f(f(x+1)+x-1)\mid x+1+f(x-1)$ $\implies 2\mid x+2,$ and we get a contradiction. By $P(x+1,x-1)$ we conclude, then, that $f(even)=2$ and $f(odd)=1$ , for large $x$ .
$\textbf{Claim 1:}$ $f(x)\equiv x(mod\text{ }2)$ , for $x>1$ .
$\textbf{Proof:}$ Let $N$ be such that $f(x)\in\{1,2\}$ for all $x>N$ . Suppose $N$ is even (for $N$ odd is similar). For $x>N$ our claim is already proved. From:
$P(N,N+1): f(f(N)+N+1)\mid N+1\implies f(N)\text{is even}.$ Suppose by induction that for $n_0\leq n$ we have $f(N-n_0)\equiv N-n_0(mod\text{ }2)$ . Then:
$P(N-n+1,N-n-1): f(f(N-n+1)+N-n-1)\mid N-n+1+f(N-n-1).$ See that $f(N-n+1)\equiv N-n+1(mod\text{ }2)\implies f(N-n+1)+N-n-1\equiv0(mod\text{ }2)$ and thus $f(f(N-n+1)+N-n-1)$ is even. From this we conclude that $f(N-n-1)\equiv N-n-1(mod\text{ }2)$ , as desired. $\square$
$\textbf{Claim 2:}$ $f(x)=1$ for all $x>1$ that is odd.
$\textbf{Proof:}$ Take $p$ to be a big prime and $n$ an odd number. We have:
$P(p-f(n-1),n-1): f(f(p-f(n-1))+n-1)\mid p.$ See that $p-f(n-1)$ is odd, and since $p-f(n-1)$ is large we have $f(p-f(n-1))=1$ , which implies that $f(n)\mid p$ and thus $f(n)=1.$ $\square$
$\textbf{Claim 3:}$ Take $p$ to be a big prime and $n$ an even number. We have:
$P(2p-f(n-1),n-1): f(f(2p-f(n-1))+n-1)\mid 2p\implies f(n)\mid2p\implies f(n)=2. \square$ We can check that any odd value can be assigned to $f(1)$ . Therefore:
$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\text{ is odd;}\\2\text{ if }x\text{ is even.}\end{cases}$ where $k$ is an odd positive integer.
Now, if for $x>>0$ we have $f(x)=1$ , take any integer $N>1$ and a large prime $p$ . See that from:
$P(p-f(N-1),N-1): f(f(p-f(N-1))+N-1)\mid p\implies f(N)\mid p\implies f(N)=1.$ We can assign any value for $f(1)$ and from this last case we get:
$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\ne1.\end{cases}$ From this we conclude the problem. $\blacksquare$

This post has been edited 3 times. Last edited by jrsbr, Aug 1, 2022, 2:35 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6858 posts

v_Enhance

#20 h Apr 22, 2023, 4:29 AM • 4 Y

Y by megarnie, HamstPan38825, EpicBird08, ihavealotofquestions

Solution from Twitch Solves ISL:

There are three families of solutions:

$f$ is the identity function;
$f(n) = 1$ for $n \ge 2$ , where $f(1)$ is any positive integer.
$f(n) = 2$ for $n$ even, $f(n) = 1$ for odd $n \ge 3$ , and $f(1)$ is any odd positive integer.

The verification is easy, so we prove these are the only solution. The proof is split into two main cases.

Case where $f$ is not injective Let $T = \min_{f(a)=f(b), a<b} (b-a).$ Then all outputs of $f$ are eventually divisors of $T$ , as $f(y+f(a)) = f(y+f(b)) \mid \gcd(f(y)+a,f(y)+b) \mid b-a \qquad \forall y > 0.$ Claim: We have $T \le 2$ .
Proof. If $T > 2$ , then look any $T$ consecutive outputs. They were supposed to be distinct divisors of $T$ , impossible for $T > 2$ . $\blacksquare$
If $T=1$ , then for any $n \ge 2$ , let $y=n-1$ and let $x$ be a large integer. Then we have $f(n) \mid x + f(n-1)$ for all large $x$ , forcing $f(n)+1$ .
If $T=2$ , then it follows $f$ must alternate between $1$ and $2$ eventually. Again, $f(n) \le 2$ follows for $n \ge 2$ as in the previous case, by letting $y=n-1$ and $x$ be large with $f(x)=1$ . We can then quickly verify that only the situation where $f(\text{even})=\text{even}$ bears solutions, the ones we claimed earlier.

Case where $f$ is not injective Let $c = f(1)$ . Taking $x=1$ then gives $f(y+c) \le f(y)+1.$ This implies $f(n) \leq \frac 1c n + \max \left\{ f(1), \dots, f(c) \right\}.$ For $f$ to be injective, we must then have $c=1$ . Finally, $f(y+1) \le f(y)+1$ together with $f$ injective then forces $f$ to be the identity function, by induction.

Z K Y

The post below has been deleted. Click to close.

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

aleksijt

44 posts

aleksijt

#22 h Aug 2, 2023, 11:06 AM • 1 Y

Y by GeoKing

Nice! The solutions are $f(x)=x\text{, }f(x)=1\text{ for }x>1\text{ and }f(x)=x\pmod2\text{ for }x>1.$ For $y\rightarrow y-f(x)$ we get $f(y)\mid x+f(y-f(x)\text{ when }y>f(x)\text{ and denote this with }Q(x,y).$ We do cases whether $f$ is bounded or not. First, assume it's not.
If $f(a)=f(b)$ , $Q(a,y)$ and $Q(b,y)$ give $f(y)\mid a-b$ and choosing $f(y)$ large we get injectivity.

Claim: The sequence of new maximums of $f$ eventually has common difference $1$ .
Proof. Let $f(a)$ be some term of the sequence with $a>f(1)$ . $Q(1,a)$ gives $f(a)\mid 1+f(a-f(1))$ and because $f(a)>f(a-f(1))$ we have equality.

This, with injectivity, gives that $f(n+1)=f(n)+1$ for all sufficiently large $n$ . Thus, $f(n)+1=f(n+1)=f(n-f(1))\Rightarrow f(1)=1$ . Hence $f$ is the identity (again, due to the Claim and injectivity).

Now suppose $f<M$ is bounded. Note that for any prime $p>M$ , setting $x=p-f(y)$ gives $f(f(p-f(y))+y)=1$ since it can't be $p$ .
Let $f(a)$ be a maximum of $f$ on $(1,+\infty)$ , then $Q(p-f(a),a)$ : $f(a)\mid f(p-f(a))+a+f(a-1)\Rightarrow f(p-f(a))\stackrel{\text{over }p}{=}\text{constant}$ since $f(p-f(a))\le f(a)$ . For two choices $p$ and $q$ , like in the injectivity proof above, we get $f(a)\mid p-q$ and by Dirichlet's theorem this forces $f(a)\mid 2$ . From here, check cases on $f(2)$ .

If $f(2)=1$ and $f(a)=2$ for some $a>1$ , $Q(f(a),a)\Rightarrow f(a)\mid f(a-1)$ and by induction $f(2)=2$ . Hence we get the second solution.

If $f(2)=2$ by the above we have $f(a)\mid f(a-2)$ ( $a>2$ ) and if $f(a)=f(b)=2$ when $a>3$ , $Q(b.a)\Rightarrow 2\mid b$ . To finish it's enough to show there are large preimages of $2$ .
Claim: If $f(x)=1$ for all $x>C$ we have $f(x)=1$ for $x>1$ .
Proof. Take $x$ large in $Q$ .

Remark:

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5000 posts

IAmTheHazard

#23 h Feb 22, 2024, 4:34 PM

Y by

The answer is $f(x)=x$ , $f(x)=1$ for $x \geq 2$ with $f(1)$ arbitrary, or $f$ sending evens to $2$ and odds to $1$ , except for $f(1)$ which can be an arbitrary odd. These clearly work.

Let $P(x,y)$ denote the assertion.

First suppose that $f$ is unbounded. Then if $f(a)=f(b)$ by comparing $P(a,y)$ with $P(b,y)$ we find that $f(z) \mid a-b$ for all $z>f(a)$ , hence $a=b$ . On the other hand, for any fixed $t$ we have $f(f(t)+y) \leq t+f(y)$ , hence $f(x)$ is bounded above by $\tfrac{t}{f(t)}x+C$ for some suitable choice of $C$ depending on $t$ (by induction, starting with $f(1)$ through $f(f(t))$ ). Hence $f(t) \leq t$ , otherwise by pigeonhole $f$ cannot be injective. But this holds for all $t$ , hence $f(t)=t$ by injectivity again.

Now suppose $f$ is bounded. Take $b>a$ with $b-a$ minimal such that $f(b)=f(a)$ ; by comparing $P(a,y)$ with $P(b,y)$ it follows that all sufficiently large $z$ satisfy $f(z) \mid b-a$ . But now take some large $M$ and consider $f(M),f(M+1),\ldots,f(M+(b-a-1))$ , which should be pairwise distinct but all divisors of $b-a$ , hence $b-a \leq 2$ .

If $b-a=1$ then $f(x)=1$ for $x \geq 2$ , and it is clear that $f(1)$ can be anything. If $b-a=2$ then we find that $f(\text{even})=2$ and $f(\text{odd})=1$ for all inputs at least $2$ , since the other case yields a contradiction by making $x$ and $y$ both odd. Then $f(1)$ is odd from $P(1,1)$ . This finishes the problem. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Aug 12, 2024, 11:36 PM

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1867 posts

cj13609517288

#24 h Apr 13, 2024, 10:22 PM • 2 Y

Y by MathLuis, megarnie

Solved (and typed up) with MathLuis.

The answer is
$\boxed{f(n)=n}, \boxed{f(n)=\begin{cases}\text{anything}&n=1\\1&n\ge2\end{cases}}, \boxed{f(n)=\begin{cases}\text{anything odd}&n=1\\2&n\text{ is even}\\1&\text{otherwise}\end{cases}}.$ The first function clearly works, the second function works as the LHS is always $1$ , and the third function works because the only way the LHS is $2$ is if $x+y$ is even, which will have the RHS be even as well.

If $f$ is injective then let $c=f(1)$ , we have that $f(x) \ne f(x+c)$ , so assume there exists $x$ with $f(x)+1 \ne f(x+c)$ then $f(x)>f(x+c)$ because we have $f(x+c) \mid f(x)+1$ from $P(1,x)$ . Now by an easy induction we can prove $f(x)>f(x+nc)$ for all positive integers $n$ therefore at some point some $f(x+kc)=0$ which can't happen, therefore for all positive integers $x$ we have $f(x+c)=f(x)+1$ therefore $f(x+nc)=f(x)+n$ , now by $P(x,y+nc)$ we have $f(f(x)+y)+n \mid x+f(y)+n$ but fix $x,y$ and let $n$ be large enough, this is enough to conclude that $f(f(x)+y))=x+f(y)$ for all integers $x,y$ . Call this $Q(x,y)$ then by $Q(x+c^2,y)$ we have $f(f(x)+y)+1=f(f(x)+y+c)=x+c^2+f(y)$ which implies $c^2=1$ and therefore $c=1$ so $f(1)=1$ and now as $f(x+1)=f(x)+1$ by an easy induction we have that $f(n)=n$ for all positive integers $n$ as desired.

Now suppose that $f$ is bounded. Then let the maximum value of $f$ that occurs infinitely many times be $T$ . Let the minimum nonzero $|a-b|$ such that $f(a)=f(b)$ be $D$ (this has to exist as $f$ is bounded).
Assuming $f(a)=f(b)$ , subtracting $P(a,y)$ and $P(b,y)$ (obviously they have the same LHS) gives
$f(f(a)+y)\mid |a-b|.$ Therefore, the values of $f$ that occur infinitely many times have to divide $D$ , meaning that $T\le D$ . Therefore, for large enough $x$ , $f(x)\le T\le D$ . However, note that since $D$ is minimal, $f$ must cycle through everything that is $\le D$ in the same order forever. Thus $T=D$ , so, $f$ is eventually periodic with period $T$ .

However, note that the values of $f$ have to divide $D$ , meaning that $d(D)=D$ , which is only true when $T=D\le 2$ .

Case 1. $T=1$ . Then there exists some $M$ such that for all $x\ge M$ , we have $f(x)=1$ . Then $P(M,y)$ and $P(M+1,y)$ give
$f(1+y)\mid M+f(y)$ and
$f(1+y)\mid M+1+f(y),$ respectively, so $f(1+y)=1$ for all $y$ , meaning that $f(x)=1$ for all $x\ge 2$ .

Case 2. $T=2$ . Then note that $f$ can alternate in two ways for large $x$ ( $12121212\dots$ or $21212121\dots$ ). Setting $x$ and $y$ to be sufficiently large and the same parity, the LHS will be $2$ , so $x$ and $f(x)$ must be the same parity for all large $x$ . Thus there exists some $M$ such that for all $x\ge M$ , $x\equiv f(x)\pmod 2$ and $f(x)\le 2$ . Similarly to the first case, subtracting $P(M,y)$ and $P(M+2,y)$ gives $f(1+y)\mid 2$ for all $y$ , so $f(x)\le 2$ for all $x\ge 2$ . Now note that $D=T=2$ , meaning that we cannot have consecutive values be the same, so indeed $x\equiv f(x)\pmod 2$ for all $x\ge 2$ as well, meaning that $M\le 2$ . Finally, $P(1,2)$ gives
$f(f(1)+2)\mid 3,$ so $f(1)$ has to be odd.

We are done! $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Ywgh1

136 posts

Ywgh1

#26 h Jan 7, 2025, 6:47 AM

Y by

v_Enhance wrote:

Solution from Twitch Solves ISL:

There are three families of solutions:

$f$ is the identity function;
$f(n) = 1$ for $n \ge 2$ , where $f(1)$ is any positive integer.
$f(n) = 2$ for $n$ even, $f(n) = 1$ for odd $n \ge 3$ , and $f(1)$ is any odd positive integer.

The verification is easy, so we prove these are the only solution. The proof is split into two main cases.

The second case you mean $f$ is injective.

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

298 posts

Ilikeminecraft

#27 h Mar 9, 2025, 4:45 AM

Y by

interesting

We do casework on if $f$ is injective or not.

If $f$ is injective, let $f(1) = c.$ Take $x = 1,$ and we get $f(y + c) \mid y + c.$ Hence, $f(n) \leq \frac nc + \max\{f(1), f(2), \dots, f(c)\}$ (this can be seen as modular arithmetic). By taking a sufficeintly large $n,$ we see this forces $c = 1$ from the injectivity condition. This automatically implies $f\equiv x.$

Assume $f$ isn't injective now. Let $f(a) = f(b)$ such that $a - b > 0$ is minimized. Take $x = a, x = b$ to get $f(f(a) + n)\mid a + f(n), b + f(n).$ By Euclidean algorith, we deduce $f(n) \mid a - b$ for all sufficiently large $n.$ Next, note that $\{f(M), f(M + 1), \dots, f(M + a - b - 1)\}$ must all be distinct. However, they all need to be divisors of $a - b.$ Hence, there are at least $a - b$ divisors of $a - b.$ Clearly, this implies $a - b \leq 2$

If $a - b = 1,$ take $C$ to be some sufficiently large number, and $x\geq2$ be an integer. Take $(C, x - 1),$ we get $f(x)\mid C + f(x - 1)$ for all sufficiently large $C.$ Hence, $f(x) = 1.$ Clearly, $f(1)$ can be any value.

If $a - b = 2,$ we know $f$ alternates between 1 and 2. Clearly, we require $f(2k) = 2, f(2k + 1) = 1$ for $k\geq1,$ and $f(1)$ is any integer.

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8853 posts

HamstPan38825

#28 h Monday at 10:38 PM

Y by

Not that bad for problem 6! The answers are:

$f \equiv x$ ;
$f(1) = k$ and $f(n) = 1$ for all $n \geq 2$ and some $k \in \mathbb N$ ;
$f(1) = k$ and $f(n) = 2 - (n \bmod 2)$ for all $n \geq 2$ and some $k \in \mathbb N$ .

We split into two cases now.

First Case: Suppose that $f$ is injective. By setting $x = 1$ , we obtain $f(y+f(1)) \leq f(y) + 1$ . In particular, if $f(1) > 1$ , then $f(x) < cx$ for some constant $c$ and sufficiently large positive integers $x$ , which contradicts injectivity.

If $f(1) = 1$ , then $f(y+1) \mid f(y) + 1$ for all positive integers $y$ and furthermore $f(f(x) + x) \mid f(x) + x$ . Indeed, inductively, we may prove by injectivity that $f(y+1) = f(y) + 1$ holds for every positive integer $y$ , and it follows that $f(f(x) + x) = f(x) + x$ for sufficiently large $x$ . These are enough to imply $f \equiv x$ .

Second Case: Suppose that there exist $x_1$ and $x_2$ with $f(x_1) = f(x_2) = c$ . Then, for all positive integers $y$ , $f(y+c)$ divides both $x_1+f(y)$ and $x_2 + f(y)$ , hence it divides $x_2 - x_1$ .

It follows that for $f(n)$ only takes finitely many values. Let $D$ be the smallest positive integer for which there exists positive integers $x_1$ and $x_2$ such that $x_2-x_1=D$ and $f(x_1) = f(x_2)$ . It follows that $f(x_1), f(x_1+1), \dots, f(x_1 + D-1)$ are all distinct divisors of $D$ , i.e. $D$ has at least $D$ distinct divisors. Thus $D \in \{1, 2\}$ . We will resolve the $D = 2$ case only; the $D = 1$ case resolves itself similarly.

Let $x$ be a large positive integer such that $f(x) = f(x+2) = 1$ . Then $f(y+1) = f(y+f(x))$ divides $x+f(y)$ , but $f(y+1) = f(y+f(x+2))$ also divides $x+f(y) + 2$ , hence $f(y+1) \mid 2$ for all $y \geq 1$ .

It follows that for all $n \geq 2$ , $f(n) \equiv f(n \bmod 2) \in \{1, 2\}$ , and we must have $f(1 \bmod 2) = 1$ and $f(2 \bmod 2) = 2$ by setting $x$ odd and $y$ even, for instance. $f(1)$ can take any value, so we are done.

Z K Y

N Quick Reply