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