2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение15.02.2013, 15:00 


06/02/13
325
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.

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение15.02.2013, 15:06 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
$(5+3k_1) + (5+3k_2) + (5+3k_3) +  \cdots$ - где тут ошибка?

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение16.02.2013, 17:56 
Заслуженный участник


18/01/12
933
Посчитать все способы не удалось. Но получилась нижняя оценка: 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$ перестановок.

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение16.02.2013, 18:21 
Аватара пользователя


01/12/11

8634
hippie в сообщении #684707 писал(а):
...Но получилась нижняя оценка: 51640048830.

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

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение16.02.2013, 20:18 


06/02/13
325
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$.

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение17.02.2013, 11:32 
Заслуженный участник


18/01/12
933
Новая нижняя оценка: 538759201336.

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение18.02.2013, 02:23 
Аватара пользователя


01/12/11

8634
hippie в сообщении #684882 писал(а):
Новая нижняя оценка: 538759201336.

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

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение20.02.2013, 20:30 
Заслуженный участник


18/01/12
933
Предыдущая оценка уже существенно устарела!


Удалось найти точное количество перестановок удовлетворяющих условию задачи и при этом (одновременно) начинающихся с числа от 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;
   }
}

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение23.02.2013, 20:06 
Заслуженный участник


18/01/12
933
Новая нижняя оценка.

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

 Профиль  
                  
 
 Re: Сколькими способами можно записать числа от 1 до 100...?
Сообщение24.02.2013, 16:56 
Заслуженный участник


18/01/12
933
Окончательный ответ: 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.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group