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
14495
Сумма всех чисел 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
4683
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
4683
slavav в сообщении #1071106 писал(а):
Зато для полного перебора можно использовать готовые инструменты, то есть написать программу за несколько минут.

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

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


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

 Профиль  
                  
 
 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
4683
до 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
14495
Посмотрел в OEIS и увидел там эту последовательность :!:

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


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

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


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

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

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


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

(Оффтоп)

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

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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