2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 15:42 
Аватара пользователя


01/12/11

8634
Можно ли написать по кругу 8 различных целых положительных чисел, не превосходящих 25, если требуется, чтобы любые два соседних числа отличались на 5 или 7? Приведите пример или докажите, что это невозможно.

У меня получилось так: 25, 20, 13, 8, 1, 6, 11, 18, круг замкнулся.

Напрашивается вопрос, обязательно ли использовать число 25?
Иными словами, можно ли написать по кругу 8 различных целых положительных чисел, не превосходящих 24, если требуется, чтобы любые два соседних числа отличались на 5 или 7?

Оказывается, и это можно: 20, 13, 6, 1, 8, 3, 10, 15, круг замкнулся.

А вот можно ли, чтобы все числа не превосходили 19?
У меня, почему-то, не получается.

Пожалуйста, помогите решить.
Заранее благодарю.

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 17:43 
Заслуженный участник


12/09/10
1547
Компьютер утверждает, что нельзя.

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 17:51 
Аватара пользователя


01/12/11

8634
Cash
Спасибо, конечно, но можно ли решить вручную?

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 17:55 
Заслуженный участник


12/09/10
1547
А смысл?

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 18:06 
Заслуженный участник


20/08/14
11060
Россия, Москва
Смысл разве лишь в том чтобы выявить взаимосвязь количества чисел и множества допустимых разностей. Т.е. решить задачу в максимально общем виде. :D

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 18:56 
Заслуженный участник


03/01/09
1677
москва
А такой вариант: 19,14, 7, 12, 5, 10, 17, 12.

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 18:57 
Заслуженный участник
Аватара пользователя


09/09/14
6328
mihiv в сообщении #1184062 писал(а):
12, [...] ,12

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 19:03 
Заслуженный участник


03/01/09
1677
москва
А, точно, должны быть все различные.

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 19:27 
Аватара пользователя


26/09/16
198
Снегири
Очевидно, нельзя.
Только, чтобы разобраться, почему, придётся перебрать варианты. Благо, не так уж их и много.

Сначала для простоты примем одно из чисел - а именно, минимальное - равным единице. Логично, что если среди чисел в кольце все будут больше, то всегда можно вычесть из всех восьми чисел столько, чтобы минимальное было равно единице, и тогда мы сможем уменьшить максимальное значение.
Очевидно, так как наше выбранное число минимально, то соседние будут больше на пять и семь соответственно. То есть, где-то в центре нашего кольца есть основа:
$..., 6, 1, 8, ...$
Из шестёрки мы не можем вычесть ни пять (потому что все числа должны быть разными), ни семь (потому что минимальное по условию у нас уже есть). Значит, слева от неё может быть только два числа: либо 11, либо 13. Справа от восьмёрки может быть уже три числа: 3, 13 или 15. Справа от тройки может стоять только 10. Потому что вычитать из неё уже нечего, а слева уже стоит 8. Думаю, надо всё это записать, пока не забыл. Какое бы ни было кольцо, у него в центре может быть всего лишь пять вариантов центра:
а) $..., 11, 6, 1, 8, 3, 10, ...$
б) $..., 11, 6, 1, 8, 13, ...$
в) $..., 11, 6, 1, 8, 15, ...$
г) $..., 13, 6, 1, 8, 3, 10, ...$
д) $..., 13, 6, 1, 8, 15, ...$

Казалось бы, вариантов уже довольно много, а если мы пойдём дальше, так станет ещё больше. Но на самом деле, нет. Теперь всё только упростится.

Слева от 11 может стоять только 4 или 18.
Слева от 13 - только 18 или 20. Справа от 13, кстати, тоже.
Справа от 15 - больше всего вариантов: 10, 20 и 22.

$|10-4| = 6; |10-18| = 8; |10-20| = 10$. То есть, для основы (а) невозможно добавить в кольцо такое число, чтобы оно сошлось. А для основы (г) такое число есть: $20, 13, 6, 1, 8, 3, 10, 15$.

Я вначале хотел переписать всё словами, но давайте для наглядности запишу оставшиеся варианты:

б1) $..., 4, 11, 6, 1, 8, 13, ...$
б2) $..., 18, 11, 6, 1, 8, 13, ...$
в1) $..., 4, 11, 6, 1, 8, 15, ...$
в2) $..., 18, 11, 6, 1, 8, 15, ...$
д1) $..., 18, 13, 6, 1, 8, 15, ...$
д2) $..., 20, 13, 6, 1, 8, 15, ...$

Числа справа не пишу, чтобы не занимать место и не тратить время, тем более что они указаны сверху.
Слева от четвёрки можно поставить только девятку, но между девяткой и 13, равно как между 9 и 15, нельзя поставить никакое число. (б1) и (в1) сразу выбрасываются.

$|18-20| = 2; |22-20| = 2; |10-20| = 10$. Между этими тремя парами можно поставить такие числа, которые бы объединили кольцо: 25 или 13, 27 или 15, а также 15 соответственно. Выбрасывая 13 и 15 из тех групп, где они уже есть, получаем весьма ограниченное количество вариантов.

Подводим итог. При условии, что числа могут различаться только на 5 или на 7, есть только пять вариантов минимальных колец:
(г) $20, 13, 6, 1, 8, 3, 10, 15$
(б2) $25, 18, 11, 6, 1, 8, 13, 20$
(в2) $25, 18, 11, 6, 1, 8, 15, 20$
(д1) $25, 18, 13, 6, 1, 8, 15, 20$
(д2) $27, 20, 13, 6, 1, 8, 15, 22$

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

Остаётся два вопроса.
1) Насколько лень кому бы то ни было будет расписывать эти наборы для общего случая кольца из $N$ элементов, различающихся на $x_{1}$ и $x_{2}$, и
2) откуда вы берёте такие вопросы.

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 19:59 
Заслуженный участник


12/09/10
1547
SVD-d в сообщении #1184082 писал(а):
Подводим итог. При условии, что числа могут различаться только на 5 или на 7, есть только пять вариантов минимальных колец:


Что скажете, например, про это:
$1, 6, 11, 18, 13, 20, 15, 8, 1$

(Оффтоп)

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

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 21:05 
Заслуженный участник
Аватара пользователя


09/09/14
6328
SVD-d в сообщении #1184082 писал(а):
есть только пять вариантов минимальных колец
Вариантов есть ровно столько же, сколько есть способов записать строку длины 8 из чисел $\{5;-5;7;-7\}$ так, чтобы в ней сумма подряд идущих чисел обнулялась только для всей строки (и ни для какой подстроки), а положительных пятёрок (соответственно, семёрок) было бы столько же, сколько и отрицательных. Строки, которые можно получить друг из друга циклическими перестановками, считаются эквивалентными. (Зеркальные тоже эквивалентны, наверное?)

Например, для строки $\{-5;-5;-5;7;5;5;5;-7\}$ получим не упоминавшееся ранее кольцо:
$23,16,11,6,1,8,13,18,23$

Это на уровне идеи, но я уверен, что подобная комбинаторная задача вполне по силам ТС, который пока не предъявил никаких попыток решения :D

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 21:30 
Заслуженный участник


27/04/09
28128
grizzly в сообщении #1184134 писал(а):
а положительных пятёрок (соответственно, семёрок) было бы столько же, сколько и отрицательных
А зачем это ограничение, если уже есть ограничение на обнуление всей суммы? Для других параметров оно может и не следовать из этого. Скажем, $(-5,1,1,1,1,1)$ для 6 чисел и модулей разностей $\{1,5\}$.

 Профиль  
                  
 
 Re: Можно ли написать по кругу 8 чисел...?
Сообщение12.01.2017, 21:35 
Заслуженный участник
Аватара пользователя


09/09/14
6328
arseniiv в сообщении #1184146 писал(а):
А зачем это ограничение, если уже есть ограничение на обнуление всей суммы?Для других параметров оно может и не следовать из этого.

Да, конечно. Я это видел сперва, а потом отвлёкся на частности.

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

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



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

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


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

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