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

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

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

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

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

Сообщение Инна »

Расстояния на окружности
Дана окружность длины 90. Можно ли отметить на ней 10 точек так, чтобы среди дуг с концами в этих точках имелись дуги со всеми целочисленными длинами от 1 до 89?
(Олимпиада Эйлера, 2017, 2 день, номер 7)
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

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

Сообщение Юляша »

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

--- скрыто
Разметим на окружности 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. Существует?
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
team55
Популярный автор
Популярный автор
Сообщения: 1086
Зарегистрирован: 18 апр 2006, 16:49

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

Сообщение team55 »

вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

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

Сообщение Юляша »

team55 писал(а):вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...
Что это за последовательность? Удвоенные треугольные числа, для которых потенциально хватает точек? Но это не гарантирует, что решение для конкретного числа существует.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
team55
Популярный автор
Популярный автор
Сообщения: 1086
Зарегистрирован: 18 апр 2006, 16:49

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

Сообщение team55 »

Почитал твоё доказательство. Согласен, я ошибся.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

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

Сообщение Юляша »

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

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

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

Сообщение Инна »

Для окружности длины 91 решение есть.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

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

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

Сообщение Инна »

Конечно же, Юляшино решение правильное.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Ответить

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