|
%I #72 Sep 10 2019 03:18:01
%S 1,2,4,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,22,23,24,25,26
%N a(1)=1, a(2)=2 and for n > 2, a(n) is the least integer > a(n-1) such that there is a permutation b(1), ..., b(n) of a(1), ..., a(n) with b(1) = a(1) and b(n) = a(n), and with the n numbers |b(1)-b(2)|, |b(2)-b(3)|, ..., |b(n-1)-b(n)|, |b(n)-b(1)| pairwise distinct.
%C Conjecture: For any n distinct real numbers a_1 < a_2 < ... < a_n, if there is a permutation b_1,b_2,...,b_n of a_1,...,a_n with |b_1-b_2|, |b_2-b_3|, ..., |b_{n-1}-b_n|, |b_n-b_1| pairwise distinct, then there exists a permutation c_1,c_2,...,c_n of a_1,...,a_n with c_1 = a_1 and c_n = a_n such that the n numbers |c_1-c_2|, |c_2-c_3|, ..., |c_{n-1}-c_n|, |c_n-c_1| are pairwise distinct.
%C This conjecture is somewhat curious but we are unable to find a counterexample.
%H Zhi-Wei Sun, <a href="http://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;1d358a7b.1309">A problem on circular permutations</a>, a message to Number Theory List, Sep 01 2013.
%H Z.-W. Sun, <a href="http://arxiv.org/abs/1309.1679">Some new problems in additive combinatorics</a>, arXiv preprint arXiv:1309.1679 [math.NT], 2013-2014.
%e a(3) = 4 since the permutation 1,2,3 does not meet the requirement (since 2-1 = 3-2) but the permutation 1,2,4 is okay as 2-1, 4-2, 4-1 are pairwise distinct.
%e a(4) = 6 since none of the permutations 1,2,4,5 and 1,4,2,5 meets the requirement (since 5-4 = 2-1 and 5-2 = 4-1), but the permutation 1,4,2,6 is okay as 4-1, 4-2, 6-2, 6-1 are pairwise distinct.
%e a(5) = 7 due to the permutation 1,6,2,4,7.
%e a(6) = 8 due to the permutation 1,4,6,2,7,8.
%e a(7) = 9 due to the permutation 1,4,8,6,7,2,9.
%e a(8) = 10 due to the permutation 1,7,4,9,8,6,2,10.
%e a(9) = 11 due to the permutation 1,6,7,9,2,10,4,8,11.
%e a(10) = 12 due to the permutation 1,6,8,9,2,11,7,10,4,12.
%e a(11) = 13 due to the permutation 1,12,2,11,4,10,6,9,7,8,13.
%e a(12) = 14 due to the permutation
%e 1, 13, 2, 12, 4, 11, 6, 10, 7, 9, 8, 14.
%e a(13) = 15 due to the permutation
%e 1, 11, 6, 8, 12, 9, 10, 2, 14, 7, 13, 4, 15.
%e a(14) = 16 due to the permutation
%e 1, 12, 9, 8, 10, 15, 2, 11, 7, 13, 6, 14, 4, 16.
%e a(15) = 17 due to the permutation
%e 1, 12, 9, 13, 4, 16, 6, 11, 10, 8, 14, 7, 15, 2, 17.
%e a(16) = 18 or 19 or 20 due to the permutation
%e 1, 17, 2, 16, 4, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10, 20.
%e Permutations for n = 13, 14, 15 were produced by Qing-Hu Hou at Nankai Univ. on the author's request.
%e From _Charlie Neder_, Aug 23 2018: (Start)
%e a(16) = 18 due to the permutation
%e 1, 11, 10, 12, 9, 13, 8, 14, 7, 15, 6, 17, 4, 16, 2, 18.
%e a(17) = 19 due to the permutation
%e 1, 11, 12, 10, 13, 9, 14, 8, 15, 7, 16, 2, 18, 6, 17, 4, 19.
%e a(18) = 20 due to
%e 1, 12, 11, 13, 10, 14, 9, 15, 8, 16, 7, 17, 2, 19, 6, 18, 4, 20. (End)
%e From _Bert Dobbelaere_, Sep 09 2019: (Start)
%e a(19) = 22 due to the permutation
%e 1, 18, 2, 17, 8, 19, 7, 20, 6, 16, 9, 15, 10, 14, 11, 13, 12, 4, 22.
%e a(20) = 23 due to the permutation
%e 1, 18, 7, 20, 6, 22, 4, 19, 9, 16, 8, 17, 11, 13, 12, 15, 10, 14, 2, 23.
%e a(21) = 24 due to the permutation
%e 1, 19, 10, 20, 7, 18, 4, 16, 9, 17, 11, 15, 12, 14, 13, 8, 23, 6, 22, 2, 24.
%e a(22) = 25 due to the permutation
%e 1, 22, 4, 23, 7, 24, 9, 18, 8, 20, 6, 19, 11, 15, 12, 17, 10, 16, 14, 13, 2, 25.
%e a(23) = 26 due to the permutation
%e 1, 22, 7, 25, 6, 23, 10, 24, 4, 20, 8, 19, 11, 17, 13, 18, 9, 16, 14, 15, 12, 2, 26. (End)
%t A program to find a(16) in terms of the values a(1),...,a(15):
%t V[i_]:=V[i]=Part[Permutations[{2,4,6,7,8,9,10,11,12,13,14,15,16,17}],i]
%t Do[Do[Do[If[Length[Union[{Abs[1-Part[V[i],1]]},Table[Abs[Part[V[i],j]-If[j<14,Part[V[i],j+1],n]],{j,1,14}]]]<15,Goto[aa]];
%t Print[n," "," ",V[i]];Goto[bb];Label[aa];Continue,{i,1,14!}];Continue,{n,18,20}];Label[bb];Break]
%t A228728[n_] := Module[{p, i, j, k, b, lim = 100},
%t If[n <= 2, A228728[n] = n,
%t j = A228728[n - 1] + 1;
%t While[j < lim, A228728[n] = j;
%t p = Permutations[Table[A228728[k], {k, 2, n - 1}]];
%t i = 1; While[i <= Length[p],
%t b = Join[{A228728[1]}, p[[i]], {A228728[n]}]; i++;
%t If[Length[Union[Join[Table[Abs[b[[k]] - b[[k + 1]]], {k, 1, n - 1}], {Abs[b[[n]] - b[[1]]]}]]] == n, Return[j]]]; j++]]]
%t Table[A228728[n], {n, 1, 11}] (* _Robert Price_, Apr 04 2019 *)
%Y Cf. A185645, A187815.
%K nonn,more
%O 1,2
%A _Zhi-Wei Sun_, Aug 31 2013
%E a(16)-a(18) from _Charlie Neder_, Aug 23 2018
%E Name clarified by _Robert Price_, Apr 04 2019
%E a(19)-a(23) from _Bert Dobbelaere_, Sep 09 2019
|
