Let $ x_1 , x_2, x_3 ...$ a succession of positive integers such that for every couple of positive integers $(m,n)$ we have $ x_{mn} \neq x_{m(n+1)}$ . Prove that there exists a positive integer $i$ such that $x_i \ge 2017 $.
Problem
Source: ITAmo 2017
Tags: number theory, algebra, Ramsey Theory, combinatorics
06.05.2017 12:02
Consider an infinite graph with each vertex represents each positive integer. We connect two vertices if the two integers they represent are of the form $mn,m(n+1)$. In other words, it's not hard to see that we connect two distinct vertices $a$ and $b$ iff $b-a\mid a$. Our goal is to show that there exists a $2017$-clique. Consider $2017$ positive integers $k\cdot 2^{n_1}+2^{n_1-a_i}$ where $a_1<a_2<\cdots <a_{2017}<n_1\in \mathbb{Z}^+$. To make the subgraph whose vertices represent these $2017$ integers a clique, we've to choose $k,a_1,a_2,\dotsc ,a_{2017},n_1\in \mathbb{Z}^+$ so that $$2^{n_1-a_i}-2^{n_1-a_j}\mid k\cdot 2^{n_1}+2^{n_1-a_i}$$for all $i< j \in \{ 1,2,\dotsc ,2017\}$. Note that the condition is equivalent to $$2^{a_j-a_i}-1\mid k\cdot 2^{n_1-(n_1-a_j)} +2^{a_j-a_i}\iff k \equiv \frac{1}{2^{a_j}}, \frac{1}{2^{a_j}}\pmod{2^{a_j-a_i}-1}.$$So, to avoid the flaw while using CRT, we have to consider the case when $\gcd (2^{a_j-a_i}-1,2^{a_r-a_s}-1)\neq 1$. In that case, we're required to construct $$1+2^{n_2-n_1}+2^{n_3-n_1}+\cdots+2^{n_k-n_1}$$so that it's $\equiv \frac{1}{2^{a_i}},\frac{1}{2^{a_j}} \pmod{2^{a_j-a_i}-1}$ and $\equiv \frac{1}{2^{a_r}},\frac{1}{2^{a_s}}\pmod{2^{a_r-a_s}-1}$. In other word, we've to ensure that $\gcd (2^{a_j-a_i}-1,2^{a_r-a_s}-1) \mid 2^x-2^y$ for all $x\in \{ a_r,a_s\},y\in \{ a_i,a_j\}$. Note that it's enough to consider only when all of $a_i,a_j,a_r,a_s$ are pairwise distinct. Now, our aim is to construct $a_1<a_2<\cdots <a_{2017}$ that $\gcd (a_j-a_i,a_r-a_s) =\gcd ( a_i,a_j,a_r,a_s)$ for all pairwise distinct $i,j,r,s\in \{ 1,2,...,2017\}$. Let $P$ denote the set of all prime number not greater than $2017$ and let $T$ denote their product. By CRT, there exists a positive integer $K$ that $K\equiv p \pmod{p^2}$ for all $p\in P$. We'll choose $a_1,a_2,\dotsc ,a_{2017}$ so that all of them $\equiv K\pmod{T^2}$ and there is no prime number $p>2017$ that $p\mid a_j-a_i$. Let's inductively choose $a_i$ from $i=1,2,\dotsc ,2017$. Suppose we have chosen $a_1,a_2,\dotsc ,a_z$ for some $z<2017$. Denote $R$ the set of all prime divisor greater than $2017$ of $\prod_{w=1}^{z}{a_w}$. When we construct $a_{z+1}$, we add the condition that $a_{z+1} \not\equiv 0 \pmod{p}$ for all $p\in R$ in our CRT conditions. So, the inductive step is completed. Finally, use CRT to construct $k$ in modulo $p$ for each $p\mid \prod_{1\leqslant i<j\leqslant 2017}{(2^{a_j-a_i}-1)}$.
06.05.2017 14:25
So the natural question that arises here is the following: What's the maximal number $n$ (in terms of $k$) such that such a sequence $a_1,a_2,\dotsc,a_n$ exists with at most $k$ different numbers occuring. For instance, we have $n(1)=1, n(2)=3, n(3)=11$ (with the maximal sequences $(1,2,1)$ and $(1,2,1,3,1,2,3,1,3,2,1)$.)
07.05.2017 22:49
GoJensenOrGoHome wrote: Let $ x_1 , x_2, x_3 ...$ a succession of positive integers such that for every couple of positive integers $(m,n)$ we have $ x_{mn} \neq x_{m(n+1)}$ . Prove that there exists a positive integer $i$ such that $x_i \ge 2017 $. The same idea as in the post #3, but with a bit shorter realization. We translate it in the graph theory language- consider a graph $G$ with vertices the positive integers and connect two $n,m\in \mathbb{N}$ iff $m-n\mid n$. We want to show the chromatic number of that infinite graph is also infinite. The most natural way is to show there are cliques of size as big as we want. We will construct such cliques by induction on their size. Suppose $m_1<m_2<\dots<m_n$ be a clique with $n$ vertices. That's, $m_j-m_i \mid m_i$ for all $1\leq i,j\leq n, i\neq j$. Now, consider some $n+1$ points: $m, m+m_1, m+m_2, \dots, m+m_n$. Can we find such $m$, so that it would be a clique. Of course, it is enough to take $m$ be multiple of all $m_j-m_i\,,\,1\leq i,j\leq n, i\neq j $ and all $m_i, i=1,2,\dots,n$ . So, the induction step is completed.
24.03.2020 16:21
We will find $n$ distinct positive integers $a_1, a_2, \dots, a_n$ such that for any two $i,j \in \{1, 2, \dots, n\}$, we have $(a_i-a_j) \mid a_j$. This would finish the problem by letting $n=2017$ and using pigeonhole. We can construct the numbers by induction on $n$. The base case $n=2$ is trivial. Suppose we have already constructed $n$ numbers $a_1, a_2, \dots, a_n$ satisfying $(a_i-a_j) \mid a_j$; we want to choose a positive integer $a$ for which $$a, a+a_1, a+a_2, \dots, a+a_n$$satisfies the same relation. Indeed, we can take $$a = \text{LCM} (a_i, a_i-a_j)$$over all $i,j$, then because $(a+a_j)-(a+a_i)=a_j-a_i$ is divisible by both $a$ and $a_j$, it's divisible by $a+a_j$.
04.11.2024 22:25
Any similar problem?