We say a positive integer $ n$ is good if there exists a permutation $ a_1, a_2, \ldots, a_n$ of $ 1, 2, \ldots, n$ such that $ k + a_k$ is perfect square for all $ 1\le k\le n$. Determine all the good numbers in the set $ \{11, 13, 15, 17, 19\}$.
Problem
Source: CGMO 2004 P1
Tags: combinatorics unsolved, combinatorics
jgnr
28.12.2008 02:25
If 11 is good, $ a_4$ must equal 5 and $ a_{11}$ must equal 5. Contradiction.
13, 15, 17, 19 is good, because:
13: 8,2,13,12,11,10,9,1,7,6,5,4,3
15: 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
17: 3,7,6,5,4,10,2,17,16,15,14,13,12,11,1,9,8
19: 8,7,6,5,4,3,2,1,16,15,14,13,12,11,10,9,19,18,17
ppwwyyxx
18.07.2010 16:40
I found out a surprising fact:for all the integers n>11, n is a good number! I used a computer and tried n from 12 to 68 and it's right! Someone can prove it？ Maybe you can get some inspiration from this:
when 12<=n<=20, all the possible a1,a2...an are the following
12
3 2 1 12 11 10 9 8 7 6 5 4
13
8 2 13 12 11 10 9 1 7 6 5 4 3
14
3 2 1 5 4 10 9 8 7 6 14 13 12 11
14
8 14 13 12 11 10 9 1 7 6 5 4 3 2
15
3 2 6 5 4 10 9 8 7 15 14 13 12 11 1
15
8 2 6 5 4 3 9 1 7 15 14 13 12 11 10
15
15 2 1 5 4 3 9 8 7 6 14 13 12 11 10
15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
16
3 7 6 5 4 10 2 8 16 15 14 13 12 11 1 9
16
8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9
16
15 7 1 5 4 3 2 8 16 6 14 13 12 11 10 9
17
3 7 6 5 4 10 2 17 16 15 14 13 12 11 1 9 8
17
15 7 1 5 4 3 2 17 16 6 14 13 12 11 10 9 8
18
3 2 6 5 4 10 18 17 16 15 14 13 12 11 1 9 8 7
18
3 7 6 5 4 10 2 17 16 15 14 13 12 11 1 9 8 18
18
15 2 1 5 4 3 18 17 16 6 14 13 12 11 10 9 8 7
18
15 7 1 5 4 3 2 17 16 6 14 13 12 11 10 9 8 18
18
15 14 13 12 11 10 18 17 16 6 5 4 3 2 1 9 8 7
19
3 2 1 5 4 19 18 17 16 15 14 13 12 11 10 9 8 7 6
19
3 2 6 5 4 10 18 8 16 15 14 13 12 11 1 9 19 7 17
19
3 2 6 5 4 19 18 1 16 15 14 13 12 11 10 9 8 7 17
19
3 7 1 5 4 19 2 17 16 15 14 13 12 11 10 9 8 18 6
19
3 7 6 5 4 10 2 8 16 15 14 13 12 11 1 9 19 18 17
19
3 7 6 5 4 19 2 1 16 15 14 13 12 11 10 9 8 18 17
19
8 2 1 5 4 3 18 17 16 15 14 13 12 11 10 9 19 7 6
19
8 2 6 5 4 3 18 1 16 15 14 13 12 11 10 9 19 7 17
19
8 7 1 5 4 3 2 17 16 15 14 13 12 11 10 9 19 18 6
19
8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 19 18 17
19
8 14 13 12 11 10 18 17 16 15 5 4 3 2 1 9 19 7 6
19
15 2 1 5 4 3 18 8 16 6 14 13 12 11 10 9 19 7 17
19
15 7 1 5 4 3 2 8 16 6 14 13 12 11 10 9 19 18 17
19
15 14 13 12 11 10 18 8 16 6 5 4 3 2 1 9 19 7 17
19
15 14 13 12 11 19 18 1 16 6 5 4 3 2 10 9 8 7 17
20
3 2 1 5 4 19 9 17 7 15 14 13 12 11 10 20 8 18 6 16
20
3 2 6 5 4 10 9 8 7 15 14 13 12 11 1 20 19 18 17 16
20
3 2 6 5 4 19 9 1 7 15 14 13 12 11 10 20 8 18 17 16
20
8 2 1 5 4 3 9 17 7 15 14 13 12 11 10 20 19 18 6 16
20
8 2 6 5 4 3 9 1 7 15 14 13 12 11 10 20 19 18 17 16
20
8 2 13 12 20 10 18 17 16 15 14 4 3 11 1 9 19 7 6 5
20
8 7 13 12 11 10 9 17 16 15 14 4 3 2 1 20 19 18 6 5
20
8 7 13 12 20 10 2 17 16 15 14 4 3 11 1 9 19 18 6 5
20
8 14 13 12 11 10 9 17 7 15 5 4 3 2 1 20 19 18 6 16
20
8 14 13 12 20 10 2 17 7 15 5 4 3 11 1 9 19 18 6 16
20
15 2 1 5 4 3 9 8 7 6 14 13 12 11 10 20 19 18 17 16
20
15 2 13 12 20 10 18 8 16 6 14 4 3 11 1 9 19 7 17 5
20
15 2 13 12 20 19 18 1 16 6 14 4 3 11 10 9 8 7 17 5
20
15 7 13 12 11 10 9 8 16 6 14 4 3 2 1 20 19 18 17 5
20
15 7 13 12 11 19 9 1 16 6 14 4 3 2 10 20 8 18 17 5
20
15 7 13 12 20 10 2 8 16 6 14 4 3 11 1 9 19 18 17 5
20
15 7 13 12 20 19 2 1 16 6 14 4 3 11 10 9 8 18 17 5
20
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 20 19 18 17 16
20
15 14 13 12 11 19 9 1 7 6 5 4 3 2 10 20 8 18 17 16
20
15 14 13 12 20 10 2 8 7 6 5 4 3 11 1 9 19 18 17 16
20
15 14 13 12 20 19 2 1 7 6 5 4 3 11 10 9 8 18 17 16