$n$ is a natural number. We shall call a permutation $a_1,\dots,a_n$ of $1,\dots,n$ a quadratic(cubic) permutation if $\forall 1\leq i \leq n-1$ we have $a_ia_{i+1}+1$ is a perfect square(cube). $(a)$ Prove that for infinitely many natural numbers $n$ there exists a quadratic permutation. $(b)$ Prove that for no natural number $n$ exists a cubic permutation.
Problem
Source: Iran TST 2014, second exam, day 2 ,problem 1
Tags: quadratics, number theory unsolved, number theory
02.01.2015 05:42
For part $(a)$, the identity $(x-1)(x+1) + 1 = x^2$ is important. This gives us the following construction (for any positive integer $k$) \[ 2, 4, 6, \ldots, 4k^2+4k, 1, 3, 5, \dots, 4k^2+4k-1 \] For part (b) take the largest power of $2$ less than or equal to $n$. Say that it's $2^k$. Note that $2^k > n/2$. If $2^k \mid x^3-1$ for some $x$, since $\gcd(2, x^2+x+1) = 1$, we have $2^k \mid x-1$. Since $2^k \cdot a_i + 1 = x^3$ (a cube) for some $i$, then $2^k \mid x-1$. Since $x > 1$, it follows $x \ge 2^k+1$, so $a_i \ge \frac{(2^k+1)^3-1}{2^k} = 2^{2k} + 3\cdot 2^k + 3 > n^2/4 + 3n/2 + 3 > n$.
31.01.2015 20:29
This problem is given by Dr. Mohsen Jamali
08.04.2017 15:10
a) Pick $2\mid x$ and number $n:=x(x+2)$.Then consider : $$246\dots [x(x+2)]13\dots [x(x+2)-1]$$By using $y(y+2)+1=(y+1)^2$ and $x(x+2)+1=(x+1)^2$ we obtain the desired.$\blacksquare$ b)Let $x=5^{\lfloor \log_5{n}\rfloor}$.And suppose $\exists y\leq n$ so that $yx+1=z^3$ $\implies $ $(z-1)(z^2+z+1)=yx$ but $(z^2-z+1,5)=1$ $\implies$ $x\mid z-1$, $z=kx+1$ where $k\geq 1$.We have : $$y=x^2k^3+3k+3xk^2\geq x^2+3+3x\geq 5x+2>5x$$Contradiction as $y\geq n$.$\blacksquare$