For any function $f:\mathbb{N}\to\mathbb{N}$ we define $P(n)=f(1)f(2)...f(n)$ . Find all functions $f:\mathbb{N}\to\mathbb{N}$ st for each $a,b$ : $$P(a)+P(b) | a! + b!$$
Problem
Source: Iran MO 3rd round 2023 ,Day 2 P1
Tags: algebra
16.08.2023 11:44
I assume that $N$ is the set of positive integers, not including $0$. Answer:$P(n)=n!$. $P(a,b)=P(1,1) \implies f(1)|1 \implies f(1)=1$ $P(a,b)=P(2,1) \implies f(2)+1|3 \implies f(2)=2$ $P(a,b)=P(3,1) \implies 2.f(3)+1|7 \implies f(3)=3$ Let's prove that $f(x)=x$ by induction Let $f(1)=1,f(2)=2,...,f(k)=k$, we'll prove that $f(k+1)=k+1$ Firstly, $P(a,b)=P(k,k+1)$ gives us $k!(f(k+1)+1)|k!(k+2)$ $\implies f(k+1)+1|k+2 \implies f(k+1) \leq k+1$ $P(a,b)=P(k+1,1) \implies k!.f(k+1)+1|(k+1)!+1$ $\implies k!f(k+1)+1|(k+1)!+1-1-k!f(k+1)=k!(k+1-f(k+1))$ $(k!,LHS)=1$ so $k!f(k+1)+1|k+1-f(k+1) \geq 0$ We have $k!f(k+1)+1>k+1-f(k+1)$ so $f(k+1)=k+1$ as desired.
20.08.2023 21:02
bin_sherlo wrote: I assume that $N$ is the set of positive integers, not including $0$. Answer:$P(n)=n!$. $P(a,b)=P(1,1) \implies f(1)|1 \implies f(1)=1$ $P(a,b)=P(2,1) \implies f(2)+1|3 \implies f(2)=2$
$f(2)+1|3$ implies that $f(2)=2 \text{ or } 1$ @below my mistake
20.08.2023 21:53
$2$ doesn't divide $3$. hectorleo123 wrote: bin_sherlo wrote: I assume that $N$ is the set of positive integers, not including $0$. Answer:$P(n)=n!$. $P(a,b)=P(1,1) \implies f(1)|1 \implies f(1)=1$ $P(a,b)=P(2,1) \implies f(2)+1|3 \implies f(2)=2$
$f(2)+1|3$ implies that $f(2)=2 \text{ or } 1$
20.08.2023 23:12
Answer $f(n)=n$: Let $P(a,b)=P(a)+P(b)$ First we get $P(1,1)=2f(1)|2$ and $f(1)=1.$ Then, $P(2,1)=f(2)+1|3$ and $f(2)=2.$ $P(3,1)=2f(3)+1|7$ and $f(3)=3$. Let's prove it from induction $f(x)=x$. We get $P(a,1)=(a-1)!f(a)+1|a!+1$. If we use modular arithmetic, we get $ (a-1)!f(a)\equiv a!\mod((a-1)!f(a)+1)$ and $f(a)\equiv a\mod((a-1)!f(a)+1)$. Then $f(a)=((a-1)!f(a)+1)k+a$. From $(a-1)!f(a)+1|a!+1$ we get $f(a)\leq a$. Then finally $((a-1)!f(a)+1)k+a\leq a$ and $((a-1)!f(a)+1)k\leq 0$. Since $((a-1)!f(a)+1)\geq0$ we have $k=0$ and FINALLY $f(a)=a$
15.11.2023 23:01
$P(a)+P(b) | a!+b!$ Let $Q(a,b)$ be assertion of this fe $Q(1,1)$ $f(1)=1$ $Q(1,2)$ $f(2)+1 | 3$ $f(2)=2$ $Q(1,3)$ $2f(3)+1|7$ $f(3)=3$ Claim$f(a)=a$ for all $a$ By induction assume that is true until $f(n)=n$ and we will prove for $f(n+1)=n+1$ $Q(1,n)$ $1+n!f(n+1) | (n+1)!+1$ $1+n!f(n+1) | n!(n+1-f(n+1))$ $1+n!f(n+1) | (n+1-f(n+1))$ $LHS>RHS$ contradicition if $n+1 \geq f(n+1)$ so $f(n+1)=n+1$ $f(n)=n$
26.01.2024 08:55
Putting $b=1$ gives $P(a) \le a!$. So $P(1) \le 1$ hence $P(1) = 1$ and $f(1)=1$. Now, assume that for any $n \ge 1$ we have $f(n)=n$. We will induct on $n$ and prove that $f(n+1)=n+1$. Then, we have $P(n)=n!$. By $a=n+1, b=n$ we have $f(n+1)+1 |n+2 \implies f(n+1) \le n+1$. Putting $a=n+1$ and $b=1$ gives $P(n+1)+1 | (n+1)!+1 \implies P(n+1)+1 | (n+1)!-P(n+1)=n!(n+1-f(n+1))$. Moreover, $\gcd(n!, n!f(n+1)+1)=1$ so $n!f(n+1)+1 | n+1-f(n+1)$ So, $n!f(n+1)+1 \le n+1-f(n+1) \implies n \ge (n!+1)f(n+1)$ which is absurd. Hence, $f(n+1)=n+1$.
22.06.2024 22:04
The answer is $f(x)=x$ which obviously works. We will proceed by strong induction. If we set $a=b=1$ we get $2f(1)|2$ so we must have $f(1)=1$. Now we show if $f(x)=x$ for $1\leq x\leq n-1$ then $f(n)=n$. If we set $a=b=n$ we get after dividing by $2(n-1)!$ that $f(n)|n$. So set $f(n)=\frac{n}{d}$. Now set $a=1$ and $b=n$ yielding $1+\frac{x!}{d}|1+n!\Rightarrow 1+\frac{n!}{d}|d-1$. Since $d(d-1)-d\leq n^2-2n<n!$ so we must have $d-1=0$ implying that $f(n)=n$.
30.12.2024 22:12
Bruh I approached this so cautiously and it still succumbed so easily wth. Put $a=b=1$ to get $P(1)=1$. Then put $b=1$ and $a=2,3,4,...$ to get that $P(a)$ seems to be $a!$ which gives $f$ to be the indentity. We prove this inductively. Suppose till $k$, $f(k)=k$. Then $P(k+1)=f(k+1)k!$. Putting $a=k+1$ and $b=1$ gives $$k!f(k+1)+1 | (k+1)!+1 \implies k!f(k+1)+1 | (k+1)!-k!f(k+1) \implies k!f(k+1)+1 | (k+1)-f(k+1)/f(k+1)-k-1$$But the dividend is smaller than the positive divisor in both cases so it must be the case that $f(k+1)=k+1$ so we are done.