Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
Yesterday at 11:16 PM
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Yesterday at 11:16 PM
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
Line AT passes through either S_1 or S_2
v_Enhance   88
N 8 minutes ago by bjump
Source: USA December TST for 57th IMO 2016, Problem 2
Let $ABC$ be a scalene triangle with circumcircle $\Omega$, and suppose the incircle of $ABC$ touches $BC$ at $D$. The angle bisector of $\angle A$ meets $BC$ and $\Omega$ at $E$ and $F$. The circumcircle of $\triangle DEF$ intersects the $A$-excircle at $S_1$, $S_2$, and $\Omega$ at $T \neq F$. Prove that line $AT$ passes through either $S_1$ or $S_2$.

Proposed by Evan Chen
88 replies
v_Enhance
Dec 21, 2015
bjump
8 minutes ago
Inequality with a,b,c
GeoMorocco   4
N 13 minutes ago by Natrium
Source: Morocco Training
Let $   a,b,c   $ be positive real numbers such that : $   ab+bc+ca=3   $ . Prove that : $$\frac{\sqrt{1+a^2}}{1+ab}+\frac{\sqrt{1+b^2}}{1+bc}+\frac{\sqrt{1+c^2}}{1+ca}\ge \sqrt{\frac{3(a+b+c)}{2}}$$
4 replies
GeoMorocco
Apr 11, 2025
Natrium
13 minutes ago
China Northern MO 2009 p4 CNMO
parkjungmin   1
N 39 minutes ago by WallyWalrus
Source: China Northern MO 2009 p4 CNMO P4
The problem is too difficult.
1 reply
parkjungmin
Apr 30, 2025
WallyWalrus
39 minutes ago
Polynomial Squares
zacchro   26
N 41 minutes ago by Mathandski
Source: USA December TST for IMO 2017, Problem 3, by Alison Miller
Let $P, Q \in \mathbb{R}[x]$ be relatively prime nonconstant polynomials. Show that there can be at most three real numbers $\lambda$ such that $P + \lambda Q$ is the square of a polynomial.

Alison Miller
26 replies
zacchro
Dec 11, 2016
Mathandski
41 minutes ago
Mmo 9-10 graders P5
Bet667   8
N 43 minutes ago by User141208
Let $a,b,c,d$ be real numbers less than 2.Then prove that $\frac{a^3}{b^2+4}+\frac{b^3}{c^2+4}+\frac{c^3}{d^2+4}+\frac{d^3}{a^2+4}\le4$
8 replies
Bet667
Apr 3, 2025
User141208
43 minutes ago
Tangent to two circles
Mamadi   1
N 43 minutes ago by ricarlos
Source: Own
Two circles \( w_1 \) and \( w_2 \) intersect each other at \( M \) and \( N \). The common tangent to two circles nearer to \( M \) touch \( w_1 \) and \( w_2 \) at \( A \) and \( B \) respectively. Let \( C \) and \( D \) be the reflection of \( A \) and \( B \) respectively with respect to \( M \). The circumcircle of the triangle \( DCM \) intersect circles \( w_1 \) and \( w_2 \) respectively at points \( E \) and \( F \) (both distinct from \( M \)). Show that the line \( EF \) is the second tangent to \( w_1 \) and \( w_2 \).
1 reply
Mamadi
Today at 7:01 AM
ricarlos
43 minutes ago
China Northern MO 2009 p4 CNMO
parkjungmin   2
N an hour ago by WallyWalrus
Source: China Northern MO 2009 p4 CNMO
China Northern MO 2009 p4 CNMO

The problem is too difficult.
Is there anyone who can help me?
2 replies
parkjungmin
Apr 30, 2025
WallyWalrus
an hour ago
Problem 4
codyj   86
N an hour ago by Mathgloggers
Source: IMO 2015 #4
Triangle $ABC$ has circumcircle $\Omega$ and circumcenter $O$. A circle $\Gamma$ with center $A$ intersects the segment $BC$ at points $D$ and $E$, such that $B$, $D$, $E$, and $C$ are all different and lie on line $BC$ in this order. Let $F$ and $G$ be the points of intersection of $\Gamma$ and $\Omega$, such that $A$, $F$, $B$, $C$, and $G$ lie on $\Omega$ in this order. Let $K$ be the second point of intersection of the circumcircle of triangle $BDF$ and the segment $AB$. Let $L$ be the second point of intersection of the circumcircle of triangle $CGE$ and the segment $CA$.

Suppose that the lines $FK$ and $GL$ are different and intersect at the point $X$. Prove that $X$ lies on the line $AO$.

Proposed by Greece
86 replies
codyj
Jul 11, 2015
Mathgloggers
an hour ago
Israeli Mathematical Olympiad 1995
YanYau   24
N an hour ago by bjump
Source: Israeli Mathematical Olympiad 1995
Let $PQ$ be the diameter of semicircle $H$. Circle $O$ is internally tangent to $H$ and tangent to $PQ$ at $C$. Let $A$ be a point on $H$ and $B$ a point on $PQ$ such that $AB\perp PQ$ and is tangent to $O$. Prove that $AC$ bisects $\angle PAB$
24 replies
YanYau
Apr 8, 2016
bjump
an hour ago
P(x), integer, integer roots, P(0) =-1,P(3) = 128
parmenides51   3
N an hour ago by Rohit-2006
Source: Nordic Mathematical Contest 1989 #1
Find a polynomial $P$ of lowest possible degree such that
(a) $P$ has integer coefficients,
(b) all roots of $P$ are integers,
(c) $P(0) = -1$,
(d) $P(3) = 128$.
3 replies
parmenides51
Oct 5, 2017
Rohit-2006
an hour ago
2017 CGMO P1
smy2012   9
N an hour ago by Bardia7003
Source: 2017 CGMO P1
(1) Find all positive integer $n$ such that for any odd integer $a$, we have $4\mid a^n-1$
(2) Find all positive integer $n$ such that for any odd integer $a$, we have $2^{2017}\mid a^n-1$
9 replies
smy2012
Aug 13, 2017
Bardia7003
an hour ago
Euler's function
luutrongphuc   1
N 2 hours ago by luutrongphuc
Find all real numbers \(\alpha\) such that for every positive real \(c\), there exists an integer \(n>1\) satisfying
\[
\frac{\varphi(n!)}{n^\alpha\,(n-1)!} \;>\; c.
\]
1 reply
luutrongphuc
2 hours ago
luutrongphuc
2 hours ago
Square problem
Jackson0423   1
N 2 hours ago by maromex
Construct a square such that the distances from an interior point to the vertices (in clockwise order) are
1,2,3,4, respectively.
1 reply
Jackson0423
2 hours ago
maromex
2 hours ago
Sequence with infinite primes which we see again and again and again
Assassino9931   4
N 2 hours ago by SimplisticFormulas
Source: Balkan MO Shortlist 2024 N6
Let $c$ be a positive integer. Prove that there are infinitely many primes, each of which divides at least one term of the sequence $a_1 = c$, $a_{n+1} = a_n^3 + c$.
4 replies
Assassino9931
Apr 27, 2025
SimplisticFormulas
2 hours ago
Unique NT Function
IndoMathXdZ   33
N Apr 10, 2025 by N3bula
Source: IMO SL 2018 N6
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.
33 replies
IndoMathXdZ
Jul 17, 2019
N3bula
Apr 10, 2025
Unique NT Function
G H J
G H BBookmark kLocked kLocked NReply
Source: IMO SL 2018 N6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IndoMathXdZ
691 posts
#1 • 3 Y
Y by megarnie, Kingsbane2139, Adventure10
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
plagueis
157 posts
#2 • 6 Y
Y by Aryan-23, IMUKAT, megarnie, Adventure10, MS_Kekas, khina
Proposed by Ariel García, Mexico
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tastymath75025
3223 posts
#3 • 10 Y
Y by cjquines0, smurfcc, mijail, Mop2018, MiraclesINmaths, Zyz1010, hakN, Adventure10, bhan2025, pokpokben
Great problem :) We’ll split into two cases.
Case 1: $f$ is unbounded. In that case, let $n_1<n_2<...$ be an infinite sequence of integers such that $f(n_i) > f(n_i-1), f(n_i-2), \dots, f(1)$ for each $i$.

For any positive integer $k$ take large $i$ so that $f(n_i-k) \mid f(n_i-k-1) + f(1)$. Note that $f(n_i)\mid  f(n_i-k) + f(k) < 2f(n_i)\implies f(n_i-k)=f(n_i)-f(k)$ and similarly $f(n_i-k-1) = f(n_i) - f(k+1)$. Therefore we have that $f(n_i) - f(k) \mid f(n_i)-f(k+1) + f(1)$, hence $f(n_i)-f(k) \mid f(1)+f(k)-f(k+1)$. As $i$ increases $f(n_i)-f(k)$ gets arbitrarily large, implying $f(k+1)=f(k)+f(1)$ for all $k$, so $f(n)=nf(1)$ and $f(1)>1$ divides each $f(n)$, and we’re done.

Case 2: $f$ is bounded by some $M$. For any $p$ and $n>m$, note that $p\mid f(n),f(m)$ implies $p\mid f(n-m)$ because $f(n)\mid f(m)+f(n-m)$. Consider primes $p$ that divide infinitely many $f(n)$ and let $S$ be the set of all such primes. Let $u$ be the smallest positive integer with $p\mid f(u)$; it follows that for any $n$ with $p\mid f(n)$, we have $p\mid f(n-u), f(n-2u), \dots, f(n \pmod u)$, which contradicts the minimality of $u$ unless $u\mid n$. Notice this allows us to associate each prime $p$ with an “order” $u_p=u$ such that $p\mid f(n)\implies u_p\mid n$. Suppose for contradiction that $u_p\neq 1$ for each $p\in S$.

Now clearly $S$ is finite, and if $m_k= k\text{lcm}_{p\in S} u_p + 1$, then $u_p\nmid m_k$ for each $p\in S$ and each $k$, so no $p\in S$ can divide $f(m_k)$. But the sequence $f(m_1), f(m_2), \dots$ is bounded and infinite, so it takes some value greater than one infinitely many times, meaning there is a prime $q$ which divides infinitely many of the $f(m_i)$. But this would imply $q\in S$, contradiction. Therefore it follows that some $p\in S$ has $u_p=1$. But now by definition there are arbitrarily large $n$ with $p\mid f(n)$, and $p\mid f(n), f(1)\implies p\mid f(n-1)$, so this implies $p\mid f(n)$ for all $n$, 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.
Kayak
1298 posts
#4 • 3 Y
Y by AlastorMoody, aops29, Adventure10
This was Indian TST D2 P3. Here's my solution to this at TST:

Case-1 $\text{Im}(f)$ is bounded.
Proof: Call a prime $p$ to be Soumil if there's infinitely many integers $i$ such that $p|f(i)$. For a soumil prime $p$, define it's lavil to be the set $T_p : \overset{\text{def}}{=} \{ i \in \mathbb{N} : p | f(i) \}$. Note that if $a, b \in T_p$ then $|a-b| \in T_p$, thus (say by Euclidean algorithm), there's an integer $g_p \in \mathbb{N}$ such that $T_p = g_p \mathbb{N}$.

Let $S$ be the set of all soumil primes. Now I claim atleast one of $g_p$ where $p \in S$ will be equal to $1$ (which would imply the proof). Assume not. Then define $S : \overset{\text{def}}{=} \prod_{p \in S} g_p$, and consider the set $Q = \{ Sm+1 \}_{m \in \mathbb{N}}$ where $m$ varies over integer. Note that by definition of soumil primes, the union of all lavil sets contains all but finitely many integers. But the elements of $Q$ don't belong to any lavil set, which is a contradiction so done. $\square$
Case-2 $\text{Im}(f)$ is unbounded.

In this case I prove $f(m) = f(1)m$.

Lemma: (Growth of $f$) We say the interval $[i, j]$ is soumil $f(n+1)-f(n) = f(1)$ for each $n \in [i, j]$. For each positive integer $m$, there're infinitely many soumil intervals of the form $[mk, m(k+1)-1]$.

Proof

So pick any integer $j$, and an integer $M > \max(f(1), f(2), \cdots, f(j))+100$, and a soumil interval $[n, 2^M+n]$. Then $f(n+M+j) = f(n)+(M+j)f(1) > M + jf(1) > \max(jf(1), f(j))$, and thus \begin{align*}
f(n+M+j) & | f(n+M) + f(j) = f(n) + Mf(1)+f(j) \\
& | f(n+M+j-1) + f(1) = f(n) + (M+j)f(1) = f(n) + Mf(1) + jf(1)
\end{align*}so subtracting them gives $f(n+M+j) | f(j) - jf(1)$ which gives the conclusion $\square$.
This post has been edited 4 times. Last edited by Kayak, Jul 17, 2019, 9:22 PM
Reason: typoes
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
323 posts
#5 • 32 Y
Y by Wizard_32, Kayak, 62861, danepale, Pathological, djmathman, Nothing000, Ti-Ci, p_square, AlastorMoody, aops29, rashah76, RAMUGAUSS, amar_04, Aryan-23, khina, SnowPanda, Supercali, starchan, tigerzhang, L567, megarnie, OlympusHero, MiraclesINmaths, CyclicISLscelesTrapezoid, ZHEKSHEN, IMUKAT, Mz_T, Kingsbane2139, sabkx, Adventure10, Deadline
This was proposed by me :)

I hope you all enjoyed it/will enjoy it!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#6 • 11 Y
Y by v4913, Kobayashi, SerdarBozdag, Anshul_singh, HamstPan38825, ZHEKSHEN, sabkx, Nuterrow, Adventure10, Assassino9931, khina
The following solution splices together ideas from both of the official solutions.

Claim: Let $d_n = \gcd(f(n), f(1))$. Then $d_{n+1} \mid d_n$ for all $n$.
Proof. Immediate from $f(n+1) \mid f(n) + f(1)$. $\blacksquare$

Hence, we will assume henceforth that $d_n = \gcd(f(n), f(1)) = 1$ for all $n \ge C$, for some constant $C$ (otherwise $\min_n d_n$ is the required constant).

Claim: If $\gcd(a,b) = 1$, then $\gcd(f(a), f(b)) \mid f(1)$. In particular, $\gcd(f(a), f(b)) = 1$ if $\min(a,b) \ge C$.
Proof. This follows by Euclidean algorithm: if $a > b$ then $f(a) \mid f(a-b) + f(b)$, so $\gcd( f(a), f(b) ) \mid \gcd( f(a-b), f(b) )$. $\blacksquare$

The second claim already implies $f$ is unbounded: if $f$ takes only values in $\{2, \dots, L\}$ then taking any $L+1$ primes larger than $C$ gives a contradiction.

Main induction: Assume $f$ is unbounded. Let $X$ be a local maximum, meaning $Y = f(X) \ge \max \left\{ f(1), \dots, f(X-1) \right\}$. We will assume $X$ and $Y$ are large enough such that $X > C + C f(1)$, $Y > 2 f(1) f(C)$. Then: \begin{align*} 	Y = f(X) \mid f(X-C) + f(C) &\implies f(X-C) = Y - f(C) \\ 	Y-f(C) = f(X-C) \mid f(X-2C) + f(C) &\implies f(X-2C) = Y - 2f(C) \\ 	Y-2f(C) = f(X-2C) \mid f(X-3C) + f(C) &\implies f(X-3C) = Y - 3f(C) \\ 	&\vdotswithin{\implies} \\ 	&\implies f(X-f(1)C) = Y - f(1) f(C). \end{align*}However, all the right-hand sides are supposed to not be divisible by $f(1)$, yet we assumed $\gcd(f(C), f(1)) = 1$, contradiction.
This post has been edited 1 time. Last edited by v_Enhance, Nov 25, 2022, 4:13 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MarkBcc168
1595 posts
#7 • 11 Y
Y by hyx, rashah76, Mathasocean, Aryan-23, Kanep, Kobayashi, Adventure10, Kingsbane2139, Mango247, sabkx, Deadline
Here is a short solution by Gems98.

First, we make the following observation.

Claim: If $d\mid f(m)$ and $d\mid f(n)$ then $d\mid f(m-n)$.

Proof: Obvious from the problem's condition.

We will consider two cases.
Case 1: $f$ is bounded.

Let $p_{1}$ be a prime number. By Dirichlet's theorem, there exists a sequence of prime numbers $p_{2}, p_{3}, \cdots, $ such that
$$p_{n+1} \equiv 1 \pmod{\prod_{i=1}^{n}p_{i}}$$By pigeonhole principle, there exists a increasing sequence $a_{1}, a_{2} ,\cdots$ such that
$$c = f(p_{a_{1}}) = f(p_{a_{2}}) = \cdots$$From $p_{a_{i+1}} \equiv 1 \pmod{p_{a_{i}}}$, we get $c \mid f(1)$ by applying the Claim repeatedly. Therefore, if $c \mid f(n)$ then $c \mid f(n-1)$.

Since the sequence $p_{a_{i}}$ is unbounded, we get $c \mid f(n)$ for every $n \in \mathbb{Z}^+$ which is the desired result.

Case 2: $f$ is unbounded.

We call the natural number $n$ $\textit{good}$ iff $f(n) > \max\{f(1), \cdots, f(n-1)\}$. Since $f$ is unbounded, there exist infinitely many $\textit{good}$ number.

It's easy to show that if $m$ is $\textit{good}$, then $f(m) = f(i) + f(m-i)$ for all $i \leq m-1$. Let $n$ be a positive integer and $m$ be a sufficiently large $\textit{good}$ number. From the condition, we get
\begin{align*}
    f(m-n+1) &\mid f(m-n)+f(1) \\
    f(m) - f(n-1) &\mid f(m) - f(n) + f(1) \\ 
    f(m) - f(n) &\mid f(n) - f(n-1) - f(1)
\end{align*}Since $m$ is sufficiently large, we get $f(n) - f(n-1) - f(1) = 0$ which implies that $f$ is linear.
Therefore, there exists positive integer $c = f(1) > 1$ such that $c\mid f(n)$ for all $n \in \mathbb{Z}^+$.
This post has been edited 1 time. Last edited by MarkBcc168, Jul 17, 2019, 2:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mofumofu
179 posts
#8 • 7 Y
Y by test20, danepale, AlastorMoody, Kingsbane2139, Adventure10, Mango247, sabkx
While this problem is a really nice one, I would like to point out some similar (and difficult) problems that have appeared before, namely 2007 N5, IMO 2011, Iran 3rd round 2017, and with a different condition Romania TST 2016.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
323 posts
#9 • 3 Y
Y by starchan, Adventure10, Mango247
Yeah, there are some other pretty cool NT functional problems around. I definitely got reminded of some of those when I came up with this problem :)

I learned of the existence of the Romania TST problem because I heard this one was discarded from the shortlist due to it, which was a shame :( . Had I known that problem existed beforehand I may have not sent my problem to be considered for IMO.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yayups
1614 posts
#10 • 3 Y
Y by Adventure10, Mango247, sabkx
We split into cases based on whether $f$ is bounded or not.

First, assume $f$ is unbounded. This means that there is an infinite sequence of \textit{peaks} $1=x_0<x_1<x_2<\cdots$ such that $f(x_n)>f(x)$ for all $x<x_n$. Note that $f(x_n)\mid f(x)+f(x_n-x)$ and $f(x)+f(x_n-x)<2f(x_n)$, so in fact $f(x_n)=f(x)+f(x_n-x)$. For any given $x$, we have for large enough $n$ that $f(x_n-x)\mid f(1)+f(x_n-x-1)$, so
\[f(x_n)-f(x)\mid f(1)+f(x_n)-f(x+1),\]so $f(x_n)-f(x)\mid f(1)+f(x)-f(x+1)$ for arbitrarily large $n$. We see that $f(x_n)$ can be arbitrarily large, so we must have $f(x+1)=f(x)+f(1)$, so $f(x)=xf(1)$. Thus, $f(1)\mid f(n)$ for all $n$.

Now suppose $f$ is bounded. Note that $f(n+1)\mid f(n)+f(1)$, so $\gcd(f(n+1),f(1))\mid\gcd(f(n),f(1))$. Thus,
\[\cdots\mid\gcd(f(3),f(1))\mid\gcd(f(2),f(1))\mid\gcd(f(1),f(1)),\]so either $\gcd(f(n),f(1))=1$ for large enough $n$, or $\gcd(f(n),f(1))>1$ for all $n$, in which case we're done. So WLOG, suppose that $\gcd(f(n),f(1))$ for all $n\ge N$.

We claim that $\gcd(f(x),f(xy+1))=1$ for $x\ge N$. To see this, note that
\[f(xy+1)\mid f(x)+f(x(y-1)+1)\implies\gcd(f(xy+1),f(x))\mid\gcd(f(x(y-1)+1),f(x)).\]Iterating this gives $\gcd(f(xy+1),f(x))\mid\gcd(f(1),f(x))=1$, as desired. Thus, any two terms in
\[f(N),f(N+1),f(N(N+1)+1),f(N(N+1)(N(N+1)+1)+1),\ldots\]are relatively prime, so in particular, any two terms are distinct. But this is an infinite sequence of $f(x)$ for distinct values of $x$, so $f$ is unbounded, which is the desired contradiction.
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
#11 • 5 Y
Y by amar_04, jishu2003, a_n, Mango247, ihatemath123
This is the first shortlist #6 that I solve(This is also the few ones that I have attempted), and spend a lot of time (10+ hours), so I decided to post it on the thread.
Let $a_n=f(2^n)$ for all $n\geq 0$. We distinguish two cases:
$\underline{Case I:}$For all $n\geq 0$, $a_n$ has an odd prime factor
note that by taking $m=n=2^k$ we have
$$a_k|2a_{k-1}$$Hence any prime factors of $a_n$ must also be a prime factor of $a_i$ where $i$ is any positive integer less than $i$. Since $a_1$ has only finitely many prime factors, there exists a prime p such that $p|a_n$ for all positive integers $n$. We that $p|f(n)$ for all $n\in\mathbb N$.
Indeed, we proceed by backward induction to show that every integer in the interval $[2^k,2^{k+1}]$ has this property, indeed we have $p|f(2^{k+1})$. Now note that if $p|f(n)$ then since $p|f(1)$ together with
$$f(n)|f(n-1)+f(1)$$we have $p|f(n-1)$ and therefore we complete the inductive step and therefore we're done.
$\underline{Case II:}$There exists $k\in\mathbb N$ such that for all $N\geq k$ we have the fact that $a_n$ is a power of $2$.(We assume that $k$ is the minimal choice)
Using similar arguments as in case I we have that for every number $m$ there exists a number $k$ such that for all $N\geq k$ we have $f(m\cdot 2^k)$ is a power of 2.
Note that if $p|f(m)$ and $p|f(n)$, then we have $p|f(n-m)$ therefore $p|f(gcd(m,n))$ by Euclidean algorithm. That is
$$gcd(f(m),f(n))|f(gcd(m,n))(1)$$Let $q$ be the minimal number such that $a_q$ is even. We claim that if $v_2(n)<q$ then $f(n)$ is odd. Otherwise, suppose $v_2(n)=s$, by $(1)$ we have $$2|gcd(f(n),f(2^k))|f(gcd(f(n),f(2^k))=f(2^s)$$this contradicts the minimality of $q$
We further distinguish two cases
$\underline{Case IIa:}$$q\geq1$
We prove the following
$\underline{CLAIM 1.}$The sequence $\{a_n\}$ is unbounded
$\underline{Proof.}$Suppose $\{a_n\}<M$ for all $n$, then since
$$f(2^n+1)|f(2^n)+f(1)$$We have $f(2^n+1)\leq f(2^n)+f(1)\leq M+f(1)$ hence $f(2^n+1)$ is also bounded, therefore by pigeonhole principle there exists an infinite sequence of numbers $\{b_n\}$ such that
$$f(2^{2^{b_i}}+1)=f(2^{2^{b_j}}+1)$$for all $i,j\in\mathbb N$.Let this number be $c$, then since $(2^{2^{b_i}}+1,2^{2^{b_j}}+1)=1$, from $(1)$ we have
$c|f(1)$, using the same induction method as in Case I we have $c|f(n)$ for all positive integer $n$, contradiction.
$\underline{CLAIM 2.}$ Let $a$ be an integer, denote $v_2(n)$ by $m$, then
$$v_2(f(a))=v_2(f(2^m))$$$\underline{Proof.}$Suppose $a=2^mp$, and $v_2(f(a))=x$, $v_2(f(2^m))=y$
If $x>y$, then we prove by induction that $v_2(f(an+2^m))\leq y$ for all positive integers $n$
Indeed the base cases are trivial, suppose the case n holds, then
$$v_2(f(a(n+1)+2^m))\leq v_2(f(an+2^m)+f(n))\leq y$$so we're done. In particular, let $d$ be the order of $2$ mod $p$, pick n such that $np+1=2^wd$ for all integer $w$, we obtain that $v_2(a_{wd+m})=y$, and since $v_2(a_i)+1\geq v_2(a_{i+1})$ we must have $v_2(a_n)\leq y$ that is, $a_n$ is bounded, which violates CLAIM 1.
If $y>x$, then we prove by induction that $v_2(f(a+n2^m))\leq x$ for all positive integers $n$
Indeed the base cases are trivial, suppose the case n holds, then
$$v_2(f(a+(n+1)2^m))\leq v_2(f(a+n2^m)+f(2^m))\leq x$$so we're done. pick n such that $n+p+1=2^w$ for all integer $w$, we obtain that $v_2(a_{w})=x$, that is, $a_n$ is bounded, which violates CLAIM 1.
Combining the two cases, we proves the claim.
$\underline{CLAIM 3.}$If $a\geq k$, then
$$v_2(f(2^{a+1})=v_2(f(2^a))+1$$$\underline{Proof.}$
Otherwise, since $v_2(f(2^{a+1})\leq v_2(f(2^a))+1$ either
(i)$v_2(f(2^{a+1})<v_2(f(2^a))$ or
(ii)$v_2(f(2^{a+1})=v_2(f(2^a))$
If $(i)$ holds,
$$v_2(f(2^a))>v_2(f(2^{a+1})=v_2(f(2^{a+1})+f(2^a))\geq v_2(f(2^{a+1}+2^a))$$This violates CLAIM 2 since $v_2(2^{a+1}+2^a)=v_2(2^a)$
If $(ii)$ holds, then we let $f(2^a)=2^m$. We prove by induction that
$$f(n2^a)=2^m$$for all integer $n$ not divisible by $4$. Indeed from $(ii)$ we have $f(2\cdot 2^a)=2^m$
Now suppose all smaller cases holds, we have
$$f(n2^a)| f((n-1)2^a)+f(2^a)=2^{m+1}$$From CLAIM 2 we have $v_2f(n2^k)=m$ and therefore $f(n2^k)=2^m$, this completes the inductive step. Now we have, for all integers $b$,
$$f(2^{b+m})|f(2^m)+f((2^b-1)2^m)=2^{a+1}$$that is $a_n$ is bounded, this violates CLAIM 1, so we prove CLAIM 3.
$\underline{CLAIM 4.}$
For all integer $n$ we have
$$f(n2^k)=n2^m$$$\underline{Proof.}$
We proceed by induction. In the following we denote $f(2^k)=2^m$. Note that $CLAIM 3$ implies that for all integer $b$ we have $f(2^{b+k})=2^{m+b}$
The base cases are trivial. Now suppose all smaller cases hold we consider the case $n$,suppose $2^{t-1}\leq n\leq 2^t$, we have
$$f(n2^k)|f((n-1)2^k)+f(2^k)$$$$f(2^t\cdot 2^m)|f(n2^k)+f(2^t-n)2^k)$$applying the inductive hypothesis we have
$$n2^m\leq f(n2^k)\leq n2^m$$This completes the inductive step and we hence have proof CLAIM 4.
$\underline{CLAIM 5.}$
$$f(2^{k-1})=2^{m-1}$$$\underline{Proof.}$
Now we have
$$f(n2^k+2^{k-1})|f(n2^k)+f(2^{k-1})$$$$f((n+1)2^k)|f(n2^k+2^{k-1})+f(2^{k-1})$$for all integer $n$. Let the terms on the left and right side of the first divisibility be $A$ and $B$, and the terms on the left and right side of the second divisibility be $C$ and $D$.
Note that $A\leq B$ and $C\leq D$. If $A=B$ and $C=D$, we add them up and apply $CLAIM 4$ to get
$$f(2^{k-1})=2^{m-1}$$which is what we want to prove.
Otherwise, either one of $2A\leq B$ or $2C\leq D$ must hold.
If the former holds we have
$$2^m+f(n2^k+2^{k-1})\leq f(2^{k-1})$$since $f(n2^k+2^{k-1})\geq \frac{1}{2}n2^{m+1}+2^m$
we have $f(2^{k-1})\geq (n+1)2^{m+1}$ which can't hold for large $n$.
If the latter holds we have
$$(n+1)2^m\leq 2f(2^{k-1})$$which also can't hold for large $n$. So CLAIM 5 is proved.
However, we define $k$ to be the minimal integer such that $f(2^k)$ is a power of $2$, so we obtain a contradiction, which rejects the case $q\geq 1$
$\underline{Case IIb.}$$q=0$
Now we have $f(1)$ is even, using the same reasoning as in Case I, we have that for all $n$, $f(n)$ is even, so we're done.
Hence we reject all case and the proof is thus completed.
This post has been edited 2 times. Last edited by mathaddiction, May 5, 2020, 3:07 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
niksic
81 posts
#12
Y by
Hopefully this isn't equivalent to any previous solutions :D Nowhere near as pretty as the first one tho :(

Notice that if $p|f(1)$ and $p|f(n)$, then $p|f(m)$ for all $m\leq n$. So for the sake of contradiction, assume that $(f(1),f(n))=1$ for all $n>N$, where $N$ is some integer.

Claim 1: $f(n)\leq n+C$ where $C$ is a constant

Also notice that $f(2n)|2f(n)$, so by induction we have $f(2^k)|2^kf(1)$, so $f(2^k)|2^k$ for $2^k>N$. Because $f(n+m)|f(n)+f(m)$, we also have $f(n+m)\leq f(n)+f(m)$. We will also use these two inequalities: $f(2^k)\leq 2^k$ for $k\geq \log_2(N)$ and $f(2^k)\leq 2^kf(1)$ for the smaller ones. Writing any $n$ as a sum of powers of two and using the inequality as many times as needed, we get $f(n)\leq n+(1+2+4+...+2^{\log_2(N)})f(1)\leq n+C$ where $C$ is constant.

Claim 2: Let $a_p$ be the smallest value $n$ for which $p|f(n)$. Then we have $p|f(n)\implies a_p|n$
Assume the contrary and let $k$ be the smallest value for which $p|f(k)$ and $a_p\nmid k$. Then $k>a_p$ and we have $f(k)|f(k-a_p)+f(a_p)\implies p|f(k-a_p)$, a contradiction.

We now split into two cases:

Case 1 $f(n)\leq \frac{1}{2}(f(n-1)+f(1))$ for infinitely many values of $n$
Take some big $n$ and $\varepsilon>0$ such that $n+2C\leq n(1+\varepsilon)$. Notice that by our assumption we can make $\varepsilon$ arbitrarily small

Take a big integer $m$ and write it as follows: $f(m)=f(an+b)\leq af(n)+f(b)\leq a\frac{1}{2}(f(n-1)+f(1))+f(b)\leq a\frac{1}{2}(n-1+C+1+C)+b+C$
$\leq \frac{1}{2}an(1+\varepsilon)+b\frac{1}{2}(1+\varepsilon)+n+C\leq (an+b)\frac{1}{2}(1+\varepsilon)+C+n = m\frac{1}{2}(1+\varepsilon)+n+C<\frac{3}{4}m$ for $m$ large enough, say for $m\geq N_0$. Take $M=max(N,N_0)$
(These inequalities are far from pretty but they work :D and obviously $3/4$ is arbitrary)

Now look at primes that are larger then $M$ .Say the number of primes that divide $f(1)f(2)\cdots f(k)$ for some $k$ is $g(k)$. By claim 2, you can notice that all primes larger than $M$ are $a_p$ for some $p$, which means $g(k)\geq \pi(k)-\pi(M)$. Say the largest prime dividing $f(1)f(2)\cdots f(M)$ is $P$. Notice that for $k>\frac{4}{3}P$, $\pi(\frac{3}{4}k)\geq g(k)\geq \pi{k}-\pi{M} \iff \pi(k)-\pi(\frac{3}{4}k)\leq \pi(M)$, the right-hand side is fixed, and from here there are many ways to prove that this is a contradiction.
(I won't be writing any of them because I can't think of an elementary way :( )

Case 2 $f(n)=f(n-1)+f(1)$ for $n\geq L$, where $L$ is some integer

This means $f(m)=f(L)+f(1)(m-L) = mf(1)+(f(L)-Lf(1))$ for $m\geq L$. Remember we had the property of $f(2)$ to be a power of $2$. It is trivial to see that this forces $f(L)-Lf(1)=0$ and $f(1)$ is a power of $2$, meaning $2$ divides all $f(m)$ with $m\geq L$, contradiction
This post has been edited 3 times. Last edited by niksic, Aug 13, 2020, 7:00 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aryan-23
558 posts
#13
Y by
Nice problem !

We distinguish cases based on the boundedness of $f$.

Case 1 : $\operatorname {Im}f$ is bounded.

For all primes $p$, define the set $S_p= \{n : p\mid f(n)\}$. Call a prime $p$ strong , if $S_p$ is infinite and weak otherwise. Its easy to see that $p\vert f(a) , f(b) \implies p\mid f(a-b)$, hence $S_p=x_p \cdot \mathbb Z^{+}$ , for some $x_p$. Suppose that for all strong primes $p$, $x_p\neq 1$. Then note that since $f(n)$ is divisible by only finitely many weak primes, hence this means that the set $ \mathbb Z^+ \setminus { \bigcup_{p 
   \quad         \text{strong}} S_p } $ is finite. Consider, $X= \prod_{p  \quad \text{strong}} x_p$ and look at $X\mathbb Z^++1$. Obviously its infinite and has $f(\bullet)$ not divisible by any strong prime, contradiction. $\blacksquare$. Hence $x_p=1$ for some strong prime $p$, and the conclusion is immediate.

Case 2 : $f$ is unbounded.

The idea is to worry only about the size of $f$ and force "Cauchyness" on some intervals.

We show $f(x)=xf(1)$ for all $x\in \mathbb Z^+$

Call a $x$ to be a peak if $f(x) > \operatorname {max} \{f(1),f(2) ,\dots f(x-1)\}$. Obviously there are infinitely many such peaks due to unboundedness. Its easy to see that due to size issues, $f(x)=f(x-k)+f(k)$ holds for all $x>k$.

We show $f(n+1)-f(n)=f(1)$ for all $n$.
Pick a arbitrary $x$ and $y$ such that $x+y$ is a peak and $f(x+y)$ is huge. Spamming the equality $f(x+y)=f(x)+f(y)=f(x-1)+f(y+1)$, we get :

$$ f(y+1) \vert f(y)+f(1) $$$$\implies f(x+y)-f(x-1) \mid f(x+y)-f(x)+f(1)$$$$\implies f(x+y)-f(x-1) \mid f(x)-f(x-1)-f(1)$$
Taking $f(x+y)$ to be huge we're done. $\blacksquare$
This post has been edited 1 time. Last edited by Aryan-23, Oct 22, 2020, 5:52 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shalomrav
330 posts
#14
Y by
For the bounded case, just take a prime $p$ for which all the values of $f(n)$ appeared before $p$. So there is some $n$ smaller than $p$ such that $f(p)=f(n)=c$ and by euclidean algorithm $c$ divides $f(1)$, and by more application of euclidean algorithm (induct down, begin with $p,1$) we get $c$ divides every guy in $f(p-1), f(p-2), f(p-3) ... $ and so. we are done since by assumption every value of $f$ is included in this sequence.
This post has been edited 6 times. Last edited by shalomrav, Feb 12, 2021, 3:54 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SnowPanda
186 posts
#15
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.
jj_ca888
2726 posts
#16 • 1 Y
Y by Mango247
Let $P(m, n)$ denote the assertion. First of all, $P(1, n)$ yields\[f(n+1) \mid f(n) + f(1) \implies \gcd(f(n+1), f(1)) \mid \gcd(f(n), f(1))\]always. Now, we only need to consider when there exists $M$ for which $\gcd(f(n), f(1)) = 1$ for all $n \geq M$ since\[\gcd(f(n), f(1)) \mid f(n) \mid \gcd(f(n-1), f(1))\]so the sequence $\gcd(f(i), f(1))_{i = 1}^{\infty}$ is in fact nonincreasing, and if it never hits $1$, then the lower bound $L$ of the sequence divides all $\gcd(f(i), f(1))$, and thus divides all $f(i)$, at which point we would be done.

Next, we will prove that in the case where $f(n), f(1)$ are relatively prime for all sufficiently large $n \geq M$, then $f$ is unbounded. First, note that $P(n, m-n)$ yields $f(n) \mid f(m-n) + f(m)$ hence $\gcd(f(n), f(m)) \mid \gcd(f(m-n), f(n))$ which is analogous to the Euclidean Algorithm, and performing this continuously yields $\gcd(f(n), f(m)) \mid f(\gcd(m, n))$. Thus, for pairs $(m, n)$ that are relatively prime, and $m, n \geq M$, it follows that $\gcd(f(m), f(n)) \mid f(1)$ but since\[\gcd(f(m), f(1)) = \gcd(f(n), f(1)) = 1\]we know $\gcd(f(m), f(n)) = 1$. It easily follows that $f$ is then unbounded; if it were upper bounded by $U$, then just pick some $N > U$ numbers $a_1, \ldots , a_N \geq M$ for which their $f$ values are all pairwise relatively prime; no two $f(a_i)$ could be the same, hence the range of $f$ needs to hit at least $N > U$ numbers, thus $U$ could not have been the upper bound, a contradiction.

Lastly, we finish by considering the case where $f$ is unbounded. Consider numbers $k$ for which $f(k) > f(1), \ldots , f(k-1)$. There are clearly infinitely many of these $k$, else $f$ is upper bounded by the largest $f(k)$. Pick arbitrarily large $K$ for which $f(K)$ is large, and greater than all $f(i)$ for $i < K$. Then for any positive $x + y = K$, note $f(x) + f(y) < 2f(K)$ but still must be a whole multiple of $K$, hence $f(x) + f(y) = K$. Note that since $f(x + 1) \mid f(x) + f(1)$,\[f(K) - f(y-1) \mid f(K) - f(y) + f(1) \implies f(K) - f(y-1) \mid f(y-1) - f(y) + f(1)\]where clearly $|f(y-1) - f(y) + f(1)| < |f(K) - f(y-1)|$ from picking $K$ such that $f(K)$ is much larger than every one of $f(y), f(y-1), f(1)$. Finally, this implies that $f(y) = f(y-1) + f(1)$ for all integers $y$, hence $f$ is linear and then induction easily shows that $f(y) = yf(1)$, so indeed $f(1) \mid f(y)$ for all $y$, finishing this case as well.

After exhausting all cases, we have shown $f(1)$ does indeed always divide all $f(n)$.
This post has been edited 11 times. Last edited by jj_ca888, Jun 29, 2021, 9:10 PM
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
#17
Y by
Cool problem! :D. I did the bounded case first and then died on the unbounded case for a longg time proving useless stuff like $f(n) > n$ before I realised simple stuff does work :P

Note that every value of $f$ has some prime dividing it since $f(n) > 1$. Let $p$ be an arbitrary prime dividing some value of $f$. Let $S_p$ denote the set of numbers $n$ such that $p | f(n)$. Note that $a,b \in S_p \implies |a-b| \in S_p$ as well, by the problem statement. Let $a_1 < a_2 < a_3, \cdots$ be the elements of $S_p$. Now, we must have $a_{k+1} - a_k = a_1$. This is because if $a_{k+1} - a_k = z < a_1$, then $z < a_1 \in S_p$, not possible. If $a_{k+1} - a_k = z > a_1$, then $a_{k+1} - a_1 \in S_p$ and is between $a_{k}$ and $a_{k+1}$, not possible. So, we have that $S_p$ is just multiples of $a_1$.

Let $q$ be a prime dividing $f(1)$. If the problem is false, then $S_q$ is finite, say with maximal element $M$. Pick a prime $r > M$. Note that $f(r)$ cannot contain any prime divisor that divides $f(n)$ for $n < r$ since then we would need $n | r$, not possible since $n \neq 1$ and $r$ is prime. Since this is true for infinitely many $r$, we have that there are infinitely many primes dividing some value of $f$. In particular, $f$ is unbounded.

I will in fact show that if $f$ is unbounded, then it is linear. Call a number $n$ a peak if $f(n) > f(k)$ for all $1 \le k \le n-1$. So $f(n) | f(k) + f(n-k)$ but since $f(n)$ is greater than both of them, we must have $f(n) = f(k) + f(n-k)$ for all $k < n$. Since $f$ is unbounded, there are infinitely many peaks. Let $m$ be one such peak.

Observe that $f(m) - f(k) = f(m-k) | f(m-k-1) + f(1) = f(m) - f(k+1) + f(1) \implies f(m) - f(k) | f(k) + f(1) - f(k+1)$. Since we can make $m$ sufficiently large, we must have that the RHS is $0$, so $f(k+1) = f(k) + f(1)$ which gives $f(n) = nf(1)$ and so $c = f(1)$ itself divides all values of $f$. Therefore, 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.
rama1728
800 posts
#18
Y by
IndoMathXdZ wrote:
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.

Solved with MathLuis :showoff:

Let \(P(m,n)\) denote the assertion of the given functional equation. We split the problem into two cases.

Case 1. \(\text{Im}(f)\) is bounded.
From the divisibility condition \[f(n+1)\mid f(n)+f(1)\]we have that \[\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=\gcd(f(n),f(1))\]Also, by Pigeon Hole, there exists a prime \(p\) such that \(p\mid f(n)\) for infinitely many \(n\), let the set of such \(n\) be denoted as \(\mathbb{S}_p\) and let \(k\) be their greatest common divisor. By the Euclidean algorithm, we can show that \(\mathbb{S}_p\) contains all the multiples of \(k\). Now, we choose a subset \(\mathcal{S}\) of \(\mathbb{S}_q\) (for some prime \(q\)) so that \(\mathcal{S}\) contains the least element of \(\mathbb{S}_q\) and all the images of the elements are equal. Let the least element be \(n_0\), then note that \(\gcd(f(n_0),f(1))=\gcd(f(m),f(1))\) for all \(m\geq n_0\), because of the divisibility condition we got earlier. Now, if we choose the prime \(q\) so that it divides \(f(1)\), then we get that \(q\) divides \(f(i)\) and \(f(i+1)\) for some \(i\). And since the only \(k\) that divides \(i\) and \(i+1\) is \(1\), \(q\) divides \(f(i)\) for all natural numbers \(i\) as desired.

Case 2. \(\text{Im}(f)\) is unbounded.
Call a positive integer \(n\) gawaskar, if \(f(n)>f(i)\) for all \(i<n\). Note that there are infinitely many gawaskar numbers and \(f(n)=f(i)+f(n-i)\) for all \(i<n\). Now, let \(x+y\) be a gawaskar number such that \(f(x+y+1)\) is huge. Then, by the problem's condition, \[f(x+y+1)\mid f(x+y)+f(1)=f(x)+f(y)+f(1)\]and \[f(x+y+1)\mid f(x)+f(y+1)\]implying that \[f(x+y+1)\mid f(y+1)-f(y)-f(1)\]Implying that \(f(y+1)=f(y)+1\). Since there are infinitely many gawaskar numbers, we have that \(f(x+1)-f(x)=f(1)\) for all \(x\in\mathbb{N}\). This implies that \(f(x)=xf(1)\), and since \(1\neq f(1)\mid f(x)=xf(1)\), we are done.

Remarks
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AwesomeYRY
579 posts
#19
Y by
Solved with help from Max Lu

If $p$ divides $f(1)$, then first there's $n_p$ values of f divisible by p, then everything afterwards isn't divisible by p. Thus, there exists some $N$ s.t. for all $n\geq N$ you have $\gcd(f(1),f(n))=1$.

If $p\nmid f(1)$, then let the first time that $q$ appears in $f(i)$ be $s_q$. Then, $p\mid f(n) \Longrightarrow s_q\mid n$. Combining these two results, for $p\geq N$, $f(p)$ is relatively prime to all previous numbers.

Thus, if $f$ is bounded, you find a contradiction because you can't keep generating relatively prime numbers (finite number of prime divisors).

Otherwise, if $f$ is bounded then we claim that $f$ is linear (and therefore of the form $f(n) = n\cdot f(1)$. There must be arbitrarily long chains of $f(n+1) = f(n)+f(1)$, otherwise if all chains were of length $\leq C$, then the value would go up by $Cf(1)$ and then get halved, which cannot become unbounded. Thus, there exists a chain with arbitrarily large $k$ of the form $[b-k,b]$. Next, $f(b)\mid f(b-k) + f(k) = f(b) - kf(1) + f(k) \leq f(b)$ so $f(k) = kf(1)$ and 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.
Inconsistent
1455 posts
#20 • 1 Y
Y by Nuterrow
Assume otherwise.

Notice that $f(m+n) \leq f(m)+f(n)$ so we can induct to $f(a_1+a_2+\ldots+a_n) \leq f(a_1)+f(a_2)+\ldots+f(a_n)$.

We say a prime $p$ is alive if for any positive integer $N$, there exists $x \geq N$ such that $p \mid f(x)$. We say a prime is dead otherwise.

Notice that for every $p \mid f(1)$ we have $p \nmid f(k)$ for some $k$, so $p$ is dead by induction because $p \nmid f(i) \Longrightarrow p \nmid f(i+1)$ since $f(i+1) \mid f(1)+f(i)$.

We say a dead prime $p$ dies on a day $N$ if for any $x \geq N$ we have $p \nmid f(x)$ and such $N$ is minimal. By definition, every prime has a death day.

Note that $f(2n) \mid 2f(n)$ so for an odd prime $p$ if $p \nmid f(n)$ then $p \nmid f(2n)$. Therefore no new primes appear in the sequence $f(1), f(2), f(4), \ldots, f(2^i), \ldots$ and eventually after all primes that divide $f(1)$ die, $f(2^n)$ is a power of $2$ for all $n \geq C$ for some $C$, and none of them are equal to $1$. This implies $2$ is alive, so $2 \nmid f(1)$. Therefore since $v_2(f(2^{i+1}) \leq 1+v_2(f(2^{i}))$ we know $v_2(f(2^i)) \leq i$. A corollary is that $f(2^i) \leq 2^i$ for all $i \geq C$.

Assume at some integer $T$ we have $v_2(f(2^T)) < T$ then by induction $v_2(f(2^i))<i$ for all integers $i \geq T$. So for all $i \geq \max(T, C)$ we have $f(2^i) \leq \frac{2^i}{2}$

Let $S = \sum_{i = 0}^{\max(T, C)} \left(f(2^i)-2^i\right)$, which is a finite positive integer.

Then for all $i \geq \max(T, C)$ we have $f(i) \leq \sum_{2^s \text{ in binary representation of i}} f(2^s) \leq \frac{i}{2}+S$

Let $R$ be the day when all primes that divide $f(1)$ die.

Lemma: If $p \mid f(q)$ where $p, q$ are primes and $q \geq N$ for some constant $N$ then $p \nmid f(i)$ for all $i < q$.

Proof: Choose $N = R$. Then assume $p \mid f(i)$ for some $i < q$, so pick the minimal such $i$ which must be greater than $1$. Clearly $i \nmid q$ so let $s$ be $q$ reduced modulo $i$. Then $p \nmid f(s)$, and by induction on $p \nmid f(k) \Longrightarrow p \nmid f(k+i)$ using $f(k+i) \mid f(i)+f(k)$, we prove $p \nmid f(q)$ which is a contradiction, so we are done.

Therefore the set of primes between $R$ and $x$ for arbitrary $x$ has an injective mapping to the set of primes at most $\frac{x}{2}+S$. So $\pi\left(x\right) \leq \pi\left(\frac{x}{2}\right)+(R+S)$ for constant $R+S$. This is clearly false by the Prime Number Theorem, giving contradiction.

Therefore $T$ doesn't exist, so $v_2(f(2^i)) = i$ for all $i$, implying $f(2^i) = 2^i$ for all $i \geq C$.

Now let $M = \sum_{i = 0}^C \left(f(2^i)-2^i\right)$. Clearly by summing over the binary representation again, $f(i) \leq i+m$ for all $i$. By taking the smallest power of 2 greater than $i$, $2^k$, we know that $2^k \leq f(i)+f(2^k-i)$ so $f(i) \geq i-M$ since $f(2^k-i) \leq 2^k-i+M$.

For $i, j > 2M$ we must have $f(i+j) \mid f(i)+f(j)$ but if $f(i+j) \neq f(i)+f(j)$ then $i+j-M \leq f(i+j) \leq \frac{f(i)+f(j)}{2} \leq \frac{i+j}{2}+M$, which is a contradiction. So $f(i+j) = f(i)+f(j)$. So letting $j = ki$ and inducting on positive integers $k$ gives us that $f(ki) = kf(i)$ for $i > 2M$. However this means if $p$ is any prime that divides $f(1)$, then $p \mid f(pi) = pf(i)$ for arbitrarily large $i$. This means $p$ is alive, so by contradiction 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.
bora_olmez
277 posts
#21
Y by
I didn't like this as much as most others.
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NoctNight
108 posts
#22 • 2 Y
Y by PRMOisTheHardestExam, Mango247
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5001 posts
#23
Y by
Really long solution, but this problem feels like you just keep throwing stuff at it and keep track of what you've proved and you eventually grind it down.

As with everyone else, split into cases where $f$ is bounded and unbounded.

In general, note that if $n \mid f(a),f(b)$ for $a>b$, then $n \mid f(a) \mid f(b)+f(a-b) \implies n \mid f(a-b)$. Call an integer $i$ with $n \mid f(i)$ $n$-cool. I claim that if there exist $n$-cool integers, then they are all consecutive multiples of some positive integer $k$, and $k$ is one of them (i.e. they are $\{k, 2k, \ldots\}$ or $\{k, 2k, \ldots, ak\}$ for some $a \geq 1$). I claim that setting $k$ equal to the least $n$-cool integer works, which is by induction. Suppose that the $c$ smallest $n$-cool integers are $\{k,\ldots,ck\}$, and the $c+1$-th smallest $n$-cool integer exists. Then if $x$ is this $c+1$-th smallest $n$-cool integer, $x-k$ must be $n$-cool as well, and also must be in $S$ as it's smaller than $x$, hence $x-k=ck \implies x=(c+1)k$, completing the induction.

Suppose $f$ is bounded, so there exists some maximal $M$ such that there are infinitely many $n$ with $f(n)=M$, and call such $n$ fat. The key idea is that for any fat $n$, we have $f(a)+f(b) \in \{M,2M\}$ for all $a+b=n$ with $a,b$ sufficiently large (so $f(a),f(b) \leq M$), where we only achieve $2M$ if $a$ and $b$ are fat as well.
First, we use the above idea but loosened a bit: let $m$ be the least integer such that $M \mid f(m)$ (which exists, since it's at most the smallest fat number). Then if $n$ is fat and $n-m$ is large, $M \mid f(n-m) \implies f(n-m)=M$. On the other hand, if some $n>k>n-m$ exists such that $f(k)=M$, then $M=f(n) \mid f(k)+f(n-k) \implies M \mid f(n-k)$: impossible by definition, as $n-k<m$. This is enough to imply that the gap between large enough consecutive fat numbers is constant (and equal to $m$).
Now, pick positive integers $a,b$, such that $a,b,b-a$ are large enough, and $b$ is fat, so $b+m$ is fat as well. Then $f(b-a)=f(b+m-a)=M-f(a)$. By fixing $a$ and letting $b$ vary, this means that $f$ is eventually periodic (with minimal period $m$).
Pick $x$ large and let $1<k=f(mx+1)$, which is constant for large enough $x$. Then by our "general fact", $k$ divides $mx+1,mx+m+1$, which implies that it divides $\gcd(mx+1,mx+m+1)=\gcd(mx+1,m)=1$. Then because there are infinitely many $k$-cool integers, and $1$ is one of them, every positive integer is $k$-cool, completing the proof. $\blacksquare$

Now to tackle the case where $f$ is unbounded. Let $M$ be the minimum value attained by $f$, and call an $n$ such that $f(n)=M$ skinny. Further, let $n$ be powerful if $f(n)\geq f(n-1),f(n-2),\ldots,f(1)$, and overpowered if the inequality is strict, so there are infinitely many overpowered (and thus powerful) $n$. It's easy to see that for all overpowered $n$, we have $f(a)+f(b)=f(n)$ for all $a+b=n$, and if $n$ is powerful (but not overpowered) this equality holds so long as both $a$ and $b$ aren't powerful either, and if one is, then both are.
Pick some large overpowered $n$ with $f(n)=x$ and $x>9999M$. Then we have $f(m)=x-M \iff f(n-m)=M$ for $m<n$. On the other hand, by our general claim, the set of $a$ such that $x-M \mid f(a)$ is equal to consecutive multiples of some positive integer $k$, including $k$in particular, the least $m$ with $f(m)=x-M$ is $k$ (important!). On the other hand, if $a<n$, then $2(x-M)\geq x$, so any such $a$ must have $f(a)=x-M$. Hence for $m<n$, $f(m)=x-M \iff m=ck$ where $c$ ranges from $1$ to some arbitrary positive integer (possibly $1$ as well). This means that the skinny integers less than $n$ are evenly spaced out with a gap of $k$ as well. But since $k$ must equal the least $m$ satisfying $f(m)=x-M$ (which is overpowered), we can repeat this argument with a different (larger) choice of overpowered $n$, giving us a different value of $k$, unless $c \leq 1$ always (in which case the gap isn't defined). This means that there is exactly one skinny number $K$, which in turn readily implies that if $n>K$ is overpowered, then $n-K$ is overpowered as well, and they are consecutive (i.e. there is no overpowered number between them). Thus there exists some $1 \leq r \leq K$ such that the overpowered integers which are at least $r$ are precisely those of the form $Kx+r$ for $r \geq 0$. Note that if $f(r)=C$, then $f(Kx+r)=Mx+C$.
For any $y$, pick some $x$ such that $Kx+r>y$, so $f(y)+f(Kx+r-y)=f(Kx+r)=Mx+C$. We then also have
$$f(y+K)+f(Kx+r-y)=f(K(x+1)+r)=M(x+1)+C,$$so $f(y+K)=f(y)+M$ for all $y$.
We are now ready to finish. Pick some $x,y$ and consider the equation $x+(y+cK)=(x+y+cK)$ for all $c \geq 0$. Then,
$$f(x+y+cK) \mid f(x)+f(y+cK) \implies f(x+y)+cM \mid f(x)+f(y)+cM \implies f(x+y)+cM \mid f(x)+f(y)-f(x+y).$$Since $f(x+y)+cM$ is unbounded, $f(x)+f(y)=f(x+y)$, hence $f$ satisfies Cauchy and is linear. This clearly implies that $f(1)>1$ divides all values of $f$, so we're done. $\blacksquare$
This post has been edited 3 times. Last edited by IAmTheHazard, Jan 25, 2023, 10:31 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
302 posts
#24
Y by
Assume $f$ is unbounded. We have a sequence $m_1<m_2< \cdots$ where $f(m_i)>f(n)$ for all positive integers $n<m_i$. First, by size stuff, we see that $f(m_i) = f(m_i-k)+f(k)$ for every positive integer $k<m_i$. Likewise $f(m_i) = f(m_i-k-1)+f(k+1)$. So, $f(m_i)-f(k)$ divides $f(m_i)-f(k+1)+f(1)$. Thus, $f(m_i)-f(k)$ divides $f(k)-f(k+1)+f(1)$. But $f(m_i)-f(k)$ gets arbitrarily large. So, $f(k)-f(k+1)+f(1)=0$. Thus, $f(n)=n \cdot f(1)$

Assume $f$ is bounded. First, we claim that there exist positive integers $a$, $b$, and $p$ where $\gcd(a,b)=1$ and $p$ divides $f(a)$ and $f(b)$. This follows from the fact that $\text{Im}(f)$ is bounded. If there are $k$ primes dividing elements in $\text{Im}(f)$ then just consider a set of $k+1$ pairwise relatively prime positive integers, by PHP we get what we want. Now, let $A=\{a_1<a_2< \cdots \}$ be the set of positive integers where $f(a_i)$ is divisible by $p$. We claim $a_k = c \cdot k$ for some positive integer $c$. Indeed, if $m>n$ are positive integers then $f(a_m)$ divides $f(a_m-a_n)+f(a_n)$. Since $p$ divides $f(a_m)$ and $f(a_n)$, it must follow that $p$ divides $f(a_m-a_n)$. So, $a_m-a_n \in A$. Now, we will proceed by induction. Suppose $a_i = c \cdot i$ for every positive integer $i<k$, we will show $a_k = c \cdot k$. Assume $a_k < c \cdot k$. Then, $a_{k}-a_{k-1}<k = a_1$. But this contradicts minimality since $a_k-a_{k-1} \in A$. Now, assume $a_k > c \cdot k$. Then $a_k>a_k-a_1>a_{k-1}$. But because $a_k-a_1\in A$, this implies there is an element in $A$ between two consecutive elements. Contradiction.

So, we have positive integers $\gcd(a,b)=1$ where $p$ divides $f(a)$ and $f(b)$. But, this implies that $a = k \cdot A$ and $b = k \cdot B$ for some $A$ and $B$. So, $k=1$. Implying that $p$ divides $f(n)$ for all positive integers $n$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Anzoteh
126 posts
#25
Y by
Lol I ended up turning this into an analysis problem smh (also thanks to some theorem a few have pointed out).

Sketch
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VicKmath7
1389 posts
#26 • 1 Y
Y by Maths_Girl
Solution
This post has been edited 1 time. Last edited by VicKmath7, May 15, 2023, 2:26 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leo.Euler
577 posts
#27
Y by
Assume for contradiction that there exists large $N$ such that for $n \ge N$, $\gcd(f(1), f(n))=1$.

Claim: $f$ is unbounded.
Proof. First, we note that $\gcd(f(1), f(n+1)) \mid \gcd(f(1), f(n))$ for all $n$, and inductively we have \[ \gcd(f(1), f(a)) \mid \gcd(f(1), f(b)) \]whenever $a > b$. Furthermore, for such $a, b$, it follows by the Euclidean algorithm that \[\gcd(f(a), f(b)) \mid \gcd(f(a-b), f(b)), \]and we can accordingly condense this to \[ \gcd(f(a), f(b)) \mid \gcd(f(1), f(n)) \mid f(1) \]for some $n$. By our assumption, when both $a$ and $b$ are larger than $N$, $\gcd(f(a), f(b)) \mid 1$, which forces $\gcd(f(a), f(b))=1$, implying that $f$ is unbounded. :yoda:

We assume the claim henceforth. Say that a positive integer $n$ is Skywalker if and only if $f(n) \ge f(k)$ for each $k < n$; clearly there is an infinitude of such numbers. By definition $f(n)=f(k)+f(n-k)$ for all $k<n$ whenever $n$ is Skywalker. Let $n$ be an arbitrarily large Skywalker, and $m<n$ be arbitrary. Fixing $m$ and variating $n$, the original functional equation implies \[ f(n-m+1) \mid f(n-m)+f(1), \]which we easily reduce to \[ f(n) - f(m) \mid f(m)-f(m-1)-f(1), \]so by size reasons we have $f(m)-f(m-1)-f(1)=0$, which rewrites as $f(m)=f(m-1)+f(1)$. Inductively we have $f(i)=if(1)$ for all $i \ge 1$, but this is a contradiction to our initial assumption that $\gcd(f(1), f(n))=1$ for sufficiently large $n$. We conclude. :starwars:

Remark: This proof consists of three main components, namely
  • showing that $f$ is unbounded by following the Euclidean algorithm,
  • defining Skywalker numbers using the unboundedness of $f$ and observing their infinitude, and
  • solving the functional equation by fixing some $m<n$ (where $n$ is a large Skywalker) and variating $n$.
In fact, the final two steps are motivated by the solution to 2019 N4, in which the functional divisibility is taken to advantage by fixing the dividend and varying the divisor enough to conclude that the dividend is 0.
This post has been edited 1 time. Last edited by Leo.Euler, Aug 14, 2023, 7:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
huashiliao2020
1292 posts
#28
Y by
I was suggested to solve this by Leo.Euler;
here's a long and inefficient solution, where I just threw things at the wall until it stuck:

Suppose FTSOC that there exists a number $L$ (we take the smallest) that does not share the common gcd of the numbers smaller than it; let the earlier common gcd be g. Let $d_n=\gcd(f(n),f(1))$. Note that $$d_{n+1}=\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=d_n\stackrel{\text{induction}}{\rightarrow}d_i\mid d_j\forall i>j\implies\forall l\ge L,d_l\mid d_L,$$and by assumption $\gcd(d_L,g)=1\implies\gcd(d_l,g)=1$. We also extract $$\forall a\equiv1\pmod b,a,b\ge L,\gcd(f(a),f(b))\mid\gcd(f(a-b)+f(b),f(b))=\gcd(f(a-b),f(b))=...=\gcd(f(1),f(k))\mid f(1)$$by iterating. By assumption, this is one (otherwise $1<\gcd(f(a),f(b),f(1))\mid\gcd(f(a),f(1))$); in particular, f is unbounded.

Since f is unbounded, there are an infinite number of times when a new largest value appears in the sequence (namely $f(n)>f(k)\forall k<n$); namely $f(n)>\max(f(k),f(n-k))>\frac{f(k)+f(n-k)}2\implies f(n)=f(k)+f(n-k)$ for infinite n. Fix $m$ and vary n with this property; we have $$f(n)-f(m)=f(n-m)\mid f(n-m-1)+f(1)=f(n)-f(m+1)+f(1)\leftrightarrow f(n)-f(m)\mid f(m)-f(m+1)+f(1),$$which for sufficiently large f(n) s.t. LHS>RHS, we must have RHS=0; in particular, $f(m+1)=f(m)+f(1)\implies f(m)=mf(1)$, contradiction since f(1)>1 and f(1) is a common gcd, so our inital FTSOC was wrong.
This post has been edited 8 times. Last edited by huashiliao2020, Sep 5, 2023, 3:53 AM
Reason: better latex
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_comb01
662 posts
#29
Y by
Fun problem!
Sketch:
Case 1: IM(f) is unbounded
The idea is to look at a "peak" and do some sort of downward induction to get $f(x)=xf(1)$.
Case 2:Im(f) is bounded
Here, the idea is to take the set of primes dividing $f$ infinitely many times, then prove one of them divides all by contradiction argument.
This post has been edited 3 times. Last edited by math_comb01, Mar 30, 2024, 11:17 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Iveela
116 posts
#30
Y by
We begin by solving the case where $d = f(1)$ is the minimum value attained by $f$. In particular, we prove that $d$ divides all values of $f$. Assume the contrary. Then, obviously $f$ is nonconstant. Notice that $d \mid f(x)$ implies $d \mid f(x-1)$ since $d \mid f(x) \mid f(x-1)+f(1) = f(x-1) + d$. Consequently $d$ doesn't divide $f(k)$ for all sufficiently large values of $k$.
Now suppose $x \in \mathbb{N}$ satisfies $f(x) \leq f(x+1)$. Then, the condition implies that $f(x+1) \mid f(x) + f(1) \leq 2f(x+1)$. Since equality holds only if $d=f(x)=f(x+1)$, this tells us that either $f(x+1)=f(x) + d$ or $f(x+1)=d$. Consider the smallest positive integer $k$ such that $f(k) \neq kd$. Suppose that a positive integer $x$ satisfies $d \neq f(x) \leq f(x+1) \leq \dots \leq f(x+k)$. Then, the condition implies that $f(x) + kd = f(x+k) \mid f(x) + f(k) \implies f(x + k) \mid f(k) - kd$ and hence $f(x+k) \leq |f(k)-kd|$ which is a constant number.
On the other hand, suppose that $x \in \mathbb{N}$ satisfies $f(x) > f(x+1)$. Then, we have $f(x+1) \mid f(x) + d \implies f(x+1) \leq \frac{f(x)+d}{2}$. It is clear that these observations are enough to conclude that $f$ is bounded. (Actually, this implies that if $f$ is unbounded we must have $f(x)=dx$.)
Let $\alpha$ be the largest value that appears infinitely many times in $f$. Let $\alpha_1, \alpha_2, \dots$ be the numbers mapped to $\alpha$ by $f$. Consider two sufficiently large positive integers $i > j$ such that $i-j$ is also very large. Then, we have $f(\alpha_j) \geq f(\alpha_j-1)$ and hence $f(\alpha_j-1) = \alpha - d$. The condition implies that $f(\alpha_i) \mid f(\alpha_j-1) + f(\alpha_i-\alpha_j+1)$. Since $i-j$ is very large, we have $f(\alpha_i-\alpha_j+1) \leq \alpha \implies f(\alpha_j - 1) + f(\alpha_i - \alpha_j +1 ) < 2 \alpha$. Hence, $f(\alpha_j-1) + f(\alpha_i-\alpha_j+1) = \alpha \implies f(\alpha_i-\alpha_j+1) = d$, a contradiction. (We actually dont use the fact that $f(1)$ is the minimum here.) $\square$

Now we solve the general case. Let $c$ be the smallest positive integer such that $f(c) \leq f(k)$ for all $k \in \mathbb{N}$. Consider the function $g : \mathbb{N} \to \mathbb{N}$ such that $g(x) = f(cx)$. Observe that $g(m+n) \mid g(m) + g(n)$ for all $m, n \in \mathbb{N}$ and $g(1) \leq g(k)$ for all $k \in \mathbb{N}$. It follows that $g(1) \mid g(k) \Leftrightarrow f(c) \mid f(ck)$ for all positive integers $k$.
Case 1: The sequence $f(c), f(2c), \dots$ is bounded.
It suffices to show that $f$ is bounded. Assume the contrary. Then there exists a positive integer $s$ such that the sequence $f(s), f(c+s), f(2c+s), \dots$ is unbounded. Let $f(ck+s)$ be a sufficiently large term of this sequence. Our condition implies that $f(ck+s) \mid f(ck) + f(s)$ which is bounded by a constant number, a contradiction. $\square$.
Case 2: The sequence $f(c), f(2c), \dots$ is unbounded.
Note that $f(ck)=kf(c)$. We claim that $f(x+c) = f(x) + f(c)$. Using the same logic as Case 1, we see that the sequences $f(s), f(c+s), f(2c+s), \dots$ are unbounded for all positive integers $s$. Consider positive integers $k$ such that $f(ck+s) > f(ck_0+s)$ for all $k > k_0$. Suppose that $f(ck) > f(ck+s)$. Consider the largest positive integer $\alpha \leq k$ such that $f(c\alpha) \leq f(ck+s)$. It is clear that $f(ck+s) - f(c\alpha) < f(c)$ The condition implies that $f(ck+s) \mid f(c\alpha) + f(c(k-\alpha)+s)<2f(ck+s)$. Hence, $f(c(k- \alpha)+s) < f(c)$ a contradiction. Then, $f(ck+s) \mid f(c\alpha) + f(c(k-\alpha)+s) < 2f(ck+s)$ implies that $f(c(k-\alpha)+s) + \alpha f(c) = f(ck+s)$.
Now we prove that $f(x+y)=f(x)+f(y)$. Let $x=\alpha c+ x_0$ and $y=\beta c + y_0$. Then, $f(x+y)=(\alpha+\beta)c+f(x_0+y_0) \mid f(x) + f(y) = c(\alpha+\beta) + f(x_0) + f(y_0)$ and hence $c(\alpha+\beta)c + f(x_0 + y_0) \mid f(x_0) + f(y_0) - f(x_0+y_0)$ for all positive integers $\alpha$ and $\beta$. This implies $f(x_0) + f(y_0) = f(x_0+y_0) \implies f(x) + f(y) = f(x+y)$. Hence, $f(x) \equiv kx, \ k \in \mathbb{N}$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
idkk
118 posts
#31
Y by
Claim: if $c|f(a),c|f(b)$ then $c|f(gcd(a,b))$

Proof: Its easy to see $c|f(a),c|f(b) \implies c|f(|b-a|)$ use euclidian division algorithim to prove the claim .


Case 1: $f$ is bounded above or in other words $f$ attains finite values.


Let $f(M)=t$ be the largest value in its range which repeats infinitely often. say $a$ is the smallest natural number such that $f(a)=t$ .
we know then that $f(x)=t \implies a|x$


Claim: $f(x)=t \iff a|x$ for large $x$

assuming $n$ is large we have $f(n)|f(a)+f(n-a)$ if $f(n)=t$ we know $f(n-a)=t$ using this the claim is easy to see .


Claim: For large $x$ , $f(x)=t$ or $\frac{t}{2}$

Consider the sequence $t=f(ax_1)=f(a(x_1+1))=......$ where $x_1$ is large covering all large solutions for $f(x)=t$


Now for any large $m$ not divisible by $a$ pick some large $n$ such that $m+n=ax_1$


Now its easy to see $I=f(m)=f(m+a)=f(m+2a)=........$ we know then $|$ divides $t$.

Pick any other large $m_1$ such that $a|m+m_1$ and choose some large $n_1$ such that $a|m_1+n_1$ to similarly get $a|f(m_1)$ and repeat similarly
from here observe we are writing $t$ as a sum of its divisors only way to do is $\frac{t}{2}+\frac{t}{2}$


Now once we have the main problem proved for large $x$ , smaller $x$'s automatically follow pretty easily .


Case 2: $f$ is unbounded .






Its easy to observe

$f(2^d)|2f(2^{d-1})|4f(2^{d-2})......|2^df(1)$

now i define the function $f_2(x)=$ largest odd factor of any natural no $x$ , observe $f_2(2^{d+1})|f_2(2^{d})$

Case 1: $f_2(f(2^d)) > 1$ always .


Prove that the common odd factor divides any number of form $f(K 2^t)$ where $K$ is a odd no. By induction.

Case 2: The sequence $f(1),f(2),f(4),.....$ eventually turns into powers of 2 .


Say $f(2^d)$ is the smallest power of $2$ in the sequence .

Claim: All multiples of $f(2^d)$ come in the sequence $f(2^d),f(2^{d+1}),f(2^d*3),f^(2^{d+2}),.....$

appolozie my laziness prove alll terms basically are multiples of $f(2^d)$ and do $f^(2^d+2^dt)|f(2^d)+f(2^dt)$ , its easy prove that the sequence wont be bounded . which will give u this claim .


Now observe $f^(2^dx+r)|f(2^dx)+f(1)$ where $f(1)$ is odd

Now as $f(1)$ has to be odd[can be proved with more that if it wasent the case all terms would be even]. , we know there exist ifninitely many $x$ such that $f(2^dx)+f(1)$ is a power of $f(1)$ , by which the result isnt hard to see[ too lazy to add the details :P]
This post has been edited 5 times. Last edited by idkk, May 28, 2024, 9:20 AM
Reason: .
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Akacool
14 posts
#32 • 1 Y
Y by Titibuuu
Lets prove that $f$ is bounded. If we assume that $f$ is unbounded we can say that there are infinite amount of $N$ that $f(N)$ is the prefix max. So it becomes that for any $x < N$
$f(x) + f(N - x) = f(N)$. Now if we take large N and some x to be $f(N - x) | f(N - x - 1) + f(1)$ and it becomes that $f(N) - f(x) | f(N) - f(x + 1) + f(1)$ which in turn means that
$f(x + 1) = f(x) + f(1)$ so $f(x) = xf(1)$.
Now that $f$ is bounded we can assume that there is a set of values of $f$ lets call $A$ that they appear infinitely many times in $f$. It is clear that the $\gcd(f(n), f(1))$ divides all $f$ less than $n$.
If we use euclidean alg on $f$ we can easily see that the $\gcd(f(x), f(y) | f(\gcd(x, y))$. So it means that every occurrence of a element of $S$ is divisible by some "primitive occurrence".
And if that occurrence is $1$ we will get that that element of $S$ is divisible by $f(1)$ in turn all of $f$ will be divisible. So every "primitive" occurrence divides every occurrence of elements of $S$. Every $f(x)$ if $x$ is large will be an element of $S$ which means that every $x$ will be divisible by some "primitive" occurrence but we can take an $X$ that isn't divisible by any so thus a contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8857 posts
#33
Y by
woah this is like the most perfect number theory FE ever made

We split into two cases.

Case 1: $f$ is bounded, say by $N$. Then there exists a nonempty set of positive integers $S$ such that for any $k \in S$, $k \mid f(n)$ for infinitely many values of $n$. Otherwise, every $k$ only divides $a_k$ values of $n$, and we can only define $f$ for less than $a_1+a_2+\cdots+a_N$ values of $n$.

For each $n \in S$, let $m_n$ be minimal such that $n \mid f(m_n)$, and let $a_1$ be the minimum among the $m_n$. Furthermore, let $a_2, a_3, \dots$ be the values with this $n \mid f(a_i)$ in increasing order.

Claim: For any $q \in \mathbb N$, $n \mid f(qa_1)$.

Proof: Observe we have
\begin{align*}
f(a_i) \mid f(a_i - a_1) + f(a_1) &\implies n \mid f(a_i - a_1) \\
f(a_i - a_1) \mid f(a_i - 2a_1) + f(a_1) &\implies n \mid f(a_i- 2a_1) \\
&\vdots
\end{align*}so we inductively have $n \mid f(a_i \bmod a_1)$. If $a_1 \nmid a_i$, this is less than $a_1$, hence we must have $a_1 \mid a_i$.

By definition, the sequence $\{a_i\}$ has infinitely many terms, so for any $q$, we can find a $a_\ell > qa_1$, and the above process implies $n \mid f(qa_i)$, as needed. $\blacksquare$

Claim: $a_1 = 1$.

Proof: Otherwise, any divisor $d$ of $f(1)$ divides only finitely many $f(n)$. In particular, for sufficiently large primes $p$, $f(p) \mid f(1) p$ implies $f(p) = p$. But this contradicts $f$ bounded. $\blacksquare$

These two claims solve the bounded case.

Case 2: $f$ is unbounded. Then by definition, there exists a sequence $n_1, n_2, n_3, \dots$ such that $f(n_i) > f(k)$ for all $k < n_i$. For these $n_i$, we must have $f(n_i) = f(k) + f(n_i-k)$ as $2f(n_i) > f(k) + f(n_i-k)$ for all $k$. In particular, we have the following claim:

Claim: $f(k+1)-f(k) = c$ for some constant $c$.

Proof. We will show that $f(k) - f(k-1) = f(k+1) - f(k)$ for each $k$. Take some $n_i > k$; by the previous property, \[f(k) + f(n_i-k) = f(n_i) = f(k+1) + f(n_i-k-1) \implies f(k+1) - f(k) = f(n_i-k) - f(n_i-k-1).\]Let $a_{k-1} = f(k) - f(k-1)$ and $a_k = f(k+1) - f(k)$. We have
\[f(n_i-1) \mid \gcd(f(k-1) + f(n_1 - k), f(k) + f(n_1-k-1)) = \gcd(f(k-1)+f(n_1-k), a_{k-1}-a_k).\]In particular, $f(n_i - 1) \mid a_{k-1} - a_k$. But $\{f(n_i)\}$ is unbounded, hence $\{f(n_i - 1)\} = \{f(n_i) - f(1)\}$ is unbounded, so $a_{k-1} = a_k$, as needed. $\blacksquare$

Therefore $f$ is linear in $n$. Let $f(1) = b$ and $f(2) = a+b$; if $a$ and $b$ are relatively prime, then $a+b \mid 2b$, which is a clear contradiction as $\gcd(a+b, 2b) = \gcd(a+b, 2)$. Hence $a$ and $b$ share a common factor $d$, and this $d$ divides $f(n)$ for every $n$.
This post has been edited 1 time. Last edited by HamstPan38825, Aug 21, 2024, 9:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
N3bula
269 posts
#34
Y by
Claim: If $f(n)\geq \alpha n$ for some fixed $\alpha$ we get the result.

Proof:
Let $\alpha$ be the largest value such that for all $n$ we have that $f(n)\geq \alpha n$. Clearly from the definition we can find values such that for any $\epsilon$ we get that $\frac{f(n)}{\alpha n} \leq 1+\epsilon$, now take a value of $r$ such that $\frac{f(r)}{\alpha r} < 2$. I claim that we have for that value of $r$ that $f(nr)=nf(r)$. Suppose that $f((n-1)r)=(n-1)f(r)$, we must have that $f(nr)\mid nf(r)$ if $f(nr)\neq nf(r)$ we have that $f(nr)\leq \frac{nf(r)}{2}$, thus $\frac{f(nr)}{\alpha nr} \leq \frac{f(r)}{2\alpha r} < 1$ however this is a contradiction. Thus for all $n$ we have that $f(nr)=nf(r)$. Now suppose that for some $p\mid f(1)$ that $p\nmid f(k)$. Clearly we have that $p \nmid f(k+1)$ and thus for all $m\geq k$ we get $p\nmid f(m)$. Thus we must have unless the result holds true that $f(r)$ is coprime to $f(1)$. Now let $p$ be a prime such that $p\mid f(1)$. Clearly there exists infinetly many $k$ such that $f(n) \mid p^k-1$. Thus we can choose abitrarily large $n$ such that $f(nr)=p^k-1$. Now consider $f(f(1)nr+f(1)) \mid f(1)f(nr)+f(1)$ as $f(nr)=p^k-1$, we get that $f(f(1)nr+f(1)) \mid f(1)p^k$ as we can make $n$ abitrarily large, as $f(n)\geq \alpha n$ we can get that $p \mid f(f(1)nr+f(1))$ for all sufficiently large $n$ this suffices as this means that $p\mid f(n)$ for all $n$.

Now suppose no such lower bound exists.
I will prove that such a $c$ still exists. Clearly we must have that if $gcd(a, b)=1$ that $gcd(f(a), f(b))=1$. Thus if we let the first $n$ primes be $p_1$, $p_2$, $\dots$, $p_n$. We know that for all $n$ we have $f(n)\leq f(1)n$. Now let $k$ be a value such that $\frac{f(k)}{k}< \frac{1}{10^{1000}}$. We get that above some point from that we must have for all $m>N$ that $\frac{f(m)}{m}<\frac{1}{10^{1000}}$. Let the largest prime divisor amongst $f(p_1)$, $f(p_2)$, $\dots$, $f(p_n)$, such that $p_n\leq N < p_{n+1}$ be $q$. Suppose $q$ is the $i$th prime, now let $u$ be a value such that $u \geq n, i$. Take the first $u$ primes. Clearly a prime divisor of size at least $p_u$ divides one of $f(p_{n+1}), f(p_{n+2}), \dots, f(p_u)$ which contradicts the size condition thus implying the result.
This post has been edited 2 times. Last edited by N3bula, Apr 10, 2025, 10:35 AM
Z K Y
N Quick Reply
G
H
=
a