Таблица из 100 строк и 2 столбцов заполнена числами от 0 до 9 так, чтобы выполнялись условия: (а) все строки таблицы различны; (б) ни одну строку в таблице нельзя получить из какой-нибудь вышестоящей строки заменами большего числа на меньшее. Докажите, что какая-то из строк таблицы равна (5, 5). Какой по счёту может быть эта строка (начиная с верха)? Укажите все возможные значения и докажите корректность приведенного ответа.

Для начала заметим, что всего есть 10 * 10 = 100 вариантов строк. Тогда т.к. по условию в таблице
дано 100 строк, то каждая строка встретится в этой таблице. Тогда и найдется строка (5, 5)
Пусть строка (a, b) обозначает число ab. Рассмотрим число ab. Из этого числа можно попасть в числа, у которых первая цифра от 0 до a, вторая цифра от 0 до b, то есть в (a + 1)(b + 1) чисел (при
условии, что число ab находится выше этих чисел). Но мы посчитали число ab – оно лишнее. Тогда
всего можно попасть в (a + 1)(b + 1) − 1 чисел из числа ab.
Тогда из строки (5, 5) можно попасть в 35 чисел. Тогда строка (5, 5) находится хотя бы на 36 месте,
т.к. иначе под строкой (5, 5) найдется хотя бы одно число, в которое можно попасть из строки (5, 5).
Теперь посчитаем, из скольки чисел можно попасть в число 55: это числа 56, 57, 58, 59 и числа вида
x5, x6, x7, x8, x9, где x ∈ {6, 7, 8, 9}. Тогда всего чисел, из которых можно попасть в 55 – 24. Тогда
строка (5, 5) находится не ниже, чем на 76 месте, т.к. иначе над строкой (5, 5) найдется строка, из
которой можно попасть в (5, 5).
Приведем пример, когда можно поставить строку (5, 5) на любое место от 36 до 76. Для начала
рассмотрим таблицу без строки (5, 5). Расставим строки так:
Сначала идут строки вида (x, 1),(x, 2),(x, 3),(x, 4), где x ∈ {0, 1, 2, 3, 4, 5}(то есть строки (0, 0),
(0, 1), . . . (0, 5), (1, 0), (1, 1), . . . , (1, 5), . . . , (5, 4)) – ровно 35 строк (назовем 1-м модулем).
Затем идут строки вида (x, 6),(x, 7),(x, 8),(x, 9), где x ∈ {0, 1, 2, 3, 4}(то есть строки (0, 6), (0, 7), . . .
(0, 9), (1, 6), (1, 7), . . . , (1, 6), . . . , (4, 9)) (назовем 12м модулем)
Затем идут строки вида (x, 0),(x, 1),(x, 2),(x, 3),(x, 4), где x ∈ {6, 7, 8, 9}(то есть строки (6, 0), (6, 1),
. . . (6, 4), (7, 0), (7, 1), . . . , (7, 4), . . . , (9, 4)) (назовем 3-м модулем)
Затем идут строки (5, 6), (5, 7), (5, 8), (5, 9) и строки вида (x, 6),(x, 7),(x, 8),(x, 9), где x ∈ {6, 7, 8, 9}(то
есть строки (5, 6), (5, 7), . . . (5, 9), (6, 6), (6, 7), . . . , (6, 9), . . . , (9, 9)) – ровно 24 строки (назовем 4-м
модулем)
Понятно, что нельзя получить нижнюю строку любого модуля из верхней, потому что числа в модулях расставлены по возрастанию. Нельзя получить строку одного модуля из строки другого, т.к.
у любых двух строк будут различны либо первые, либо вторые цифры.
Теперь докажем, что мы можем поставить строку (5, 5) в любое место от 36 до 76 включительно.
Мы не сможем получить строку (5, 5) из 1-го модуля, потому что в нем все числа меньше 55. Нельзя
получить строку 4-го модуля из строки (5, 5), потому что все числа 4-го модуля больше 55.
Нельзя получить строку (5, 5) из строк над (5, 5) в модуле 2, потому что 5 меньше второй цифры
любой строки 2-го модуля, и нельзя получить строку 2-го модуля из строки (5, 5), так как первая
цифра любого 2-го модуля меньше 5.
Нельзя получить строку (5, 5) из строк 3-го модуля, так как вторая цифра любой строки 3-го модуля
меньше 5 и нельзя получить строку 3-го модуля из (5, 5), потому что первая цифра любой строки
3-го модуля больше 5.
Получим, что строка (5, 5) может стоять в любом месте от 36 до 76 включительно.