2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 "Сорок одно число"
Сообщение24.11.2016, 20:55 


24/11/16
6
Вспомнилась одна интересная задача, которую разбирали в школе в конце девяностых. Придумал её наш учитель, которого, увы, уже нет в живых.
Дано 41 число: 1, 2, ..., 41. Числа от 2 до 41 переставили, а число 1 осталось на своём месте. Известно, что в получившейся последовательности чисел разность между любыми двумя соседними числами равна одному или двум. Сколько перестановок удовлетворяют условию задачи?

Очевидно, что на втором месте будет 2 (тогда на третьем 3 или 4) или 3 (на третьем 2, 4 или 5). Но как двигаться дальше? Был бы признателен за помощь.

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 21:15 


28/07/13
165
Если некоторые числа переставились на своё же место, это считается "перестановкой" в вашем смысле?

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 21:19 


24/11/16
6
Да, конечно. Не рассматривается только вариант, когда последовательность якобы осталась такой же, как и была.

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 21:31 


28/07/13
165
Почему
ERoznat в сообщении #1171480 писал(а):
Очевидно, что на втором месте будет 2


UPD. Извиняюсь, я сначала не заметил "или 3" у вас.

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 21:35 


24/11/16
6
Я руководствуюсь тем, что на первом месте осталась единица. Так как разность между двумя соседними числами 2 или 1, то на второй позиции будет 2 или 3. Числа от 4 до 41 условию задачи не удовлетворяют.

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 21:37 


28/07/13
165
Можно рекуррентное соотношение выписать (оно линейное). А потом посчитать на компьютере (6585451).

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 22:08 


24/11/16
6
Я, увы, обучался в классе с уклоном на физмат, но жизнь связал с экологией. :D
Можете объяснить на примере, допустим, с аналогичным условием, но для 51 числа, а не для 41, как составляется реккурентное соотношение для таких задач?

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 22:14 


28/07/13
165
Тут всё одинаково для 31, 41 и $n$. Грэхем, Кнут и Поташник написали одну известную книгу, которую вы легко найдете в интернетах, и начинается она с уроков "на пальцах", как составлять рекуррентные соотношения.

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение24.11.2016, 22:20 
Заслуженный участник
Аватара пользователя


13/08/08
14424
В изначальной строке без единицы можно выделить произвольное число несоприкасающихся пар и перевернуть их:
$123456789... \to 132457689...$

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение25.11.2016, 01:01 
Заслуженный участник


10/01/16
2315
ERoznat в сообщении #1171480 писал(а):
что на втором месте будет 2

и мы получили ровно такую же задачу, но с 40 числами.
ERoznat в сообщении #1171480 писал(а):
или 3

Но где же тогда 2?
Она - либо следующая , и тогда далее - 4, и опять получилась такая же задача - но для 38,
либо она - в конце (ибо у нее остался токо один "допустимый сосед"). Но тогда - чтоб не было перескоков больших - все однозначно: в начале возрастая идут нечетные, а затем - убывая - четные.
Вместе это и даст рек. соотношения, о которых грит user14284
К сожалению, явной формулы - не получим: у соответствующего кубического ур-я - плохие корни...

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение25.11.2016, 19:35 


24/11/16
6
Хорошо.
Соответственно, вероятность такого события будет равна, как я понимаю, $6585451/((n-1)!)$ ?

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение25.11.2016, 20:16 


28/07/13
165
Какого события и при чём тут вероятность?

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение26.11.2016, 17:00 


24/11/16
6
user14284 в сообщении #1171688 писал(а):
Какого события и при чём тут вероятность?

Ну давайте так сформулирую. Дана последовательность из 41 числа, перемешали так же, как и выше, 40 чисел от 2 до 41. Пусть событие К - после перемешивания чисел разность между двумя любыми соседними числами не более двух. Будет ли равно P(K) тому выражению, которое я изложил выше?

 Профиль  
                  
 
 Re: "Сорок одно число"
Сообщение26.11.2016, 18:17 


28/07/13
165
Да, если $n=41$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

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



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

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


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

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