4
$\begingroup$

Call a permutation $\left(p_1,p_2,\cdots{},p_n\right)$ of $\left(1,2,\cdots{},n\right)$ quadratic if there exists a perfect square among $$p_1,p_1+p_2,\cdots{},p_1+p_2+\cdots{}+p_n.$$ Find all natural numbers $n$ such that all the permutations of $(1,2,\cdots{},n)$ are quadratic.

$\endgroup$
  • $\begingroup$ May not help much, but there are infinitely many of them. Just take any $n$ which is both a triangular number and a perfect square (then the final sum is a square). Do you know any examples not of this form? $\endgroup$ – lulu Dec 4 '15 at 13:16
  • $\begingroup$ Interesting, though invalid question. For $n = 2$, we already have $2,1$ which is not quadratic. Combined with lulu's comment, I think this question needs some work. Is there a reason behind this question? $\endgroup$ – Pieter21 Dec 4 '15 at 13:19
  • $\begingroup$ @lulu: Yep! The answer is the set of those $n$ for which $\dfrac{n(n+1)}{2}$ is perfect square $\endgroup$ – Jack Frost Dec 4 '15 at 13:23
  • $\begingroup$ To clarify my comment (which was poorly phrased): I meant take any $n$ such that $1+\dots+n$ is a perfect square. Thus that sum is both a triangular number and a perfect square. $\endgroup$ – lulu Dec 4 '15 at 13:23
  • 1
    $\begingroup$ See OEIS sequence A001110. $\endgroup$ – Robert Israel Dec 4 '15 at 18:51
4
$\begingroup$

Bravo to the commenters. Some really interesting stuff going on there. I will just attempt here to consolidate their thoughts into an answer, because the ideas presented there are haphazard, creative and somewhat disorganised. There is a general statement that can be made which subsumes the reasoning in what I think is an elegant way. See the following lemma.

Lemma: For any natural $n > 0$, there exists a permutation $p_1, p_2, \dots, p_n$ of the first $n$ natural numbers such that (i) for all $k < n$ (notice strictness), the term $\sum_{i=1}^kp_i$ is not square and (ii) if $\sum_{i=1}^np_i$ is square, then $p_n = n$.

Proof: By induction on $n$. The base case is trivial, for there are clearly no positive natural numbers less than $1$, and clearly $p_1 = 1$. For the inductive case, I borrow heavily from a comment above of the OP. We simply take the sequence $p_1, p2, \dots, p_n$, and consider two cases:

  • If $\sum_{i=1}^np_i$ is a square, call it $s^2$. By part (ii) of the inductive hypothesis we have that $p_n = n$. Then for our permutation of size $n+1$, we copy all $p_i$ from the old permutation of length $n$, and simply replace $p_n$ with $n+1$ and set $p_{n+1}$ to $n$. Clearly this gives us condition (i) for our new sequence, for all the partial sums up to length $n-1$ are the same as before, and the sum up to $p_n$ is $s^2 + 1$, which is never square. Now we must show that the sum up to $p_{n+1}$ is not square, or else we violate condition (ii). Well, this follows from the fact that no two consecutive triangle numbers are squares, which is evident from the recurrence relation given in the link provided in the comments: tri-squares.

  • If $\sum_{i=1}^np_i$ is not a square, then we have it easy. Just take the old permutation and append $p_n = n$ to it. Clearly conditions (i) and (ii) are now met.

Corollary: This lemma immediately gives us that the numbers whose permutations are all quadratic are exactly the triangular square numbers, and no other numbers.


Update: The OEIS link provided by Robert Israel in his comment gives us the following property for the sequence of square-triangular numbers $a(n)$: "For every $n$, $a(n)$ is the first of three triangular numbers in geometric progression. The third number in the progression is $a(n+1)$." This clearly gives us the property needed in the above proof, which is that there are no consecutive triangular numbers that are also square.

$\endgroup$
  • 1
    $\begingroup$ Thanks! Couldn't get it to work out, for whatever reason. Much appreciated. $\endgroup$ – lulu Dec 4 '15 at 19:57
  • $\begingroup$ My pleasure! I basically just took the comments and flattened them out- grunt work :) $\endgroup$ – Colm Bhandal Dec 4 '15 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.