2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Десять чисел в ряд
Сообщение07.11.2015, 00:28 
Аватара пользователя


01/12/11

8634
Сколькими способами можно расставить натуральные числа от 1 до 10 в ряд так, чтобы каждое (кроме первого) число было делителем суммы всех предыдущих?

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 07:59 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Сумма всех чисел 55. Отсюда следует, что на последнем месте может стоять 1 или 5. Что если организовать процесс задом наперёд? то есть начинаем с десятой позиции и ставим числа так, чтобы разница между 55 и суммой написанных чисел делилась на это число?
Мне кажется, что задачу надо попробовать решить для меньших чисел.
$2: (2,1)$
$3: (2,1,3),(3,1,2)$
$4: (3,1,4,2),(4,2,3,1)$
Для пяти у меня чего-то заскок произошёл :oops:

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 17:30 
Заслуженный участник


26/05/14
981
22 способа. Вычислено полным перебором.

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 18:24 
Аватара пользователя


01/12/11

8634
slavav
Вручную?

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 19:03 
Заслуженный участник


26/05/14
981
Нет, не вручную. Перебором всех перестановок и проверкой их свойств на компьютере. $10!$ - не большое число.

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 19:37 
Заслуженный участник
Аватара пользователя


01/09/13
4318
slavav в сообщении #1071062 писал(а):
22 способа. Вычислено полным перебором.

Странно, что для 9 решений больше - 24.

slavav в сообщении #1071085 писал(а):
$10!$ - не большое число.

А это уже перебор :-) - gris подсказал алгоритм.

-- 07.11.2015, 19:39 --

gris в сообщении #1070954 писал(а):
надо попробовать решить для меньших чисел

У Вас ошибка для 5 только...

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 19:49 
Заслуженный участник


26/05/14
981
Geen в сообщении #1071101 писал(а):
[quote="slavav в А это уже перебор :-) - gris подсказал алгоритм.


Подсказанный алгоритм можно использовать для ограничения перебора. Зато для полного перебора можно использовать готовые инструменты, то есть написать программу за несколько минут.

c( 1 ) = 1
c( 2 ) = 1
c( 3 ) = 2
c( 4 ) = 2
c( 5 ) = 4
c( 6 ) = 5
c( 7 ) = 7
c( 8 ) = 7
c( 9 ) = 24
c( 10 ) = 22
c( 11 ) = 29
c( 12 ) = 39

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 19:54 
Заслуженный участник
Аватара пользователя


01/09/13
4318
slavav в сообщении #1071106 писал(а):
Зато для полного перебора можно использовать готовые инструменты, то есть написать программу за несколько минут.

Так она и так за несколько минут пишется...
Сейчас, для $n=20$ подсчитает, выложу результат

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


13/08/08
14430
Я вначале подумал, что из каких-нибудь соображений делимости, простоты и т.п. требуемая комбинация невозможна. Потом попробовал на маленьких числах. Потом подумал, что если уж есть перестановки, то искать теоретически их число дело муторное и написал прямейший, тупейший, неэффективнейший скрипт, который и выдал <вовсе не случайное> число нужных перестановок :-) .

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 20:31 
Заслуженный участник


26/05/14
981
Перебор с ограничением:
c( 1 ) = 1
c( 2 ) = 1
c( 3 ) = 2
c( 4 ) = 2
c( 5 ) = 4
c( 6 ) = 5
c( 7 ) = 7
c( 8 ) = 7
c( 9 ) = 24
c( 10 ) = 22
c( 11 ) = 29
c( 12 ) = 39
c( 13 ) = 67
c( 14 ) = 55
c( 15 ) = 386
c( 16 ) = 235
c( 17 ) = 312
c( 18 ) = 347
c( 19 ) = 451
c( 20 ) = 1319
c( 21 ) = 5320
c( 22 ) = 3220
c( 23 ) = 4489
c( 24 ) = 20237

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 21:16 
Заслуженный участник
Аватара пользователя


01/09/13
4318
до 25:
1 1 2 2 4 5 7 7 24 22 29 39 67 55 386 235 312 347 451 1319 5320 3220 4489 20237 36580

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 21:34 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Посмотрел в OEIS и увидел там эту последовательность :!:

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 21:38 
Заслуженный участник


26/05/14
981
c( 26 ) = 52875

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 21:40 
Заслуженный участник
Аватара пользователя


01/09/13
4318
gris в сообщении #1071140 писал(а):
Посмотрел в OEIS и увидел там эту последовательность :!:

Блин, всё украдено до нас :lol:

 Профиль  
                  
 
 Re: Десять чисел в ряд
Сообщение07.11.2015, 21:50 
Заслуженный участник


26/05/14
981
slavav в сообщении #1071142 писал(а):
c( 26 ) = 52875

(Оффтоп)

Клянусь обновлять форум перед отправкой сообщения!

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

Модератор: Модераторы



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

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


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

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