Конструктивы в комбигео
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На координатной плоскости в некоторых точках с целыми координатами лежит по камешку (камешков конечное количество). Разрешается
делать следующий ход: выбрать пару камешков, взять некоторый вектор 
с целыми координатами, и далее один из
выбранных камешков сдвинуть на вектор 
а другой — на противоположный вектор 
При этом запрещается
класть два камушка в одну точку. Всегда ли можно за несколько ходов добиться того, чтобы все камешки лежали на одной
прямой?
Источники:
Подсказка 1
Попробуйте ввести центр масс всех камешков. Подумайте, как он может помочь в решении задачи.
Подсказка 2
Действительно, операция, описанная в условии задачи, не будет изменять положение центра тяжести. Тогда попробуйте провести такую прямую через центр тяжести, чтобы она охватывала бесконечно много точек с целыми координатами, куда мы сможем складывать камешки.
Подсказка 3
Обозначим координаты центра тяжести (x₀, y₀). Тогда нам почти всегда подойдет прямая y₀x = x₀y, кроме одного случая. Подумайте, какого.
Подсказка 4
Да, для случая (x₀, y₀) = (0, 0) нужна другая прямая, например, y = 0. Подумайте, какие ходы необходимо делать, чтобы все камни в итоге легли на нашу прямую.
Подсказка 5
Попробуйте поочередно попарно двигать камни 1 и n, 2 и n, 3 и n, ..., n-1 и n. Если мы положили первые n-1 камешков на нашу прямую (а мы можем так сделать, потому что у нее бесконечное количество точек с целыми координатами), то почему n-й камешек окажется на прямой? Вспомните про центр тяжести.
Пусть начальные координаты камешков это
и пусть координаты их центра масс
Рассмотрим прямую 
проходящую через точку 
на которой лежит бесконечное количество узлов (то есть точек с целыми
координатами). Такая прямая 
найдется.
Действительно, если 
то годится прямая
На ней лежат узлы вида 
где 
Если же 
то подойдет прямая
Сделаем ход с 
-м и 
-м камешками так, чтобы 
-й камешек попал в некоторый незанятый узел прямой 
Отметим, что такой ход
можно сделать: если 
-й камешек попал в узел 
то 
-й камешек попадет в узел 
симметричный 
относительно середины отрезка
между положениями 
-го и 
-го камней до хода; так как возможностей выбора узла 
бесконечно много, то для какого-то из них
соответствующий узел 
будет незанятым. Сделаем аналогичные ходы со 
-м и 
-м камешками, с 
-м и 
-м камешками, и так далее,
с 
-м и 
-м камешками.
Теперь все камни, кроме возможно 
-го, лежат на прямой 
Но заметим, что в процессе выполнения ходов центр масс камней
остается неизменным, и он лежит на прямой 
(согласно нашему выбору 
Но отсюда следует, что и оставшийся 
-й камень
также лежит на 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
