Find all increasing sequences $a_1,a_2,a_3,...$ of natural numbers such that for each $i,j\in \mathbb N$, number of the divisors of $i+j$ and $a_i+a_j$ is equal. (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.)
Problem
Source: Iran second round 2011
Tags: induction, number theory proposed, number theory
quantumbyte
28.04.2011 18:39
I know that the answer is $a_n=n$ but I am having trouble to prove this statement.
jgnr
28.04.2011 18:47
is it strictly increasing or just non-decreasing?
goodar2006
28.04.2011 18:57
goodar2006 wrote: (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.) I think you get your answer from this.
mahanmath
28.04.2011 19:06
First It`s easy to show the sequence is strictly increasing . Then use the fact that $d(n)$ is odd only for perfect squares $n$ . (There is an easier way to finish the problem , but it worths to thinking about it yourself )
goodar2006
28.04.2011 20:54
after proving that the sequence is strictly increasing, looking at $a_{2^{p-2}}$ where $p$ is a prime number can also solve the problem.
mahanmath
28.04.2011 20:57
goodar2006 wrote: after proving that the sequence is strictly increasing, looking at $a_{2^{p-2}}$ where $p$ is a prime number can also solve the problem. This is exactly what I wrote in my post , an easier way !
Amir Hossein
30.04.2011 21:22
Try to solve the generalization of this problem.
goodar2006
04.05.2011 19:44
as an intresting result; mahanmath proved that the problem statement is still true if we omit the increasing condition! you can think on it!
Amir Hossein
04.05.2011 20:58
Can someone finish the proof of this problem with induction? I solved this using induction but I don't remember how did I finish it...
mahanmath
04.05.2011 21:10
amparvardi wrote: Can someone finish the proof of this problem with induction? I solved this using induction but I don't remember how did I finish it... Could you write the start of your solution , (because my solution has an inductive progressing ,so It may help us to recovery (!!) your solution .)
Amir Hossein
04.05.2011 21:17
The only thing I remember is that I proved that $a_1=1, a_2=2,a_3=3$, which is not hard (just find the numbers for which $d(n)=2$, $d(n)=3$, and $d(n)=4$. Then you can easily find $a_1,a_2,a_3$). Then use (a stronger version of?) Bertrand's postulate (but I don't remember how to finish this part) and the problem will be solved really easy (but, the increasing condition helps when you're trying to use Bertrand's postulate).
mahanmath
04.05.2011 21:22
amparvardi wrote: The only thing I remember is that I proved that $a_1=1, a_2=2,a_3=3$, which is not hard (just find the numbers for which $d(n)=2$, $d(n)=3$, and $d(n)=4$. Then you can easily find $a_1,a_2,a_3$). Then use (a stronger version of?) Bertrand's postulate (but I don't remember how to finish this part) and the problem will be solved really easy (but, the increasing condition helps when you're trying to use Bertrand's postulate).
OK , emrooz az Artin shenidam chand ta az talaee ha ham ba Tchebycheff halide boodan , farda miporsam azash ke joziatesho bege behem .....(khodam dige hal nadaram be in masale fek konam kollan!)
Amir Hossein
04.05.2011 21:29
mahanmath wrote:
OK , emrooz az Artin shenidam chand ta az talaee ha ham ba Tchebycheff halide boodan , farda miporsam azash ke joziatesho bege behem .....(khodam dige hal nadaram be in masale fek konam kollan!)
Eival! bashe, mamnun.
- Then please post your solution with Bertrand's postulate, I am interested in seeing how to finish it. Thanks. Any attempts on the generalization of the problem? there should be a nice solution for this problem.
NikoIsLife
08.06.2019 18:14
goodar2006 wrote: Find all increasing sequences $a_1,a_2,a_3,...$ of natural numbers such that for each $i,j\in \mathbb N$, number of the divisors of $i+j$ and $a_i+a_j$ is equal. (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.) I think I have a solution, but I'm not sure if my solution is correct.
I claim that the only solution is $\boxed{a_n=n}$ for all positive integers $n$.
Let $\tau(n)$ be the number of (positive) divisors that $n$ has.
Denote $P(i,j)$ the assertion that $\tau(i+j)=\tau(a_i+a_j)$.
Claim 1: If $p$ is a prime, then $a_{2^{p-2}}=2^{p-2}$.
Proof: From $P(2^{p-2},2^{p-2})$,
$$\tau(2^{p-1})=\tau(2a_{2^{p-2}})\implies\tau(2a_{2^{p-2}})=p$$Since $p$ is prime, the only integers $n$ for which $\tau(n)=p$ are of the form $q^{p-1}$ for some prime $q$. Therefore,
$$2a_{2^{p-2}}=2^{p-1}\implies a_{2^{p-2}}=2^{p-2}$$which proves the claim.$\square$
Claim 2: If $n$ is a positive integer and $p$ is prime such that $p>n\ge2$, then
$$a_{p-n}+a_n=p$$
From $P(p-n,n)$, we have
$$\tau(p)=\tau(a_{p-n}+a_n)\implies\tau(a_{p-n}+a_n)=2$$This implies that $a_{p-n}+a_n$ is a prime number.
Before we continue proving this, we first prove the following subclaim:
Subclaim 2.1: If $n$ is a positive integer and $p$ and $q$ are primes such that $p>q>n\ge2$, then
$$a_{p-n}\ne a_{q-n}$$
Proof: Suppose there exists $n,p,q$ such that $a_{p-n}=a_{q-n}$. Then this means, $a_{p-n}+a_n=a_{q-n}+a_n=r$ for some prime $r$.
Since $p>q\ge3$, this means there is a positive integer $k$ which lies strictly between $p$ and $q$, where $k$ is composite. Since $a_1,a_2,a_3,\ldots$ is an increasing sequence, this means that $a_{k-n}+a_n=r$, which implies that $a_{k-n}+a_n$ is prime.
However, from $P(k-n,n)$,
$$\tau(k)=\tau(a_{k-n}+a_n)\implies\tau(k)=2$$which implies that $k$ is prime, which is a contradiction.$\square$
Now, we prove Claim 2. Let $m$ be the smallest prime such that $2^{m-2}>p$, and let $S$ be the set of all positive integers less than $2^{m-2}$ which are of the form $q-n$ for some prime $q$, and $T$ be the set $\{s_k\mid k\in S\}$.
Since $s_k<s_{2^{m-2}}=2^{m-2}$, this means all the elements of $T$ must be less than $2^{m-2}$ as well. We know that all of the elements from $T$ must be of the form $p-n$ as well, which implies that $T\subseteq S$.
Furthermore, according to Subclaim 2.1, we find that $a_{p-n}\ne a_{q-n}$ for any primes $p$ and $q$ satisfying $p>q>n\ge2$. This implies that all the elements of $T$ are distinct. This shows that $|S|=|T|$, which implies that $S=T$.
Therefore, $a_{p-n}=p-n$ for all $n$ and prime $p$ satisfying $p>n\ge2.\square$
Finally, we use induction to complete the proof that $a_n=n$ for all positive integers $n$.
The base cases are when $n=1$ and $n=2$, which easily follows from Claim 1.
For the inductive step, suppose that we know that $a_n=n$ for all $n=1,2,3,\ldots,k$.
According to Bertrand's Postulate, there exists a prime $p$ such that $k<p<2k$. Also, $p-k<2k-k=k$. From our induction hypothesis, this implies that $a_{p-k}=p-k$. Hence, from Claim 2,
$$a_k+a_{p-k}=p\implies a_k+(p-k)=p\implies a_k=k$$which completes the proof.$\blacksquare$.
Contradiction
28.01.2020 12:13
Solution without Bertrand's Postulate
First, it is easy to show that $a_{2^{p-2}}=2^{p-2}$. Now, we are sufficient to show that $a_n$ is strictly increasing in order to prove $a_n=n$.
Assume that $a_i=a_{i+1}$. For large $X$, since $(X^2-i)+i=X^2$ has odd number of divisors, $a_{X^2-i}+a_i$ also has an odd number of divisors. So $a_{X^2-i}+a_i=a_{X^2-i}+a_{i+1}$ is a square and $a_{X^2-i}+a_{i+1}$ has odd number of divisors too.
This implements that $(X^2-i)+(i+1)=X^2+1$ also has odd number of divisors, which is a contradiction.
Now we get that $a_i<a_{i+1}$ and $a_n$ increases strictly