Страница 1 из 1

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

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

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. Существует?

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

Добавлено: 24 мар 2017, 14:06
team55
вроде можно?
0, 2, 6, 12, 20, 30, 42, 56, 72, 90...

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

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

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

Добавлено: 24 мар 2017, 23:03
team55
Почитал твоё доказательство. Согласен, я ошибся.

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

Добавлено: 27 мар 2017, 09:53
Юляша
Выполнен перебор с компьютерной поддержкой. Получилось, что для 6 точек и дуги 30 решения вроде как тоже не существует.
Хорошо бы, чтобы кто-нибудь попытался подтвердить независимо.

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

Добавлено: 28 мар 2017, 18:17
Инна
Для окружности длины 91 решение есть.

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

Добавлено: 28 мар 2017, 19:00
Инна
Конечно же, Юляшино решение правильное.