Find the greatest positive integer $m$ with the following property: For every permutation $a_1, a_2, \cdots, a_n,\cdots$ of the set of positive integers, there exists positive integers $i_1<i_2<\cdots <i_m$ such that $a_{i_1}, a_{i_2}, \cdots, a_{i_m}$ is an arithmetic progression with an odd common difference.
Problem
Source: 2013 China TST Quiz 2 Day 2 P2
Tags: arithmetic sequence, number theory, China TST, algebra proposed
31.03.2013 16:57
Very easy problem. The greatest positive integer $m$ is 3. For any permutation of the set of positive integers, we can prove that there always exists $i_1<i_2<i_3$ such that $a_{i_1},a_{i_2},a_{i_3}$ form an arithmetic series with an odd common difference. Let $i\ge2$ be the smallest integer such that $\{a_1,a_2,...a_i\}$ contains both odd and even integers(suppose $a_s(s\le i)$ is odd, $a_t(t\le i)$ is even) and $M=max\{a_1,a_2,...a_i\}$. Let $j>i$ be the first integer such that $a_j > M$, then $2a_j-a_s>a_j,2a_j-a_t>a_j$. So there exists some $p>j,q>j$ such that $a_p=2a_j-a_s,a_q=2a_j-a_t$, either $a_s,a_j,a_p$ or $a_t,a_j,a_q$ is an arithmetic series with an odd common difference. Let $a_{3n-2}=2n-1,a_{3n-1}=4n-2,a_{3n}=4n$, we can see that $\{a_n\}$ is a permutation of the set of positive integers. Suppose there exists positive integers $i_1<i_2<i_3<i_4$ such that $a_{i_1},a_{i_2},a_{i_3},a_{i_4}$is an arithmetic series with an odd common difference. Let $a_{i_k}(k \in \{3,4\})$ be an even intger, then $0<a_{i_{k-2}}<a_{i_{k-1}}<a_{i_{k}},a_{i_{k-1}}$ is odd and $2a_{i_{k-1}}\le a_{i_k}$, contradicting the fact that $2a_{i_{k-1}}=a_{i_{k-2}}+ a_{i_k}$.
30.10.2024 15:06
Sketch by swynca and me. Answer is $3$. Suppose that there is no arithmetic progression with length $3$. Let $M$ be larger than each positive integer coming before $1$ on the line. Consider all $1(mod \ M)$ positive integers, note that none of them is left to $1$. Let these numbers be $Mx_i+1$ on the row with $x_1=0$. We study on $\{x_i\}_{i=1}^{\infty}$. For any odd $t$, $x,x+t,x+2t$ don't lie on this order in the row. We observe that $2t$ must come before $t$. Let $t$ be an odd number. Let $k$ be a fixed number larger than any number left to $t$. $t+2k$ must be between $t$ and $t+k$. Since $(0,t+2k,2t+4k)$ is an arithmetic progression with odd common difference, $2t+4k$ must lie between $t,t+2k$. $(t,2t+4k,3t+8k)$ is an arithmetic progression with odd common difference thus, $3t+8k$ must be between $t$ and $2t+4k$. If we continue this process with looking $(0,odd,even)$ and $(t,even,odd)$ respectively, there exist infinitely many numbers between $t$ and $t+2k$ which is impossible. Now we present a sequence where any arithmetic progression with length $4$ doesn't exist. We write $2,1,4,6,3,8,10,15,12...$ in a row with this order. We put the smallest even integer not written before, after that if its half doesn't exist before that even number, then we add its half. It can be checked manually.$\blacksquare$