Расстояния на окружности
Дана окружность длины 90. Можно ли отметить на ней 10 точек так, чтобы среди дуг с концами в этих точках имелись дуги со всеми целочисленными длинами от 1 до 89?
(Олимпиада Эйлера, 2017, 2 день, номер 7)
Расстояния на окружности
Модераторы: Азарапетыч, Администрация
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Расстояния на окружности
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
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. Существует?
--- скрыто
Разметим на окружности 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. Существует?
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Расстояния на окружности
вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...
Re: Расстояния на окружности
Что это за последовательность? Удвоенные треугольные числа, для которых потенциально хватает точек? Но это не гарантирует, что решение для конкретного числа существует.team55 писал(а):вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Расстояния на окружности
Почитал твоё доказательство. Согласен, я ошибся.
Re: Расстояния на окружности
Выполнен перебор с компьютерной поддержкой. Получилось, что для 6 точек и дуги 30 решения вроде как тоже не существует.
Хорошо бы, чтобы кто-нибудь попытался подтвердить независимо.
Хорошо бы, чтобы кто-нибудь попытался подтвердить независимо.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Расстояния на окружности
Для окружности длины 91 решение есть.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Расстояния на окружности
Конечно же, Юляшино решение правильное.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...