Высшая проба 2022, 9-10 классы, задача 4

Решение. На протяжении этого решения число сочетаний из по обозначается , читателей, более привыкших к нотации просим обращать внимание на "перевернутый" порядок индексов: .

Итак, нам требуется найти число пар и , таких что , причем выполняются три соотношения при . Наше решение задачи состоит из двух этапов:

Утверждение . Пары биективно соответствуют четверкам , таким что , и .

Комментарий . Говоря более развернуто, в Утверждении сказано следующее: у каждой удовлетворяющей условию задачи пары их цифры таковы, как сказано в Утверждении , и обратно, каждая четверка , удовлетворяющая условию Утверждения , ровно одним способом достраивается до пары , удовлетворяющей условию задачи.

Утверждение . Количество четверок , удовлетворяющих условиям Утверждения , есть в точности .

План решения намечен, осталось его осуществить.

Лемма . Всякое интересное число имеет вид:

где и . И обратно, всякая запись такого вида является корректной записью в -ичной системе счисления интересного числа.

Доказательство. Условие, что число является интересным есть , или эквивалентно

Значит, по заданному значению пара восстанавливается не более чем одним способом, иначе число имело бы больше одной записи в -ичной системе счисления. Но заметим, что при подстановке , равенство верно тождественно, кроме того, (за это отвечает условие ), неравенства и очевидно следуют из .

Доказательство утверждения . Пусть и - два интересных числа. Рассмотрим "-ичную запись без переносов" , она конечно же может и не быть правильной -ичной записью, поскольку некоторые из "цифр" могут быть больше ; но она удовлетворяет равенству (), поскольку ему удовлетворяют и . Посмотрим, что происходит, когда мы "вспоминаем", что надо сделать перенос. Если перенос из разряда единиц, то уменьшается на , а увеличивается на , значит всего левая часть () увеличивается на . Аналогично если перенос из разряда - то уменьшается на и увеличивается на , всего левая часть () увеличивается на . Аналогично при переносе из разряда левая часть () уменьшается на . Заметим, что из одного разряда не может быть сделано больше одного переноса: то что стоит в разряде есть сумма двух цифр, плюс возможно единичка, пришедшая из переноса - это точно меньше . Значит, если соотношение (*) выполнялось до всех переносов и выполняется после всех - то либо не было сделано ни одного переноса, либо были сделаны все три. Докажем, что первый вариант невозможен. В самом деле, по Лемме , аналогично . Но если из разряда единиц не было переносов, из разряда его тоже не было (число осталось четырехзначным), тогда сумма цифр в этих разрядах сейчас равна . Но такую сумму двумя цифрами можно набрать единственным образом: . То есть . По Лемме это означает , то есть - тогда из разряда есть перенос - противоречие! Итак, должны осуществиться ровно три переноса. Докажем, что это эквивалентно условию . В разряде единиц стоит - при перенос есть; в разряде стоит (единичка пришла от переноса) - перенос есть тогда и только тогда, когда ; в разряде стоит - при перенос есть, наконец из разряда переноса нет когда он есть из разряда единиц.

Для Утверждения мы приведем комбинаторное доказательство.

Комбинаторное доказательство Утверждения с наводящими соображениями. Напомним, что выражение считает способы расставить в ряд белых и черных шаров. Научимся через такие функции выражать ответы в задачах типа нашей, начнем с более простой.

Поучительный пример . Пусть мы хотим перечислить пары , такие что и . Построим для этого биекцию между такими парами, и расстановками в ряд двух черных и белого шарика следующим образом: для расстановки посчитаем число белых шариков, стоящих правее левого черного шарика (не важно до или после правого черного) - назовем это число ; аналогично посчитаем число белых шаров, стоящих левее правого черного - назовем это число . Очевидно, оба числа лежат в заказанных пределах, притом - каждый белый шарик посчитан хотя бы один раз, те что стоят между черными посчитаны дважды. Оставляем читателю додумать, почему построена именно биекция, то есть по паре можно построить расстановку шариков в ряд, притом ровно одну. Итак, количество таких пар есть в точности .

Поучительный пример . Отлично, усложним задачу. Пусть мы ищем число четверок , таких что , , и наконец . Давайте смотреть на расстановки в ряд четырех черных шаров и белого. Первый черный шар будет отвечать за , второй за , для каждого из них соответствующими числами мы будем называть число белых шаров вправо от них, тогда автоматически получится, что (всякий белый шар, который правее второго слева черного, также правее и первого слева черного). Аналогично третий и четвертый черные шары отвечают за числа и соответственно, причем числа равны количеству белых шаров левее соответствующего черного. Аналогично имеем а также полностью аналогично прошлому примеру. Итак, количество таких четверок есть в точности .

А теперь собственно то, что нам нужно. Напомним: мы ищем число таких четверок , что , , и наконец . Чтобы действовать как в примере нам нужно было бы пересчитать расстановки в ряд черных и белого шара, такие что между первым и вторым черными стоят хотя бы два белых, и между третьим и четвертым черными стоят хотя бы два белых. Сделаем это так: перечислим все расстановки в ряд четырех черных и белых, таких расстановок ровно

Теперь в каждую из расстановок добавим два белых шара между первым и вторым черными, и два белых между третьим и четвертым черными. Оставляем читателю доказать, что построена биекция между множеством всех расстановок четырех черных и белых, и множеством расстановок с приведенным выше дополнительным условием четырех черных и белого.

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