IMO 2011 Problem 5

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#1 h Jul 19, 2011, 12:00 PM • 15 Y

Y by Davi-8191, microsoft_office_word, megarnie, son7, ChuongTk17, Adventure10, Mango247, ItsBesi, and 7 other users

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$ , the difference $f(m) - f(n)$ is divisible by $f(m- n)$ . Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$ , the number $f(n)$ is divisible by $f(m)$ .

Proposed by Mahyar Sefidgaran, Iran

Z K Y

The post below has been deleted. Click to close.

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

m.candales

186 posts

m.candales

#2 h Jul 19, 2011, 1:28 PM • 19 Y

Y by lspecwave, zephyr7723, A-Thought-Of-God, Pitagar, lneis1, son7, megarnie, anar_mehdiyev, Adventure10, Mango247, Stuffybear, iamnotgentle, and 7 other users

-- $f(n)|f(0)$ for every integer $n$
$f(m)=f(m-0)|f(m)-f(0)$ . Then $f(m)|f(0)$

-- $f(-n) = f(n)$ for every integer $n$
$f(-n)=f(0-n)|f(0)-f(n)$ . Then $f(-n)|f(n)$ since $f(-n)|f(0)$ . Similarly $f(n)|f(-n)$ . Then $f(n)=f(-n)$

Suppose that $f(m) < f(n)$ and $f(m)$ doesn't divide $f(n)$ .
$f(m+n)=f(m-(-n))|f(m)-f(-n)=f(m)-f(n)$ . Then $f(m+n)\le f(n)-f(m) \ \ \ \ (*)$
$f(m)|f(n+m)-f(n)$ . Then $f(m)$ doesn't divide $f(n+m)$ . Then $|f(n+m)-fm)|$ is not $0$
$f(n)|f(n+m)-f(m)$ . Then $f(n)\le f(n+m)-f(m)$ or $f(n)\le f(m)-f(n+m)$
If $f(n)\le f(n+m)-f(m)$ , then $f(n)+f(m+n)\le f(m+n)+f(n)-2f(m)$ (adding with (*)), which is impossible
If $f(n)\le f(m)-f(n+m)$ , then $f(n)+f(n+m)\le f(n)-f(n+m)$ (adding with (*)), which is impossible

Therefore if $f(m)\le f(n)$ , we must have that $f(m) |f(n)$

This post has been edited 1 time. Last edited by m.candales, Jul 19, 2011, 1:37 PM

Z K Y

The post below has been deleted. Click to close.

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

howsiyu

1 post

howsiyu

#3 h Jul 19, 2011, 1:36 PM • 5 Y

Y by son7, Adventure10, Mango247, and 2 other users

here is the sketch.
1. f(x) l f(0)
2. f(x) l f(-x), f(-x) l f(x)
3. f(x)=f(-x)
4.f(x+y) l f(x)+f(y), f(x) l f(x+y)-f(y), f(y) l f(x+y)-f(x)
5. two of .f(x+y), f(x), f(y) are the same.
6. f(a) l f(b) or f(b) l f(a) if a,b are x, y or x+y

Z K Y

The post below has been deleted. Click to close.

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

hungnguyenvn

50 posts

hungnguyenvn

#4 h Jul 19, 2011, 5:31 PM • 2 Y

Y by Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

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

Learner94

634 posts

Learner94

#5 h Jul 19, 2011, 5:48 PM • 6 Y

Y by dizzy, son7, Adventure10, and 3 other users

Solution:

We have $f(m-n)|f(m)-f(n)$ setting $n=0$ gives $f(m)|f(0)$ , setting $m=0$ we get $f(-n)|f(n)$ implying $f(n)|f(-n)$ hence $f(-n)= f(n)$ .This gives $f(m+n)|f(m)-f(n)$ , If $f(n)\geq f(m)$ we have $f(m+n)\leq f(n)-f(m)$ .Further $f(n)|f(m+n)-f(m)$ .This implies we may have $(i) f(n)\leq f(m+n)-f(m)$ but from the previous inequality $f(m+n)+f(m)\leq f(n)\leq f(m+n)-f(m)$ which means $2f(m)\leq 0$ clearly impossible.We consider case $(ii) f(n)\leq f(m)-f(m+n)$ , but this ,with $f(n)\geq f(m)$ , gives $f(m)+f(m+n)\leq f(n)+f(m+n)\leq f(m)$ ,giving $f(m+n)\leq 0$ , again not possible.The last case $(iii)$ and the only possibility is $f(m+n)= f(m)$ .But we have $f(m)|f(m+n)-f(n)$ implying $f(m)|f(m)-f(n)$ . Hence we must have $f(m)|f(n)$ , and we are done!

This post has been edited 1 time. Last edited by Learner94, Jul 19, 2011, 6:35 PM

Z K Y

The post below has been deleted. Click to close.

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

TheStrayCat

161 posts

TheStrayCat

#6 h Jul 19, 2011, 6:30 PM • 5 Y

Y by donot, Adventure10, Mango247, and 2 other users

Here's my convoluted solution I'm not totally sure about. If anyone takes the time and checks this stream of consciousness, I'll be happy.

First, $n=0$ -> $f(m)|f(0)$ for every integer $m$ .
Then, since we have $f(1)|f(1), f(1)|f(2)-f(1), f(1)|f(3)-f(2), ...$ for both positive and negative integers, for every integer $m$ we have $f(1)|f(m)$ . Therefore we can replace our function with $f_1(x)=f(x)/f(1)$ , making sure this affects neither the conditions nor the required result.

Similarly, we get $f(-1)=1$ . Next, using the basic statement we have that for all integral variables $f(m)|f(km)$ . Since the function is positive, employing $k=-1$ we obtain it's even.

Now suppose there's number $m$ for which $f(m)>1$ and $f(m-1)>1$ . Substituting $1$ in the place of $n$ , we have that $f(m-1)|f(m)-1$ , and doing the same with $m-1$ and $-1$ , $f(m)|f(m-1)-1$ . Hence, at least one value, $f(m-1), f(m)$ must equal 1 and we have a contradiction.

Denote the set of all integers $m$ for which $f(m)>1$ as $P$ . As shown above, $m \in P$ entails $km \in P$ . Now we'll show that $m \in P$ and $n \in P$ entail $(m+n) \in P$ . Really, if $f(m+n)=1$ , then according to the statement $f(n)|f(m)-1$ and $f(m)|f(n)-1$ , hence, either of these values is equal to one, which is against our assumption. So, if $f(m)>1, f(n)>1, f(p)>1$ , for any integer multipliers $f(am+bn+cp)>1$ (*).

On the other hand, no pair of coprime numbers can be contained in $P$ - otherwise we can find two neighbouring numbers each of them dividing one of the taken. Given all this, we conclude that all numbers of $P$ share a divisor $s$ greater than $1$ . [If a set of numbers has no common divisor, there exists a number that is coprime with all of them and can be expressed as their combination like (*)]. In this case, we introduce a new function $f_2(x)=f(x/s)$ and continue the same steps for it. Numbers which are not divisible by $s$ can be disregarded, because they satisfy the needed condition anyway. Step by step, every number will be reached in this way at some point and our construction proves what is necessary.

This post has been edited 1 time. Last edited by TheStrayCat, Jul 22, 2011, 9:03 PM

Z K Y

The post below has been deleted. Click to close.

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

mszew

1046 posts

mszew

#7 h Jul 19, 2011, 8:12 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Is it possible to find all f?

Z K Y

The post below has been deleted. Click to close.

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

mavropnevma

15142 posts

mavropnevma

#8 h Jul 19, 2011, 8:32 PM • 5 Y

Y by Adventure10, Mango247, and 3 other users

Surely your example is not good, since $f$ takes positive values. However, the post above you opens some hope on such a question.

Definitely $f$ is even, the fibres of $f$ are finitely many, and $\textrm{Im} f$ is a finite chain $C$ in $(\mathbb{Z}_+^*, \mid)$ , with $\min C = f(\pm 1)$ and $\max C = f(0)$ . How much definition can we bring as to the structure of $f$ ?

Z K Y

The post below has been deleted. Click to close.

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

Zhero

2043 posts

Zhero

#9 h Jul 19, 2011, 11:29 PM • 6 Y

Y by Adventure10, Mango247, navi_09220114, and 3 other users

I believe the functions can be characterized as follows:

Let $1 = a_1 < a_2 < \cdots < a_t$ be integers, with $a_1 \, | \, a_2 \, | \, \cdots \, | \, a_t$ , and let $c_1 < c_2 < \ldots < c_t$ be any integers such that $c_1 \, | \, c_2 \, | \, \cdots \, | \, c_t$ . For any nonzero integer $k$ , let $\alpha(k)$ be the largest integer $i$ such that $a_i | k$ . Then $f(k) =c_{\alpha(k)}$ for all nonzero $k$ , and $f(0)$ is any multiple of $c_t$ .

Please inform me if the following solution has any errors:
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

veyron

16 posts

veyron

#10 h Jul 20, 2011, 3:00 AM • 5 Y

Y by ali.agh, Adventure10, Mango247, and 2 other users

a different approach:
1. $f(n)|f(0)$
2. $f(n)=f(-n)$
3. $f(n)|f(kn)$
4. let $am+bn=gcd(m,n)$
then $f(bn)|f(am)-f(gcd(m,n))$
$f(am)|f(bn)-f(gcd(m,n))$
at least one of $f(am)-f(gcd(m,n))$ , $f(bn)-f(gcd(m,n))$ equals 0
we have $f(am) \ge f(m) \ge f(gcd(m,n))$ $f(n) \ge f(m)$
so $f(am)=f(m)=f(gcd(m,n))$
and $f(gcd(m,n))|f(n)$
we have $f(m)|f(n)$

Z K Y

The post below has been deleted. Click to close.

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

mathmdmb

1547 posts

mathmdmb

#11 h Jul 20, 2011, 6:49 AM • 1 Y

Y by Adventure10

orl wrote:

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers m and n, the difference $f(m) - f(n)$ is divisible by $f(m- n).$ Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$ , the number $f(n)$ is divisible by $f(m).$

Proposed by Mahyar Sefidgaran, Iran

Nice problem.

We use the facts: $a,b\in\mathbb{N}a|b\implies b\ge a$ and $a|b\pm a\implies a|b$ .

First let's prove that $f$ is an even function.
Set $n=0$ giving that $f(m)|f(m)-f(0)\implies f(m)|f(0)\forall m$ . Setting $m=0$ , we get $f(-n)|f(n)$ and since $f$ is defined for all integers, it is symmetric for $n$ and $-n$ implying $f(-n)=f(n)$
Then expand using $m+n=m-(-n)$ to note that $f(m+n)|f(m)-f(n)$ . Since the co-domain of $f$ is $\mathbb{N}$ we have three cases.

Case 1:
$f(m)-f(n)\ge f(m+n)$ . But we have $f(m)=f(m+n-n)|f(m+n)-f(n)$ giving $f(m)-f(n)\ge f(m+n)\ge f(m)+f(n)$ $\implies f(m)+f(n)\le f(m)-f(n)\implies 2f(n)\le 0$ , contradiction since $f(m)\in\mathbb{N}$ .

Case 2:
$f(m)\le f(n)-f(m+n)$ which is almost similar using the given fact $f(n)\ge f(m)$ and not possible.

Case 3:
$f(m+n)=f(m)$ holds as the only possibility.
Then $f(m)|f(m+n)-f(m)=f(n)-f(m)\implies f(m)|f(n)$ .
We are done.

Edit: Since most solutions use the same idea, I was thinking to solve this using induction. Is it possible with induction? Also, may be in the cases I have reversed the order of $m$ and $n$ .

Z K Y

The post below has been deleted. Click to close.

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

Samanyolu

15 posts

Samanyolu

#12 h Jul 20, 2011, 10:22 PM • 3 Y

Y by Adventure10 and 2 other users

What do you think about this solution?
1. f(m) divides f(0) for all m integers. So, f(m) can take a finite number of values.
2. We can partition the integers into a finite number of sets S1, S2, ..., Sr so that for all i all elements of Si have same image f(Si) under f.
3. WLOG assume that f(S1)<f(S2)<...<f(Sr)
4. Since f(m-n)|f(m)-f(n), we can find 1<=t<=r so that f(St)|f(Sj)-f(Si) for all 1<=i<j<=r
5. We prove by induction on r that f(S1)|f(S2)|.....|f(Sr).

Z K Y

The post below has been deleted. Click to close.

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

yunxiu

571 posts

yunxiu

#13 h Jul 21, 2011, 1:43 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

mszew wrote:

"Is it possible to find all f?For example:
$f(n) \in \{a,-a\}$ and $f(0)=k a$

Another example: $f(odd)=a$ , $f(even)=ab$ , $f(0)=abc$ .

Z K Y

The post below has been deleted. Click to close.

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

SCP

1502 posts

SCP

#14 h Jul 21, 2011, 5:56 PM • 1 Y

Y by Adventure10

mathmdmb wrote:

orl wrote:

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers m and n, the difference $f(m) - f(n)$ is divisible by $f(m- n).$ Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$ , the number $f(n)$ is divisible by $f(m).$

Proposed by Mahyar Sefidgaran, Iran

Case 1:
$f(m)-f(n)\ge f(m+n)$ . But we have $f(m)=f(m+n-n)|f(m+n)-f(n)$ giving $f(m)-f(n)\ge f(m+n)\ge f(m)+f(n)$ $\implies f(m)+f(n)\le f(m)-f(n)\implies 2f(n)\le 0$ , contradiction since $f(m)\in\mathbb{N}$ .

.

Wrong

f(m)|f(m+n)-f(n)=0 gives
f(m)+f(n ge f(m+n) here with f; qnd f(m+n) different

Hence it is wrong qnd zouldn`t get more than four and you hqve typo in casa2

Z K Y

The post below has been deleted. Click to close.

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

mavropnevma

15142 posts

mavropnevma

#15 h Jul 21, 2011, 7:35 PM • 16 Y

Y by ali.agh, Adventure10, Mango247, sabkx, and 12 other users

Again, a fat-less late proof. Let us first gather some trivial results.

Since $f(m)=f(m-0)\mid f(m)-f(0)$ , it follows $f(m)\mid f(0)$ for every integer $m$ .
We now have $f(-n)=f(0-n)\mid f(0)-f(n)$ , so $f(-n)\mid f(n)$ , since $f(-n)\mid f(0)$ . Then also $f(n)\mid f(-n)$ , therefore $f(n)=f(-n)$ (they are both positive).

Now we can write
$f(m-n) \mid f(m) - f(n),$
$f(n) \mid f(m) - f(m-n),$
$f(m) \mid f(n) - f(n-m) = f(n) - f(m-n),$
therefore we have three positive integers, each dividing the difference of the other two. That is only possible if two of them are equal, and dividing the third, so for $f(m) \leq f(n)$ we either have $f(m) = f(n)$ , or else we can say even more, namely $f(m-n) = f(m) \mid f(n)$ .

What can we say about such functions? It is now time for some elementary group theory. Define the fibre $\Omega =f^{-1} (\omega)$ that contains $0$ .
In general, we must have $\Omega - \Omega \subseteq \Omega$ , since for any elements $m,n \in \Omega$ we have $\omega = f(n) \mid f(m) - f(m-n) = \omega - f(m-n)$ , implying $f(m-n) = \omega$ , hence $m-n \in \Omega$ . Therefore $\Omega$ is some additive subgroup $(k\mathbb{Z},+) \subsetneq (\mathbb{Z},+)$ .

Clearly, a constant $f$ fulfills.
If $f$ takes more than one value, and it may only take finitely many, all divisors of $\omega = f(0)$ (so $\textrm{Im} f$ is a finite chain in the poset $(\mathbb{N}^*, \mid)$ , of maximal element $\omega$ ), then it is easy to show that $\alpha = f(\pm 1)$ divides them all.

A non-constant example with only two fibres $0\in \Omega =f^{-1} (\omega)$ , $\pm 1 \in A=f^{-1} (\alpha)$ (with $\alpha \mid \omega$ ) will have to have $A = \mathbb{Z} \setminus \Omega$ , with $\Omega$ some additive subgroup $(k\mathbb{Z},+) \subsetneq (\mathbb{Z},+)$ .

This can most likely be pursued even farther - I will append any further progress ...

Z K Y

The post below has been deleted. Click to close.

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

YaoAOPS

1541 posts

YaoAOPS

#75 h Sep 22, 2023, 3:06 PM • 1 Y

Y by radian_51

Claim: The image of $f$ is the divisors of $f(0)$ .
Proof. Since $f(m) \mid f(m) - f(0)$ for all $m$ it follows that $f(m) \mid f(0)$ . $\blacksquare$
As such, let the divisors of $c$ be $1 = d_1 < d_2 < \dots < d_{k-1} < d_k = f(0)$ .

Claim: For all $n$ , $d_i \mid d_n$ for $i \le n$ .
Proof. The base case of $k$ follows immediately. We now induct downwards. Suppose that it holds for $i + 1, \dots, k$ .
Take minimal $t \ne 0$ such that $f(n) = d_i$ .
Suppose that $f(m) < f(n)$ . Then $d_i \mid f(m + n) - f(n)$ . $f(m + n)$ is also a divisor of $f(0)$ . Since $f(m) \not\equiv 0 \pmod{d_i}$ , it follows that $f(m + n)$ can't be a divisor larger than $d_n$ , which implies $f(m + n) = f(m)$ .
As such, it follows that $f(m) \mid f(m + n) - f(n)$ , so $f(m) \mid f(n)$ follows. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

thdnder

198 posts

thdnder

#76 h Oct 5, 2023, 4:54 PM • 1 Y

Y by radian_51

Let $P(m, n)$ be given assertion. $P(n, 0)$ gives $f(n) \mid f(0)$ . Then $P(0, n)$ gives $f(-n) \mid f(0) - f(n)$ , so $f(-n) \mid f(n)$ . Similarly we have $f(n) \mid f(-n)$ . Therefore $f(n) = f(-n)$ .

Now let $m ,n$ be positive integers such that $f(m) \le f(n)$ . Let $a = f(m),b = f(n), c= f(n - m)$ . Then we have $a \mid b - c$ and $c \mid b - a$ . Since $f(n) = f(-n) \mid f(m - n) - f(m)$ , so $b \mid c - a$ . If $b = \max(a, b ,c)$ , then since $b \mid c - a$ , so $c = a$ . Thus $a \mid b$ . So $c = \max(a, b, c)$ . Therefore $a = b$ . So in all case $f(m) \mid f(n)$ . Thus we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8868 posts

HamstPan38825

#77 h Dec 17, 2023, 6:26 PM • 1 Y

Y by radian_51

Plugging in $0$ for $m, n$ respectively yields
$\begin{align*} f(m) &\mid f(m) - f(0) \\ f(-n) &\mid f(0) - f(n). \end{align*}$ In particular, $f(m) \mid f(0)$ for every $m$ , which implies $f(-n) \mid f(n)$ . Symmetrically, this forces $f(n) = f(-n)$ .

Now assume $f(m) \geq f(n)$ and consider the relations
$\begin{align*} f(m) &\mid f(m+n) - f(n) \\ f(n) &\mid f(m+n) - f(m) \\ f(m+n) &\mid f(m) - f(n). \end{align*}$ Let $d = \gcd(f(m), f(n))$ , and let $f(m) = dx$ , $f(n) = dy$ , $f(m+n) = dz$ , where $\gcd(x, y) = 1$ . Then we have the divisibility relations $x \mid z-y$ , $y \mid z-x$ , and $z \mid x-y$ . In particular, $xy \mid z-y-x$ as $\gcd(x, y) = 1$ .

On the other hand, as $z \mid x-y$ , it follows that $|z-y-x| < x+y$ and thus $xy < x+y$ . As $(x, y) = (2, 2)$ is invalid, this forces $x=1$ or $y = 1$ , which is clearly enough.

This post has been edited 1 time. Last edited by HamstPan38825, Dec 17, 2023, 6:26 PM

Z K Y

The post below has been deleted. Click to close.

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

amazingtheorem

17 posts

amazingtheorem

#78 h Jan 21, 2024, 1:29 PM • 1 Y

Y by radian_51

Let $P(m,n)$ be the assertion of $f(m-n)\mid f(m)-f(n)$ .
First, $P(a,0)$ asserts that $f(a)\mid f(a)-f(0) \implies f(a)\mid f(0)$ for all $a \in \mathbb{Z}$ .
Lemma 1. We have $f(a)=f(-a)$ for all $a\in \mathbb{Z}$ .
Note that for every $n\in \mathbb{Z}$ , $P(n+ik+k,n+ik)$ asserts that $f(n+ik+k)\equiv f(n+ik) \pmod {f(k)}$ . This means, $\cdots\equiv f(n-2k)\equiv f(n-k) \equiv f(n)\equiv f(n+k)\equiv f(n+2k)\equiv \cdots \pmod{f(k)}$ . In other word, if there is positive integers $k,a$ , and $b$ with $k\mid a-b$ , then we have $f(k)\mid f(a)-f(b)$ .
Now, if there is an integer $t$ such that $a=kt$ , taking $b=k$ , we have $k\mid a-b$ . This implies $f(k)\mid f(kt)-f(k) \implies f(k)\mid f(kt)$ . Hence, $f(k)\mid f(kt)$ for all integers $t$ .
Hence, we now have $f(k)\mid f(-k)$ and $f(-k)\mid f(k)$ . This forces $f(k)=f(-k)$ for all integer $k$ . $\blacksquare$
For the sake of contradiction, assume that there is $a,b\in \mathbb{Z}$ such that $f(b)>f(a)$ , but $f(a)\nmid f(b)$ .
Now, $P(a,a-b)$ and $P(b,b-a)$ assert that $f(b)\mid f(a)-f(a-b)\implies f(b)\mid f(a)+f(b)-f(a-b)$ and $f(a)\mid f(a)+f(b)-f(a-b)$ , consecutively. This implies $lcm(f(a),f(b))\mid f(a)+f(b)-f(a-b)$ .
However, by $P(a,b)$ , we have $f(a-b)\mid f(b)-f(a) \implies f(a-b)\le f(b)-f(a) \implies f(a)+f(b)-f(a-b)\ge 2f(a)>0$ .
From $f(a)\nmid f(b)$ , we have $lcm(f(a),f(b))\ge 2f(b)$ . This implies $2f(b)\le lcm(f(a),f(b)) \le f(a)+f(b)-f(a-b) \implies f(b)\le f(a)-f(a-b) <f(a) \implies f(b)<f(a)$ which is a contradiction.
Hence, it is true that for all $m,n \in \mathbb{Z}$ with $f(m)\le f(n)$ , we must have $f(m)\mid f(n)$ .

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

799 posts

shendrew7

#79 h Mar 19, 2024, 4:03 AM • 1 Y

Y by radian_51

Substituting $(x,0)$ , $(-x,0)$ , $(0,x)$ , $(0,-x)$ tells us $f(x)=f(-x)$ , so we only need to focus on $x \in \mathbb{Z}_{\ge 0}$ .

Suppose we have $a+b+c=0$ for integers $a$ , $b$ , $c$ . Then we have
$f(a) \mid f(-b) - f(-c) = f(b)-f(c)$
and cyclic permutations, from which it follows that the minimum two of $f(a),f(b),f(c)$ must be equal. Substituting back into our system, they must both divide the maximum, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

ihatemath123

3449 posts

ihatemath123

#80 h Nov 19, 2024, 3:26 PM • 1 Y

Y by radian_51

Taking $P(m,0)$ gives us $f(m) \mid f(m) - f(0) \implies f(m) \mid f(0)$ for all $m$ . Taking $P(0,m)$ and $P(0,-m)$ implies that $f$ is even.

Claim: We have $f(a) \mid f(b)$ whenever $a \mid b$ .
Proof: Since $f$ is even, assume WLOG that $a$ and $b$ are positive. Then, we have $f(a) \mid f(ak) - f(a(k-1))$ , so adding these divisibilities together over $k=1, 2, \dots, \tfrac{b}{a}$ gives us the desired claim.

So, $f(1) \mid f(m)$ for all $m$ . From hereon, assume WLOG that $f(1) = f(-1) = 1$ .

Claim: If $f(a) \neq 1$ and $f(b) \neq 1$ , then $f(a-b) \neq 1$ .
Proof: Assume FTSOC that $f(a-b) = f(b-a) = 1$ . From $P(b,b-a)$ and $P(a, a-b)$ we have
$\begin{cases} f(a) & \mid f(b) - 1 \\ f(b) & \mid f(a) - 1. \end{cases}$ Since both $f(a)$ and $f(b)$ are greater than $1$ , this implies that $f(a) > f(b)$ and $f(b) > f(a)$ , giving us a contradiction.

So, by the Euclidean algorithm, the values of $f$ which map to something not equal to $1$ are all multiples of $k$ for some integer $k \geq 2$ (here we use our first claim as well). We now finish the problem with induction on $f(0)$ :

The base case of $f(0) = 1$ is trivial.
We will show that the problem statement is true for $f(0) = C$ if it is true for $f(0)$ equal to every proper divisor of $C$ . If $f(x) = 0$ for all positive integers $x$ , we are automatically done. Otherwise, from our previous claim, there exists an integer $k \geq 2$ for which $f(x) \neq 1$ if and only if $k \mid x$ . From our first claim, for any multiple $x$ of $k$ , $f(k) \mid f(x)$ . Therefore, the function
$g(x) = \frac{f(kx)}{f(k)}$ satisfies the same conditions set on $f$ by the problem statement. By assumption, $f(k) > 1$ , so $g(0)$ is a proper divisor of $f(0)$ , thus the inductive assumption holds on $g$ .

Z K Y

The post below has been deleted. Click to close.

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

L13832

268 posts

L13832

#81 h Dec 16, 2024, 4:36 AM • 1 Y

Y by radian_51

Is this correct?
Redacted

This post has been edited 1 time. Last edited by L13832, Apr 2, 2025, 8:24 PM

Z K Y

The post below has been deleted. Click to close.

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

ItsBesi

146 posts

ItsBesi

#84 h Jan 1, 2025, 6:26 PM

Y by

Does this work?

Let $P(m,n)$ denote the given assertion.

Claim: $f(n)=f(-n) \forall n \in \mathbb{Z} \iff f-\text{even}$

Proof:

$P(n,0) \implies f(n) \mid f(n)-f(0) \implies f(n) \mid -f(0) \implies f(n) \mid f(0), n \rightarrow -n \implies \boxed{ f(-n) \mid f(0)}$ $...(*)$

$P(0,n) \implies f(n) \mid f(0)-f(n)$ , combining with $(*)$ we get: $f(n) \mid f(-n) , n \rightarrow -n \implies f(-n) \mid f(n) \therefore f(-n) \mid f(n) \mid f(-n) \implies f(n)=f(-n) \iff f-\text{even}$ $\square$

Now by taking $P(n,-1) , P(n+1,n) \text{and} P(n+1,1)$ and combining with $f-\text{even}$ we get:

$\boxed{f(n+1) \mid f(n)-f(1)}$ $...(1)$

$\boxed{f(1) \mid f(n+1)-f(n)}$ $...(2)$

$\boxed{f(n)\mid f(n+1)-f(1)}$ $...(3)$

Now we seperate the problem into $2$ cases.
Case 1. $f(n+1) \geq f(n)$ .
From $(1) \implies f(n+1) \mid f(n)-f(1) \text{but since} LHS > RHS \implies RHS=0 \implies f(n)-f(1)=0 \implies f(n)=f(1)$
$(LHS>RHS \because f(n+1) \geq f(n) )$

By $(3) \implies f(n)\mid f(n+1)-f(1) \implies f(n) \mid f(n+1)-f(n) \implies \boxed{f(n) \mid f(n+1)}$
So $\forall m$ s.t $f(n) \leq f(m) \implies f(n) \mid f(m)$ $\square$

Case 2. $f(n) \geq f(n+1)$
We begin by making the following claim

Claim: $f(1) \leq f(n)$

Proof: From $(2) \implies f(1) \mid f(n+1)-f(n)$ but since $f(n) \geq f(n+1)$ we get:
$f(1) \mid f(n)-f(n+1) \implies f(1) \leq f(n)-f(n+1) so f(1) \leq f(1)+f(n+1) \leq f(1)+f(n) \leq f(n) \implies \boxed{f(1) \leq f(n)}$ $\square$

Subcase 2.1 $f(n+1) \geq f(1)$

From $(3) \implies f(n) \mid f(n+1)-f(1)$ but $LHS>RHS \implies RHS=0 \implies f(n+1)=f(1)$

From $(1) \implies f(n+1) \mid f(n)-f(1) \implies f(n+1) \mid f(n)-f(n+1) \implies \boxed{f(n+1) \mid f(n)}$
So $\forall m$ s.t $f(m) \leq f(n) \implies f(m) \mid f(n)$ $\square$

Subcase 2.2 $f(n+1) <f(1)$

From $(3) \implies f(n) \mid f(n+1)-f(1)$ but $LHS >RHS \implies RHS=0 \implies f(n+1)-f(1)=0 \implies f(n+1)=1 \rightarrow \leftarrow$ $\blacksquare$

100th post

This post has been edited 2 times. Last edited by ItsBesi, Jan 4, 2025, 3:18 PM
Reason: 100th post

Z K Y

The post below has been deleted. Click to close.

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

RedFireTruck

4243 posts

RedFireTruck

#85 h Jan 10, 2025, 6:20 AM

Y by

Plugging in $n=0$ gives $f(m)|f(0)$ .

Plugging in $m=0$ gives $f(-n)|f(n)$ , so $f(n)=f(-n)$ .

FTSOC, assume that $f(m)\le f(n)$ and $f(m)\not |f(n)$ .

We see that $f(m+n) | (f(m)-f(n))$ . If $f(m+n)\ge f(n)$ , then $f(m)=f(n)$ . Therefore, we assume $f(m+n)<f(n)$ . Then, $f(n)|(f(m+n)-f(m))$ , so $f(m+n)=f(m)$ . Then, since $f(m)=f(m+n) | (f(m)-f(n))$ , $f(m)|f(n)$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

g0USinsane777

48 posts

g0USinsane777

#86 h Jan 16, 2025, 4:34 AM

Y by

Let $P(m,n)$ denote the assertion $f(m-n)|f(m)-f(n)$
Take some $f(x)>f(y)$
$P(y, y-x)$ gives us $f(x)|f(y)-f(y-x)$ , but we have that $f(y)-f(y-x) < f(y) < f(x)$ , which gives us that $f(y)=f(y-x)$
$P(y,x)$ gives that $f(y-x)=f(y)|f(y)-f(x)$ , which means that $f(y)|f(x)$ , giving what is desired.

Z K Y

The post below has been deleted. Click to close.

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

pie854

243 posts

pie854

#87 h Feb 13, 2025, 10:17 AM

Y by

Note that $f(m) \mid f(m)-f(0)$ implies $f(m) \mid f(0)$ . Now $f(n) \mid f(0)-f(-n)$ implies $f(n) \mid f(-n)$ . Taking $-n$ instead, we get $f(-n)\mid f(n)$ and thus $f(n)=f(-n)$ (since $f>0$ ).

Take $a, b$ such that $f(a)<f(b)$ . Taking $m=b, n=-a$ we get $f(a+b) \mid f(b)-f(a)$ which implies $f(a+b)<f(b)$ . Now taking $m=a+b, n=a$ we get $f(b) \mid f(a+b)-f(a)$ which implies $f(a+b)=f(a)$ since $|f(a+b)-f(a)|<f(b)$ . Finally, $f(a) \mid f(a+b)-f(b)=f(a)-f(b) \implies f(a)\mid f(b),$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

InterLoop

279 posts

InterLoop

#88 h Apr 15, 2025, 12:29 AM

Y by

solution

Z K Y

The post below has been deleted. Click to close.

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

Ihatecombin

65 posts

Ihatecombin

#89 h Apr 15, 2025, 2:44 AM

Y by

I'm just going to list a couple of useful results first.
Claim 1: $f(x) \leq f(0)$ for all $x$
Proof:
Notice that we can substitute $n = 0$ to obtain
$f(m) \mid -f(0)$ $\blacksquare$
Claim 2: $f(x)$ is even
Proof:
Notice that we can substitute $m = 0$ to obtain
$f(-n) \mid -f(n)$ $\blacksquare$
Claim 3: $f(x) \mid f(kx)$ for all integers $k$ , $x$
Proof:
Notice that we can sub $m = 2m$ and $n = m$ to have
$f(m) \mid f(2m)$ We use induction, let $m = km$ and $n = (k-1)m$ , this gives us
$f(m) \mid f(km)$ $\blacksquare$
Claim 4: Let $X$ denote the highest value which can be reached by $f(x)$ for $x \neq 0$ . If $a$ is the smallest natural number such that $f(a) = X$ , then $f(x+a) = f(x)$ .
Proof:
Let $m = n+a$ , then
$f(a) \mid f(n+a) - f(n)$ Since $f(x) \neq 0$ , it follows that $f(n+a) = f(n)$
$\blacksquare$
Claim 5:
$f(1) \mid f(x)$ for all $x$
Proof:
Notice that we can sub $m = n+1$ to obtain
$f(1) \mid f(n+1) - f(n)$ Induction finishes. $\blacksquare$
Now we shall define the sequence $a_{i}$ , where $a_{i}$ denotes the $i$ -th smallest value such that there exists $a_{1}, a_{2}, \dots, a_{i-1} \in \mathbb{N}$ and $a_{1}, a_{2}, \dots, a_{i-1} < a_{i}$ with $f(a_{j})$ being pairwise distinct and $f(a_{j}) \neq f(a_{i})$ for all $j < i$ . Obviously $a_{1} = 1$ and $f(a_{1}) \mid f(a_{2})$ by claim $5$ , we shall show by induction that if $f(a_{k}) \mid f(a_{k+1})$ for all $k \leq n-1$ , then $f(a_{n}) \mid f(a_{n+1})$ .

Notice that we have the equation
$f(m-n) \mid f(m) - f(n) \quad (1)$ and since $f(x)$ is even, we can sub $n = -n$ to obtain
$f(m+n) \mid f(m) - f(n) \quad (2)$ We can sub $m = a_{n+1}$ and $n = a_{n}$ in equation $1$ to obtain
$f(a_{n+1} - a_{n}) \mid f(a_{n+1}) - f(a_{n})$ However $f(a_{n+1} - a_{n}) \mid f(a_{n})$ by the induction hypothesis and thus
$f(a_{n+1} - a_{n}) \mid f(a_{n+1}) \quad (3)$ In equation $2$ we can sub $m = a_{n+1} - a_{n}$ and $n = a_{n}$ , this will give us
$f(a_{n+1}) \mid f(a_{n+1} - a_{n}) - f(a_{n}) \quad (4)$ In equation $2$ we can sub $m = a_{n} - a_{n+1}$ and $n = a_{n+1}$ to get
$f(a_{n}) \mid f(a_{n+1} - a_{n}) - f(a_{n+1}) \quad (5)$ If $f(a_{n+1} - a_{n}) = f(a_{n})$ , then we are done by equation $3$ . Hence assume FTSOC this is not the case. However this implies that $f(a_{n}) - f(a_{n+1} - a_{n}) > 0$ . Connecting this with equation $4$ implies that $f(a_{n}) > f(a_{n+1})$ , notice that $f(a_{n+1}) \neq f(a_{n+1} - a_{n})$ by definition. Thus combining equation $3$ and equation $5$ gives us that $f(a_{n+1}) > f(a_{n})$ . This is clearly a contradiction thus we are done.

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

400 posts

alexanderhamilton124

#90 h May 4, 2025, 12:57 PM • 2 Y

Y by L13832, fearsum_fyz

Pretty nice problem!

Let $P(m, n)$ be the assertion. $P(m, 0)$ gives $f(m) \mid f(0)$ , which means $f$ is bounded. $P(2n, n)$ gives $f(n) \mid f(2n) - f(n) \implies f(n) \mid f(2n)$ . $P(m, -m)$ gives $f(2m) \mid f(m) - f(-m) \implies f(m) \mid f(-m)$ as $f(m) \mid f(2m)$ . Similarly, $P(-m, m)$ gives $f(-2m) \mid f(-m) - f(m)$ , and as $f(-m) \mid f(-2m)$ , we have $f(-m) \mid f(m) \implies f(-m) = f(m)$ . Hence, $f$ is even.

$P(m, -n)$ gives $f(m + n) \mid f(m) - f(n)$ . Now consider any two integers, $x, y$ . If $f(m) = f(n)$ , we are done, so assume not. WLOG, $f(m) > f(n)$ .

Since $f(m + n) \mid f(m) - f(n)$ , and $f(m) - f(n)$ is positive, $f(m + n) < f(m)$ . However, we also have $f(m) \mid f(m + n) - f(n)$ . But, $f(m) > f(m + n)$ and $f(m) > f(n)$ , which means $f(m + n) = f(n)$ . This means $f(n) \mid f(m) - f(n) \implies f(n) \mid f(m)$ , and we're done.

Z K Y

The post below has been deleted. Click to close.

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

Markas

150 posts

Markas

#91 h May 11, 2025, 6:03 PM

Y by

Let n = 0. We get that $f(m) \mid f(m) - f(0)$ $\Rightarrow$ $f(m) \mid f(0)$ . Let m = 0, we have that $f(-n) \mid f(0) - f(n)$ $\Rightarrow$ $f(-n) \mid f(n)$ . From the statement we have that $f(m + n) \mid f(m) - f(-n)$ and plugging in m = 0 we have that $f(n) \mid f(0) - f(-n)$ $\Rightarrow$ $f(n) \mid f(-n)$ , but we have that $f(-n) \mid f(n)$ and $f(n) \mid f(-n)$ $\Rightarrow$ $f(-n) = f(n)$ . Using this into $f(m + n) \mid f(m) - f(-n)$ , gives us that $f(m + n) \mid f(m) - f(n)$ . Now since $f(n) \geq f(m)$ , we have that $f(n) - f(m) \geq f(m + n)$ . From the statement we have that $f(n) \mid f(m + n) - f(m)$ .
Case 1: $f(n) \leq f(m + n) - f(m)$ $\Rightarrow$ $f(m + n) + f(m) \leq f(n) \leq f(m + n) - f(m)$ , which is impossible since $f(m) > 0$ .

Case 2: $f(n) \leq f(m) - f(m + n)$ $\Rightarrow$ $f(m + n) + f(m) \leq f(n) \leq f(m) - f(m + n)$ , which is again impossible.

Case 3: f(m + n) = f(m). Since $f(m) \mid f(m + n) - f(n)$ and $f(m) \mid f(m + n)$ , then $f(m) \mid f(n)$ , which is what we wanted to show and we are ready.

This post has been edited 1 time. Last edited by Markas, May 11, 2025, 6:04 PM

Z K Y