3
$\begingroup$

A permutation $P$ of $\{0,1, \dots n-1 \}$ is called square permutation if $P(i) + i$ is a perfect square for all $0 \leq i \leq n-1$. Prove that:

if $n=2023$ and $P$ is a square permutation, then there exists $i$ such that $3 \mid P(i) + i$

My first thought was that it should be true for all $n$, but I've quickly recognized that it's not. For example, if $n = k^2 + 1$ for some $3 \nmid k$ then the permutation $P(i) = k^2 - i$ is square permutation (since $P(i) + i = k^2$) but $3 \nmid P(i) + i$ for all $i$.

Later, I've observed that a square permutation exists for all $n$. The proof by induction is quite direct: it is obviously true when $n=1$, then for any $n > 1$

  1. select $k$ smallest so that $k^2 \geq n-1$,
  2. for all $i \geq k^2-n+1$, set $P(i) = k^2 - i$, so $P(i) + i = k^2$ for all $k^2 - n +1 \leq i \leq n-1$.

The problem is reduced to construct a square permutation for $n' = k^2 -n+1$ which is smaller than $n$.

For example, $n=12$:

  1. select $k$ = 4 (since $4^2 = 16 \geq 12-1$),
  2. set $P(i) = 16 - i$ for $5 \leq i \leq 11$.

Now problem is reduced to $n=5$:

  1. select $k$ = 2 (since $2^2 = 4 \geq 5 - 1$),
  2. set $P(i) = 4 - i$ for $0 \leq i \leq 4$.

The square permutation constructed is: $$ P=\Bigl(\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 4 & 3 & 2 & 1 & 0 & 11 & 10 & 9 & 8 & 7 & 6 & 5 \end{matrix}\Bigr) $$

By this constructive proof, I've recognized that there are many cases of $n$ for which there is a square permutation so that $3 \nmid P(i) + i$ for all $i$. For example, in the example above, we have constructed a square permutation where $P(i) + i$ is either $16$ or $4$.

So $2023$ seems to be a special value, but I've no clue why.

Thanks for any hint.

NB. I believe that square permutation is first introduced in this paper. The proof for the existence is similar to mine.

$\endgroup$

1 Answer 1

5
$\begingroup$

It is actually simple. Suppose that $3 \nmid P(i) + i$ for all $i$, then $P(i) + i \equiv 1 \pmod 3$ for all $i$ (because $P(i)+i$ being a square implies $P(i)+i\not\equiv 2\pmod 3$). So

$$ \sum\limits_{i=0}^{2023-1} (P(i) + i) \equiv 2023 \equiv 1 \pmod 3 $$

But

$$ \sum\limits_{i=0}^{2023-1} (P(i) + i) = 2 \times \sum\limits_{i=0}^{2023-1} i = 2022 \times 2023 \equiv 0 \pmod 3 $$ So is a contradiction.

$\endgroup$
3
  • $\begingroup$ You say that $3\nmid P(i)+i$ implies $P(i)+i\equiv1\pmod3$, but you could also have $P(i)+i\equiv2\pmod3$. Also, you never used the fact that $P$ is a square permutation. $\endgroup$ Commented Aug 3, 2023 at 18:34
  • $\begingroup$ @MikeEarnest since $P(i) + i$ is a perfect square, so if $3 \nmid P(i) + i$ then $P(i) + i \equiv 1 \pmod 3$. $\endgroup$ Commented Aug 3, 2023 at 19:27
  • 1
    $\begingroup$ I apologize, very nice answer. I added in some explanation so that no one else gets confused like me and complains. $\endgroup$ Commented Aug 3, 2023 at 19:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .