Задача 4.2. В волшебном саду растёт бесконечное число деревьев. Каждому дереву садовник приписал пару натуральных чисел: высоту и толщину ствола. При этом любые два дерева отличаются хотя бы по одному из этих параметров. Докажите, что в саду найдутся два дерева, одно из которых не ниже и не тоньше другого.

Решение:

Рассмотрим пары натуральных чисел, соответствующие каждому дереву: \( (h, t) \), где \( h \) — высота, а \( t \) — толщина ствола.

Условие задачи гласит, что любые два дерева отличаются хотя бы по одному из этих параметров. Это означает, что для любых двух деревьев с параметрами \( (h_1, t_1) \) и \( (h_2, t_2) \) верно, что \( h_1 \neq h_2 \) или \( t_1 \neq t_2 \).

Мы хотим доказать, что найдутся два дерева, одно из которых не ниже и не тоньше другого. Это значит, мы хотим найти два дерева с параметрами \( (h_1, t_1) \) и \( (h_2, t_2) \) такие, что \( h_1 \leq h_2 \) и \( t_1 \leq t_2 \), причём хотя бы одно из неравенств строгое (т.е. \( h_1 < h_2 \) или \( t_1 < t_2 \)), чтобы они не были идентичными.

Предположим противное: что не существует такой пары деревьев. Это означает, что для любых двух деревьев \( (h_1, t_1) \) и \( (h_2, t_2) \), если \( h_1 ≤ h_2 \), то обязательно \( t_1 > t_2 \). И наоборот, если \( t_1 ≤ t_2 \), то обязательно \( h_1 > h_2 \).

Рассмотрим два дерева A и B с параметрами \( (h_A, t_A) \) и \( (h_B, t_B) \).

Случай 1: \( h_A = h_B \). По условию, деревья должны отличаться хотя бы по одному параметру, значит \( t_A \neq t_B \). Пусть \( t_A < t_B \). Тогда дерево B не ниже и не тоньше дерева A.

Случай 2: \( t_A = t_B \). По условию, деревья должны отличаться хотя бы по одному параметру, значит \( h_A \neq h_B \). Пусть \( h_A < h_B \). Тогда дерево B не ниже и не тоньше дерева A.

Случай 3: \( h_A \neq h_B \) и \( t_A \neq t_B \).

Рассмотрим дерево 1 с параметрами \( (h_1, t_1) \). Возьмём другое дерево 2 с параметрами \( (h_2, t_2) \).

Если \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), и при этом \( (h_1, t_1) \neq (h_2, t_2) \), то мы нашли такую пару.

Предположим, что такого не происходит. Тогда для любых двух деревьев \( (h_i, t_i) \) и \( (h_j, t_j) \):

• Если \( h_i ≤ h_j \), то \( t_i > t_j \).
• Если \( t_i ≤ t_j \), то \( h_i > h_j \).

Возьмём дерево 1 \( (h_1, t_1) \). Рассмотрим все деревья. Если есть дерево \( (h_2, t_2) \) такое, что \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), мы доказали утверждение.

Если такого дерева нет, то для любого дерева \( (h_i, t_i) \) (кроме самого себя), либо \( h_i < h_1 \) и \( t_i > t_1 \), либо \( h_i > h_1 \) и \( t_i < t_1 \).

Рассмотрим бесконечный набор деревьев. Это задача на применение принципа Дирихле. Если мы будем отбирать деревья таким образом, чтобы их параметры постоянно увеличивались или уменьшались, рано или поздно возникнет противоречие.

Рассмотрим пару \( (h, t) \). Если существует другая пара \( (h', t') \) такая, что \( h' ≥ h \) и \( t' ≥ t \), и \( (h, t) \neq (h', t') \), то мы нашли искомые деревья.

Предположим, что для любых двух различных пар \( (h_i, t_i) \) и \( (h_j, t_j) \), если \( h_i ≤ h_j \), то \( t_i > t_j \).

Пусть у нас есть дерево \( D_1 = (h_1, t_1) \). Возьмем дерево \( D_2 = (h_2, t_2) \). Если \( h_1 < h_2 \) и \( t_1 < t_2 \), то утверждение доказано.

Если \( h_1 < h_2 \), но \( t_1 ≥ t_2 \), то по условию \( t_1 > t_2 \).

Если \( t_1 < t_2 \), но \( h_1 ≥ h_2 \), то по условию \( h_1 > h_2 \).

Рассмотрим последовательность деревьев \( D_1, D_2, D_3, … \), такую что \( h_1 < h_2 < h_3 < … \). Тогда согласно нашему предположению, \( t_1 > t_2 > t_3 > … \). Эта последовательность толщин является убывающей последовательностью натуральных чисел. Такая последовательность не может быть бесконечной, она должна оборваться. Но у нас бесконечное число деревьев.

Аналогично, рассмотрим последовательность деревьев \( D_1, D_2, D_3, … \), такую что \( t_1 < t_2 < t_3 < … \). Тогда \( h_1 > h_2 > h_3 > … \). Это также убывающая последовательность натуральных чисел, которая не может быть бесконечной.

Следовательно, либо мы нашли пару \( (h_i, t_i) \) и \( (h_j, t_j) \) где \( h_i ≤ h_j \) и \( t_i ≤ t_j \) (и они различны), либо такая последовательность упирается в наименьшие/наибольшие возможные натуральные числа, что противоречит бесконечности.

Более строгое доказательство: По принципу Дирихле, если мы имеем бесконечный набор пар \( (h, t) \) и рассматриваем их в некотором порядке, мы можем построить подпоследовательность. Пусть мы имеем пары \( (h_i, t_i) \).

Рассмотрим все пары \( (h, t) \) в саду. Если существует пара \( (h_1, t_1) \) и \( (h_2, t_2) \) такая, что \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), и \( (h_1, t_1) \neq (h_2, t_2) \), то условие выполнено.

Предположим, что такого не существует. Тогда для любых двух различных пар \( (h_i, t_i) \) и \( (h_j, t_j) \), если \( h_i ≤ h_j \), то \( t_i > t_j \).

Это эквивалентно тому, что если \( h_i < h_j \), то \( t_i > t_j \) (т.к. если \( h_i = h_j \), то \( t_i \neq t_j \), и если \( t_i < t_j \), то \( h_i > h_j \), что противоречит \( h_i = h_j \). Таким образом, если \( h_i = h_j \), то \( t_i > t_j \)).

Итак, для любых \( i \neq j \): если \( h_i ≤ h_j \), то \( t_i > t_j \).

Рассмотрим дерево \( D_1 \) с параметрами \( (h_1, t_1) \).

Если существует дерево \( D_2 \) с параметрами \( (h_2, t_2) \) такое, что \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), то утверждение доказано.

Если для всех других деревьев \( (h_i, t_i) \) из \( h_1 ≤ h_i \) следует \( t_1 > t_i \), то рассмотрим все деревья.

Рассмотрим множество деревьев $$S = \{ (h, t) ∣ h, t ∈ ℕ \}$$.

Допустим, что для любых двух деревьев \( (h_1, t_1), (h_2, t_2) \) из $$S$$ таких, что \( h_1 ≤ h_2 \), выполняется \( t_1 > t_2 \).

Построим последовательность деревьев \( D_1, D_2, D_3, … \).

Пусть \( D_1 = (h_1, t_1) \) — любое дерево.

Если существует \( D_2 = (h_2, t_2) \) такое, что \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), то мы нашли требуемую пару.

Если такого \( D_2 \) не существует, то для любого \( D_i = (h_i, t_i) \), если \( h_1 ≤ h_i \), то \( t_1 > t_i \).

Возьмём дерево с минимальной высотой \( h_{min} \). Пусть это дерево \( D_{minH} = (h_{min}, t_{minH}) \).

Теперь рассмотрим все деревья \( (h, t) \) такие, что \( h ≥ h_{min} \).

Если среди них есть дерево \( (h', t') \) такое, что \( t' ≥ t_{minH} \), то утверждение доказано.

Предположим, что для всех деревьев \( (h, t) \) с \( h ≥ h_{min} \) выполняется \( t < t_{minH} \).

Рассмотрим деревья с высотами \( h_{min}, h_{min}+1, h_{min}+2, … \).

Каждому дереву \( (h, t) \) сопоставим точку \( (h, t) \) на плоскости. Условие, что любые два дерева отличаются хотя бы по одному параметру, означает, что все эти точки различны.

Мы хотим доказать, что существуют две точки \( P_1 = (h_1, t_1) \) и \( P_2 = (h_2, t_2) \) такие, что \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), причём \( P_1 \neq P_2 \).

Предположим противное: для любых двух различных точек \( (h_1, t_1) \) и \( (h_2, t_2) \), если \( h_1 ≤ h_2 \), то \( t_1 > t_2 \).

Рассмотрим множество всех деревьев. Выберем дерево \( D_1 = (h_1, t_1) \).

Если существует дерево \( D_2 = (h_2, t_2) \) такое, что \( h_1 ≤ h_2 \) и \( t_1 ≤ t_2 \), и \( D_1 \neq D_2 \), то условие доказано.

Если такого дерева нет, то для любого другого дерева \( D_i = (h_i, t_i) \), если \( h_1 ≤ h_i \), то \( t_1 > t_i \).

Рассмотрим все деревья. Построим последовательность \( (h_1, t_1), (h_2, t_2), … \) такую, что \( h_1 ≤ h_2 ≤ h_3 … \).

Если \( h_i = h_{i+1} \), то \( t_i \neq t_{i+1} \). Так как \( h_i ≤ h_{i+1} \), то \( t_i > t_{i+1} \).

Если \( h_i < h_{i+1} \), то \( t_i > t_{i+1} \).

Таким образом, мы имеем последовательность высот \( h_1 ≤ h_2 ≤ h_3 … \) и последовательность толщин \( t_1 > t_2 > t_3 > … \).

Так как \( t_i \) — натуральные числа, последовательность \( t_1 > t_2 > t_3 > … \) не может быть бесконечной. Она должна оборваться.

Это означает, что наше предположение неверно.

Следовательно, существует пара деревьев \( D_i = (h_i, t_i) \) и \( D_j = (h_j, t_j) \) такая, что \( h_i ≤ h_j \) и \( t_i ≤ t_j \), и \( D_i \neq D_j \).

Вывод: Утверждение доказано.