Расстояния на окружности

Логические задачи

Модераторы: Азарапетыч, Администрация

Расстояния на окружности

Сообщение Инна » 23 мар 2017, 22:38

Расстояния на окружности
Дана окружность длины 90. Можно ли отметить на ней 10 точек так, чтобы среди дуг с концами в этих точках имелись дуги со всеми целочисленными длинами от 1 до 89?
(Олимпиада Эйлера, 2017, 2 день, номер 7)
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

Re: Расстояния на окружности

Сообщение Юляша » 24 мар 2017, 10:26

Вроде получается довольно простое доказательство, что нельзя.

--- скрыто
Разметим на окружности 90 базовых точек через единичные дуги. Без ограничения общности можно считать, что все отмеченные точки совпадают с базовыми. Пронумеруем базовые точки от 0 до 89.

Каждая пара базовых точек создает две дуги - "короткую" и "длинную". Итого, получаем 10*9*2/2=90 дуг. Из них две дуги имеют длину 45, остальные должны иметь уникальные значения от 1 до 89.
Таким образом, получаем 44 дуги четной длины и 46 дуг нечетной длины.
Пусть Х точек имеют четную базовую координату и Y точек - нечетную базовую координату. Тогда число дуг нечетной длины равно 2*X*Y.

Система уравнений X+Y=10, 2*X*Y=46 не имеет натуральных решений, а значит требуемое построение невозможно.

--- конец скрытого

Согласно этому доказательству при меньшем числе точек, может существовать решение для 3 точек и дуги 6 (существует и получается автоматически) и для 6 точек и дуги 30. Существует?
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3161
Зарегистрирован: 15 янв 2009, 12:32

Re: Расстояния на окружности

Сообщение team55 » 24 мар 2017, 14:06

вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...
Аватара пользователя
team55
Графоман со стажем
Графоман со стажем
 
Сообщения: 719
Зарегистрирован: 18 апр 2006, 16:49

Re: Расстояния на окружности

Сообщение Юляша » 24 мар 2017, 17:26

team55 писал(а):вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...


Что это за последовательность? Удвоенные треугольные числа, для которых потенциально хватает точек? Но это не гарантирует, что решение для конкретного числа существует.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3161
Зарегистрирован: 15 янв 2009, 12:32

Re: Расстояния на окружности

Сообщение team55 » 24 мар 2017, 23:03

Почитал твоё доказательство. Согласен, я ошибся.
Аватара пользователя
team55
Графоман со стажем
Графоман со стажем
 
Сообщения: 719
Зарегистрирован: 18 апр 2006, 16:49

Re: Расстояния на окружности

Сообщение Юляша » 27 мар 2017, 09:53

Выполнен перебор с компьютерной поддержкой. Получилось, что для 6 точек и дуги 30 решения вроде как тоже не существует.
Хорошо бы, чтобы кто-нибудь попытался подтвердить независимо.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3161
Зарегистрирован: 15 янв 2009, 12:32

Re: Расстояния на окружности

Сообщение Инна » 28 мар 2017, 18:17

Для окружности длины 91 решение есть.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

Re: Расстояния на окружности

Сообщение Инна » 28 мар 2017, 19:00

Конечно же, Юляшино решение правильное.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния


Вернуться в Задачки

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

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

cron