Is there a positive integer $N$, besides 1 and 2, such that there is a permutation $a_1=1,a_2,a_3,\dots,a_N$ of $1,2,3,\dots,N$ in which for each $k>1$, $a_k=a_{k-1}\div k,a_k=a_{k-1}-k,a_k=a_{k-1}+k,\textrm{or }a_k=a_{k-1}\times k$?
$\begingroup$
$\endgroup$
5
asked Feb 12, 2017 at 3:12
-
$\begingroup$ How far have you computed beyond $N=2$? $\endgroup$– Noam D. ElkiesFeb 12, 2017 at 3:37
-
$\begingroup$ Not many. Consider the last three entries. Welcome to MathOverflow! Gerhard "Looking Forward To More Sequences" Paseman, 2017.02.11. $\endgroup$– Gerhard PasemanFeb 12, 2017 at 3:41
-
2$\begingroup$ @NoamD.Elkies $1,3,9,5,10,60,53,61,52,62,51,63,50,64,49,65,48,66,47,67,46,68,45,69,44,70,43,71,42,72,41,73,40,74,39,75,38,76,37,77,36,78,35,79,34,80,33,81,32,82,31,83,30,84,29,85,28,86,27,87,26,88,25,89,24,90,23,91,22,92,21,93,20,94,19,95,18,96,17,97,16,98,15,99,14,100,13$. This permutation of the integers up to 100 satisfies the required arithmetical conditions but leaves out the following 13 numbers: $2,4,6,7,8,11,12,54,55,56,57,58,59$. $\endgroup$– Freddy BarreraFeb 12, 2017 at 4:02
-
4$\begingroup$ If it leaves out those numbers, it's not actually a permutation, is it? $\endgroup$– Gerry MyersonFeb 12, 2017 at 6:13
-
1$\begingroup$ Barrera´s example above shows that if one attempts to permute the integers up to 100 according to his rules, one can fit at least 87 numbers, leaving just 13 out. It would be interesting to know if for values greater than 100 one can fit a higher proportion of the numbers, perhaps approaching 100%. I conjecture this is the case. $\endgroup$– Bernardo Recamán SantosFeb 12, 2017 at 12:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
This is implicit in Gerhard Paseman's answer but it should be made explicit: what you ask for is not possible, for a fairly simple reason. Consider $a_N$. There are four possibilities: $$ (1)\qquad a_N = a_{N-1}/N $$ but this can't be satisfied, because $a_{N-1}\le N$, so either $a_{N-1}$ doesn't divide $N$ or $a_{N-1}=N$, in which case $a_N=1$ --- but $a_N$ can't be 1 because it was specified that $a_1 = 1$. So we know that $a_N \ne a_{N-1}/N$. $$ (2)\qquad a_N = a_{N-1} - N $$ but this can't be satisfied, because $a_{N-1}\le N$, so $a_N$ would have to be zero or negative. So we know that $a_N \ne a_{N-1} - N$. $$ (3)\qquad a_N = a_{N-1} + N $$ but this can't be satisfied, because $a_{N-1}\ge 2$, so $a_N$ would have to be greater than $N$. So we know that $a_N \ne a_{N-1} + N$. $$ (4)\qquad a_N = N a_{N-1} $$ but this can't be satisfied if $N>2$, because in that case $a_{N-1}\ge 2$, so $a_N$ would have to be greater than $N$. So we know that $a_N \ne N a_{N-1}$.
So your stipulation that $a_1=1$ makes it impossible for any $N>2$.
$\begingroup$
$\endgroup$
3
It may be of interest to see how far it can be continued, but it cannot be completed. Suppose we ignore the restriction that the first term must be 1. The last term must be the previous term times or divided by N. So the last two terms are 1,N or N,1. Now unless N is 2, there is no way to use N-1 to generate the term N and maintain a permutation, so the second to last term must be 1, from which it follows the previous term must be N-1. If N is 3, this gives the last remaining permutation 2,1,3 satisfying the relaxation. For if N is greater, there is no way to use N-2 to make N-1 without using 1, and so the permutation property is broken.
As evidenced in the comments, one can use plus and minus as alternating operations to generate long stretches of the permutation having the properties desired for many k.
Gerhard "Recommends Asking Another, Separate Question" Paseman, 2017.02.11.
answered Feb 12, 2017 at 4:17
-
$\begingroup$ A question: what's the lexicographically least infinite sequence that obeys this rule? (It should be placed in oeis. I bet Neil Sloane would like it.) $\endgroup$ Feb 12, 2017 at 4:55
-
$\begingroup$ I think it starts 1,2,5,9,4,10,3,11,99. Gerhard "Unless You Can Do Better" Paseman, 2017.02.11. $\endgroup$ Feb 12, 2017 at 5:09
-
1$\begingroup$ Removing the restriction that the first term be 1 often allows all but one integer to be permuted. $\endgroup$ Feb 12, 2017 at 13:16