Решение задач на расстояния между точками на прямой

Задание 6

Условие:

Ира отметила на прямой несколько точек. Оказалось, что все расстояния между точками принимают чётные значения. Кроме того, не менее пяти расстояний между отмеченными точками делятся на 9 без остатка.

Вопросы:

1. Какое наименьшее количество точек могла отметить Ира?
2. Какое наименьшее расстояние могло быть между самыми далёкими точками (точек не обязательно наименьшее количество)?

Решение:

Пусть отмеченные точки имеют координаты \(x_1, x_2, \dots, x_n\) на прямой, где \(n\) — количество точек. Без потери общности, предположим, что точки расположены в порядке возрастания: \(x_1 < x_2 < \dots < x_n\).

Все расстояния между точками — это \(|x_i - x_j|\) для \(i \neq j\).

1. Наименьшее количество точек:

• Условие 1: Все расстояния между точками — чётные числа.
  Это означает, что все отмеченные точки должны иметь одинаковую чётность. То есть, все они должны быть чётными или все нечётными. Если бы были точки разной чётности, то расстояние между ними было бы нечётным.
  Например, если \(x_1\) — чётное, а \(x_2\) — нечётное, то \(x_2 - x_1\) — нечётное.
  Значит, все \(x_i\) имеют одинаковую чётность.

• Условие 2: Не менее пяти расстояний между отмеченными точками делятся на 9 без остатка.
  Расстояния, делящиеся на 9, — это \(|x_i - x_j|\), где \(|x_i - x_j|\) кратно 9.

Рассмотрим наименьшее возможное количество точек.

• Если точек 2: \(x_1, x_2\). Расстояние \(|x_2 - x_1|\). Может быть только одно расстояние. Условие "не менее пяти расстояний" не выполняется.
• Если точек 3: \(x_1, x_2, x_3\). Расстояния: \(|x_2 - x_1|\), \(|x_3 - x_2|\), \(|x_3 - x_1|\). Всего 3 расстояния. Условие "не менее пяти расстояний" не выполняется.
• Если точек 4: \(x_1, x_2, x_3, x_4\). Расстояния: \(|x_2 - x_1|\), \(|x_3 - x_2|\), \(|x_4 - x_3|\), \(|x_3 - x_1|\), \(|x_4 - x_2|\), \(|x_4 - x_1|\). Всего 6 расстояний. Это уже возможно.

Теперь нужно удовлетворить обоим условиям.
Пусть все точки имеют одинаковую чётность.
Пусть расстояния, делящиеся на 9, будут: \(d_1, d_2, d_3, d_4, d_5\).
Эти расстояния могут быть как между соседними точками, так и между любыми двумя точками.

Рассмотрим случай с 4 точками: \(x_1, x_2, x_3, x_4\).
Расстояния: \(x_2-x_1\), \(x_3-x_2\), \(x_4-x_3\), \(x_3-x_1\), \(x_4-x_2\), \(x_4-x_1\).
Если мы хотим, чтобы не менее пяти расстояний делились на 9, то 4 точки может быть недостаточно, если не удастся подобрать такие координаты, чтобы 5 из 6 расстояний делились на 9.

Рассмотрим 5 точек: \(x_1, x_2, x_3, x_4, x_5\).
Количество расстояний: \(\binom{5}{2} = \frac{5 \times 4}{2} = 10\).
Из них не менее 5 должны делиться на 9.

Пусть все точки имеют одинаковую чётность.
Пусть расстояния между соседними точками будут кратны 18 (чтобы они были чётными и делились на 9).
Например, \(x_2 - x_1 = 18a_1\), \(x_3 - x_2 = 18a_2\), \(x_4 - x_3 = 18a_3\), \(x_5 - x_4 = 18a_4\).
Тогда расстояния между любыми двумя точками будут:
\(x_3 - x_1 = 18(a_1 + a_2)\)
\(x_4 - x_1 = 18(a_1 + a_2 + a_3)\)
\(x_5 - x_1 = 18(a_1 + a_2 + a_3 + a_4)\)
\(x_4 - x_2 = 18(a_2 + a_3)\)
\(x_5 - x_2 = 18(a_2 + a_3 + a_4)\)
\(x_5 - x_3 = 18(a_3 + a_4)\)

Все эти расстояния будут чётными и кратными 9.
Нам нужно, чтобы не менее пяти расстояний делились на 9.
Если мы выберем \(a_1=a_2=a_3=a_4=1\), то расстояния между соседними точками будут 18.
\(x_1 = 0\)
\(x_2 = 18\)
\(x_3 = 36\)
\(x_4 = 54\)
\(x_5 = 72\)

Расстояния:
\(x_2-x_1 = 18\)
\(x_3-x_2 = 18\)
\(x_4-x_3 = 18\)
\(x_5-x_4 = 18\)
\(x_3-x_1 = 36\)
\(x_4-x_2 = 36\)
\(x_5-x_3 = 36\)
\(x_4-x_1 = 54\)
\(x_5-x_2 = 54\)
\(x_5-x_1 = 72\)

Все эти 10 расстояний чётные и делятся на 9. Условие "не менее пяти" выполнено.
Таким образом, 5 точек достаточно.

Может ли быть меньше 5 точек?
Мы рассмотрели 4 точки. Количество расстояний — 6.
Пусть \(x_1=0, x_2=18, x_3=36, x_4=54\).
Расстояния: 18, 18, 18, 36, 36, 54. Все 6 расстояний чётные и делятся на 9.
Значит, 4 точки тоже подходят.

Может ли быть 3 точки?
\(x_1, x_2, x_3\). Расстояния: \(x_2-x_1\), \(x_3-x_2\), \(x_3-x_1\). Всего 3 расстояния. Условие "не менее пяти" не выполнено.

Значит, наименьшее количество точек — 4.

Ответ на 1-й вопрос: 4.

2. Наименьшее расстояние между самыми далёкими точками:

Мы нашли, что 4 точки достаточны. Пусть эти точки будут \(x_1, x_2, x_3, x_4\).
Расстояние между самыми далёкими точками — это \(|x_4 - x_1|\).
Мы хотим минимизировать это расстояние, при этом выполняя условия:
1. Все расстояния \(|x_i - x_j|\) чётные. (Значит, все \(x_i\) имеют одинаковую чётность.)
2. Не менее пяти расстояний \(|x_i - x_j|\) делятся на 9.

Рассмотрим 4 точки. У нас 6 расстояний.
Для выполнения условия 2, нам нужно, чтобы 5 из 6 расстояний делились на 9.
Пусть \(x_1=0\).
Тогда \(x_2, x_3, x_4\) должны быть такими, чтобы:
\(x_2\), \(x_3\), \(x_4\) — все чётные (или все нечётные).
\(x_2-x_1 = x_2\)
\(x_3-x_1 = x_3\)
\(x_4-x_1 = x_4\)
\(x_3-x_2\)
\(x_4-x_2\)
\(x_4-x_3\)

Пять из этих шести должны делиться на 9.
Если \(x_2, x_3, x_4\) делятся на 9, то:
\(x_2 = 9k_2\), \(x_3 = 9k_3\), \(x_4 = 9k_4\).
Так как они должны быть чётными, то \(k_2, k_3, k_4\) должны быть чётными.
Пусть \(k_2=2m_2, k_3=2m_3, k_4=2m_4\).
Тогда \(x_2 = 18m_2\), \(x_3 = 18m_3\), \(x_4 = 18m_4\).
Пусть \(m_2=1, m_3=2, m_4=3\) (для минимальности и различия).
\(x_1 = 0\)
\(x_2 = 18\)
\(x_3 = 36\)
\(x_4 = 54\)
Расстояния:
\(x_2-x_1 = 18\) (делится на 9)
\(x_3-x_1 = 36\) (делится на 9)
\(x_4-x_1 = 54\) (делится на 9)
\(x_3-x_2 = 18\) (делится на 9)
\(x_4-x_2 = 36\) (делится на 9)
\(x_4-x_3 = 18\) (делится на 9)
Все 6 расстояний делятся на 9. И все они чётные.
В этом случае расстояние между самыми далёкими точками (\(x_4 - x_1\)) равно 54.

Можно ли найти меньшее расстояние?
Нам нужно, чтобы 5 из 6 расстояний делились на 9.
Пусть \(x_1=0\).
\(x_2, x_3, x_4\) — все чётные.
Пусть \(x_2 = a, x_3 = b, x_4 = c\).
Расстояния: \(a, b, c, b-a, c-a, c-b\).
Пять из них должны делиться на 9.

Рассмотрим случай, когда расстояние между крайними точками минимально.
Пусть \(x_1 = 0\).
Тогда \(x_4\) должно быть минимальным чётным числом, кратным 9.
Минимальное чётное число, кратное 9, это 18.
Если \(x_4 = 18\).
Точки: \(0, x_2, x_3, 18\).
Все \(x_i\) должны быть чётными.
Расстояния: \(x_2, x_3, 18, x_3-x_2, 18-x_2, 18-x_3\).
Пять из них должны делиться на 9.
\(18\) делится на 9.
Значит, 4 других расстояния из \(x_2, x_3, x_3-x_2, 18-x_2, 18-x_3\) должны делиться на 9.

Пусть \(x_2 = 9\). Но \(x_2\) должно быть чётным. Значит, \(x_2\) не может быть 9.
Если \(x_2\) чётное, то \(x_2\) не может делиться на 9, если оно не делится на 18.
Пусть \(x_2 = 6\). (Чётное)
\(x_3\) — чётное.
Расстояния: 6, \(x_3\), 18, \(x_3-6\), \(18-6=12\), \(18-x_3\).
\(18\) делится на 9.
Нам нужно, чтобы 4 из \(6, x_3, x_3-6, 18-x_2, 18-x_3\) делились на 9.

Рассмотрим вариант, когда точки расположены так, что расстояния между ними кратны 9.
Пусть \(x_1=0\).
\(x_2 = 9k_2\), \(x_3 = 9k_3\), \(x_4 = 9k_4\).
Все \(x_i\) должны быть чётными. Значит, \(k_i\) должны быть чётными.
\(x_2 = 18m_2\), \(x_3 = 18m_3\), \(x_4 = 18m_4\).
Минимальные различные положительные значения: \(m_2=1, m_3=2, m_4=3\).
\(x_1=0, x_2=18, x_3=36, x_4=54\).
Расстояние между самыми далёкими точками: \(x_4 - x_1 = 54\).
Все 6 расстояний делятся на 9.

Что если не все расстояния между соседними точками делятся на 9?
Пусть \(x_1=0\).
\(x_2, x_3, x_4\) — чётные.
Пять расстояний делятся на 9.
Рассмотрим случай, когда \(x_4-x_1\) минимально.
\(x_4-x_1\) должно быть чётным.
Если \(x_4-x_1 = 18\).
Точки: \(0, x_2, x_3, 18\).
\(x_2, x_3\) — чётные, \(0 < x_2 < x_3 < 18\).
Расстояния: \(x_2, x_3, 18, x_3-x_2, 18-x_2, 18-x_3\).
\(18\) делится на 9.
Нужно, чтобы 4 из \(x_2, x_3, x_3-x_2, 18-x_2, 18-x_3\) делились на 9.
Все эти числа должны быть чётными.
\(x_2\) — чётное. Если \(x_2\) делится на 9, то \(x_2\) должно быть кратно 18. Но \(0 < x_2 < 18\). Невозможно.
Значит, \(x_2\) не делится на 9.
\(x_3\) — чётное. Если \(x_3\) делится на 9, то \(x_3\) должно быть кратно 18. Но \(0 < x_3 < 18\). Невозможно.
Значит, \(x_3\) не делится на 9.
\(x_3-x_2\) — чётное.
\(18-x_2\) — чётное.
\(18-x_3\) — чётное.

Тогда три расстояния, которые должны делиться на 9: \(x_3-x_2\), \(18-x_2\), \(18-x_3\).
Возможно ли, чтобы три чётных числа делились на 9?
Если \(a\) делится на 9, то \(a = 9k\). Если \(a\) чётное, то \(k\) должно быть чётным, \(k=2m\), \(a=18m\).
Значит, \(x_3-x_2\), \(18-x_2\), \(18-x_3\) должны быть кратны 18.
\(18-x_2 = 18m_1 \implies x_2 = 18(1-m_1)\). Так как \(x_2 > 0\), то \(m_1=0\), \(x_2=0\), но \(x_2>0\). Или \(m_1 < 1\).
Если \(m_1=0\), то \(x_2=18\), но \(x_2<18\).
Если \(x_2\) чётное, \(0 < x_2 < 18\), то \(x_2\) может быть 2, 4, 6, 8, 10, 12, 14, 16.
\(18-x_2\) будет: 16, 14, 12, 10, 8, 6, 4, 2. Ни одно не делится на 9.

Значит, \(x_4-x_1\) не может быть 18.
Попробуем \(x_4-x_1 = 36\).
Точки: \(0, x_2, x_3, 36\).
\(x_2, x_3\) — чётные, \(0 < x_2 < x_3 < 36\).
Расстояния: \(x_2, x_3, 36, x_3-x_2, 36-x_2, 36-x_3\).
\(36\) делится на 9.
Нужно, чтобы 4 из \(x_2, x_3, x_3-x_2, 36-x_2, 36-x_3\) делились на 9.
Все эти числа чётные. Значит, они должны быть кратны 18.
\(x_2\) должно быть кратно 18. Так как \(0 < x_2 < 36\), то \(x_2=18\).
\(x_3\) должно быть кратно 18. Так как \(18 < x_3 < 36\), то \(x_3\) не может быть кратно 18.
Значит, \(x_3\) не делится на 9.

Давайте вернемся к первому случаю, который мы нашли:
\(x_1=0, x_2=18, x_3=36, x_4=54\).
Расстояние между самыми далёкими точками = 54.
Все 6 расстояний делятся на 9, и все они чётные.

Рассмотрим случай с 5 точками.
\(x_1, x_2, x_3, x_4, x_5\).
\(x_1=0\).
\(x_2=18, x_3=36, x_4=54, x_5=72\).
Расстояние между самыми далёкими точками = 72.
Все 10 расстояний делятся на 9 и чётные.

Если мы хотим минимизировать расстояние между самыми далёкими точками, то нам нужно найти наименьшее \(x_n - x_1\), при котором условия выполняются.
Мы знаем, что 4 точки достаточны.
Минимальное расстояние между крайними точками равно \(x_4 - x_1\).
Мы нашли пример: \(x_1=0, x_2=18, x_3=36, x_4=54\). Расстояние = 54.

Можно ли сделать расстояние меньше 54?
Пусть \(x_4-x_1 = D\). \(D\) должно быть чётным.
Пять расстояний должны делиться на 9.

Если \(D=36\).
\(x_1=0, x_4=36\).
\(x_2, x_3\) — чётные, \(0 < x_2 < x_3 < 36\).
Расстояния: \(x_2, x_3, 36, x_3-x_2, 36-x_2, 36-x_3\).
\(36\) делится на 9.
Нужно, чтобы 4 из \(x_2, x_3, x_3-x_2, 36-x_2, 36-x_3\) делились на 9.
Эти 4 числа должны быть кратны 18.
\(x_2\) кратно 18. \(x_2=18\).
\(x_3\) кратно 18. \(x_3\) должно быть между 18 и 36. Невозможно.
Значит, \(D\) не может быть 36.

Следующее чётное число, кратное 9, это 54.
Если \(D=54\).
\(x_1=0, x_4=54\).
\(x_2, x_3\) — чётные, \(0 < x_2 < x_3 < 54\).
Расстояния: \(x_2, x_3, 54, x_3-x_2, 54-x_2, 54-x_3\).
\(54\) делится на 9.
Нужно, чтобы 4 из \(x_2, x_3, x_3-x_2, 54-x_2, 54-x_3\) делились на 9.
Эти 4 числа должны быть кратны 18.
\(x_2\) кратно 18. \(x_2\) может быть 18 или 36.
\(x_3\) кратно 18. \(x_3\) может быть 18 или 36.
\(x_3-x_2\) кратно 18.
\(54-x_2\) кратно 18.
\(54-x_3\) кратно 18.

Случай 1: \(x_2=18\).
Тогда \(54-x_2 = 54-18 = 36\), кратно 18.
Остаются: \(x_3, x_3-18, 54-x_3\). Нужно, чтобы два из них делились на 9.
\(x_3\) должно быть кратно 18. \(18 < x_3 < 54\). \(x_3=36\).
Проверим:
\(x_1=0, x_2=18, x_3=36, x_4=54\).
Расстояния:
\(x_2-x_1 = 18\) (делится на 9)
\(x_3-x_1 = 36\) (делится на 9)
\(x_4-x_1 = 54\) (делится на 9)
\(x_3-x_2 = 36-18 = 18\) (делится на 9)
\(x_4-x_2 = 54-18 = 36\) (делится на 9)
\(x_4-x_3 = 54-36 = 18\) (делится на 9)
Все 6 расстояний делятся на 9. И все они чётные.
Расстояние между самыми далёкими точками = 54.

Ответ на 2-й вопрос: 54.

Итоговые ответы:
1. Наименьшее количество точек: 4
2. Наименьшее расстояние между самыми далёкими точками: 54