Сколькими способами можно записать числа от 1 до 100...?

[Ontt]

TOTAL в сообщении #684241 писал(а):

Теперь прыгайте в 12 (12 играет роль 1 из предыдущего участка)

Если 12 играет роль 1 из предыдущего участка, то последовательность будет:
$1\; 3\; 6\; 9\; 11\; 8\; 5\; 2\; 4\; 7\;10$ $(1+11)\; (3+11)\; (6+11)\; (9+11)\; (11+11)\; (8+11) $(5+11)\; (2+11)\; (4+11)\; (7+11)\;(10+11)$.
Соответственно, утверждение "так затаптываем любой участок длины $5+3k$ и готовы повторить" ошибочно, потому что либо мы 1) "затаптываем по $11k$ и повторяем", либо 2) "затаптываем по $5+3k$ и продолжаем, а не повторяем".
Ну а при затаптывании по $11k$ мы столкнемся с необходимостью залезть на числа больше 100.

[TOTAL]

$(5+3k_1) + (5+3k_2) + (5+3k_3) + \cdots$ - где тут ошибка?

[hippie]

Посчитать все способы не удалось. Но получилась нижняя оценка: 51640048830.

Существует 5 способов перестановки 5 последовательных чисел, при которых на первом месте стоит одно из трёх наименьших, а на последнем — одно из трёх наибольших:
$k,\ k+3,\ k+1,\ k+4,\ k+2$;
$k,\ k+2,\ k+4,\ k+1,\ k+3$;
$k+1,\ k+4,\ k+2,\ k,\ k+3$;
$k+1,\ k+3,\ k,\ k+2,\ k+4$;
$k+2,\ k,\ k+3,\ k+1,\ k+4$.
Разобьём все 100 чисел на группы по 5 (1–5; 6–10; 11–15; …; 96–100). И рассмотрим перестановки, в которых каждая пятёрка переставлена одним из 5 перечисленных выше способов.
При этом:
после первого способа может идти первый или второй;
после второго или третьего — первый, второй, третий или четвёртый;
после четвёртого или пятого — третий, четвёртый или пятый.
Всего таких перестановок получается 25820024415. Столько же обратных к ним. В сумме это и даёт $25820024415\cdot 2 = 51640048830$ перестановок.

[Ktina]

hippie в сообщении #684707 писал(а):

...Но получилась нижняя оценка: 51640048830.

Весьма любопытно, что это число встречается в OEIS (аргумент равен 1121).

[Ontt]

TOTAL в сообщении #684251 писал(а):

$(5+3k_1) + (5+3k_2) + (5+3k_3) + \cdots$ - где тут ошибка?

Я понял, спасибо.

hippie в сообщении #684707 писал(а):

Разобьём все 100 чисел на группы по 5

Второй и третий способ - это частные случаи вариантов, предложенных TOTAL, при $k_i=0$.

Ktina в сообщении #684714 писал(а):

аргумент равен 1121

Там два аргумента, а именно: $A(40,6)=51640048830$.

[hippie]

Новая нижняя оценка: 538759201336.

[Ktina]

hippie в сообщении #684882 писал(а):

Новая нижняя оценка: 538759201336.

Не поделитесь, как получили?

[hippie]

Предыдущая оценка уже существенно устарела!


Удалось найти точное количество перестановок удовлетворяющих условию задачи и при этом (одновременно) начинающихся с числа от 1 до 5 и заканчивающихся числом от 96 до 100.
Таких перестановок 8265113664188550.
Вместе с обратными перестановками это даёт новую нижнюю оценку — 16530227328377100 способов.

Следующая программа для Maple вычисляет количество перестановок чисел от 1 до $n$, удовлетворяющих условию задачи и при этом начинающихся с числа от 1 до 5 и заканчивающихся числом от $n-4$ до $n$ для $n$ от 10 до 100.

restart: x:=array(1..101, 1..2): for n from 1 to 101 do: x[n, 1]:=0: x[n, 2]:=0: od: x[4,2]:=1: x[5,2]:=2:
for n from 4 to 100 do: if n mod 3 > 0 then x[n,1]:=x[n,1]+1: x[n+1,1]:=1: fi: od:
for k from 6 to 100 do:
x[k,2]:=x[k-5,1]+x[k-5,2]: 
for n from 4 to k-4 do: if n mod 3 > 0 then x[k,1]:=x[k,1]+x[k-n,1]+x[k-n-1,1]+x[k-n-1,2]: fi: od:
od:
for k from 10 to 100 do: print(k, x[k,1]+x[k-1,1]+x[k,2]+x[k-1,2]+x[k-6,1]+x[k-6,2]): od:

Примечание: правильность результата для $n\le 35$ была проверена прямым перечислением указанных перестановок с помощью следующей программы на с++:

#include <fstream.h>

ofstream file1("2-3 (5-5) Перестановки.txt");
int x[50][50];
void next(int n, int m);

void next(int n, int m)
{int i, j, k;
   if(n==m-3)
      {i=(x[m-3][m-4]-x[m-2][m-4])*(x[m-3][m-4]-x[m-2][m-4]);
      if(i==4 || i==9)
         {j=(x[m-3][m-4]-x[m-4][m-4])*(x[m-3][m-4]-x[m-4][m-4]);
            if(j==4 || j==9)
               {k=(x[m-1][m-4]-x[m-2][m-4])*(x[m-1][m-4]-x[m-2][m-4]);
                  if(k==4 || k==9){x[49][0]++;}
               }
            j=(x[m-3][m-4]-x[m-1][m-4])*(x[m-3][m-4]-x[m-1][m-4]);
            if(j==4 || j==9)
               {k=(x[m-4][m-4]-x[m-2][m-4])*(x[m-4][m-4]-x[m-2][m-4]);
                  if(k==4 || k==9){x[49][0]++;}
               }
         }
      }
   if(n<m-3)
      {for (i=n; i<m-1; i++)
         {j=(x[i][n-1]-x[n-1][n-1])*(x[i][n-1]-x[n-1][n-1]);
         if(j==4 || j==9)
               {for (k=n; k<m; k++){x[k][n]=x[k][n-1];}
                  x[i][n]=x[n][n-1]; x[n][n]=x[i][n-1];
                  next(n+1, m);}
         }
      }
return;
}

void main(void)
{int i1, i2, j, m;
   for (m=10; m<36; m++)
   {x[49][0]=0;
   for (i1=0; i1<m; i1++){x[i1][0]=i1+1;}
   for (i1=0; i1<5; i1++)
      {j=x[0][0]; x[0][0]=x[i1][0]; x[i1][0]=j;
         for (i2=m-1; i2>m-6; i2--)
           {j=x[m-1][0]; x[m-1][0]=x[i2][0]; x[i2][0]=j; next(1, m);}
      }
file1 << m << ", " << x[49][0] << endl << endl;
   }
}

[hippie]

Новая нижняя оценка.

С помощью компьютерных экспериментов удалось обнаружить некоторые закономерности связывающие количество перестановок, удовлетворяющих условию задачи, с заданными первым и последним элементом.
В результате удалось посчитать количество перестановок, удовлетворяющих условию задачи и дополнительному условию: первое число последовательности отличается от последнего не меньше чем на 75 (т.е. $|x_1-x_{100}|\ge 75$).
Количество таких перестановок равно 57870073173592846.

[hippie]

Окончательный ответ: 75331253197821334.

Для $n$ от 1 до 100 у меня получилось следующее количество перестановок удовлетворяющих условию задачи:

1: 1;
2: 0;
3: 0;
4: 2;
5: 10;
6: 12;
7: 8;
8: 12;
9: 30;
10: 72;
11: 106;
12: 128;
13: 186;
14: 316;
15: 546;
16: 836;
17: 1186;
18: 1756;
19: 2720;
20: 4224;
21: 6366;
22: 9374;
23: 13932;
24: 20958;
25: 31470;
26: 46820;
27: 69194;
28: 102458;
29: 152152;
30: 225548;
31: 333142;
32: 490964;
33: 723690;
34: 1067166;
35: 1571878;
36: 2311500;
37: 3395804;
38: 4987584;
39: 7324024;
40: 10747556;
41: 15758418;
42: 23093022;
43: 33831708;
44: 49549838;
45: 72539300;
46: 106146940;
47: 155272874;
48: 227079648;
49: 332013856;
50: 485303902;
51: 709175222;
52: 1036090222;
53: 1513430688;
54: 2210297430;
55: 3227453828;
56: 4711888196;
57: 6878058788;
58: 10038772218;
59: 14650139050;
60: 21377196718;
61: 31189711354;
62: 45501835686;
63: 66375475478;
64: 96816600944;
65: 141207379474;
66: 205936346484;
67: 300316857328;
68: 437925275862;
69: 638551133676;
70: 931039973172;
71: 1357437281908;
72: 1979027686184;
73: 2885135395434;
74: 4205949381400;
75: 6131215621496;
76: 8937479544878;
77: 13027786418408;
78: 18989534941848;
79: 27678786904622;
80: 40343134034054;
81: 58800752326548;
82: 85701330182384;
83: 124906303411094;
84: 182042953223360;
85: 265311869987824;
86: 386663625552054;
87: 563513450168714;
88: 821239890553946;
89: 1196825903714304;
90: 1744164728111946;
91: 2541791661095364;
92: 3704150829211786;
93: 5398013114927704;
94: 7866400327572006;
95: 11463447410338494;
96: 16705203365164138;
97: 24343657734087752;
98: 35474610889786830;
99: 51694860870171028;
100: 75331253197821334.

Просьба проверить полученные результаты и либо подтвердить либо опровергнуть.