Азиатско-Тихоокеанская математическая олимпиада, 2024 год

Кез келген натурал $t$ саны үшін, әрбір ${0 \le i \le t-1}$ үшін $2a_i \ne t +i$ және $C_{t+i}^{2a_i}$ биномдық коэффициенті тақ сан болатындай $0,1,\ldots,{t-1}$ сандарының тек жалғыз $a_0,a_1,\ldots,a_{t-1}$ орын ауыстыруы бар екенін дәлелдеңіз.

Комментарий/решение

Заметим сперва, что $C_{m}^{k}$ нечетно тогда и только тогда, когда в двоичной записи числа $m$ на каждой позиции где стоит 0 также стоит 0 и в двоичной записи числа $k$ (Например, по теореме Люка). То есть $S(t+i) \ge S(2a_i)$, где $S(n)$ обозначает количество единиц в двоичной записи $n$, но на самом деле это неравенство можно усилить до $S(t+i) \ge S(2a_i) + 1 = S(a_i) + 1$, потому что $t+i \ne 2a_i$.

То есть $S(t) + S(t+1) + \ldots + S(2t-1) \ge S(0) + \ldots + S(t-1) + t$. Докажем по индукции, что на самом деле для любого $t$ это равенство. Для $t=2k$, $$S(2k)+S(2k+1)+\ldots+ S(4k-1) = 2S(2k)+1 + 2S(2k+2)+1+\ldots + 2S(4k-2)+1 = 2S(k)+2S(k+1)+\ldots + 2S(2k-1) + k = S(0)+S(1)+\ldots + S(k-1) + S(k)+S(k+1)+\ldots + S(2k-1) + 2k,$$ где мы использовали $S(0)+S(1)+\ldots + S(k-1) + k = S(k)+S(k+1)+\ldots + S(2k-1)$, по предположению. Для $t=2k-1$, $$S(2k-1)+S(2k)+\ldots+ S(4k-3) = S(2k-1) + 2S(2k)+1 + 2S(2k+2)+1+\ldots + 2S(4k-4)+1 = 2S(k)+2S(k+1)+\ldots + 2S(2k-2) + k-1 + S(2k-1) = 2S(k)+2S(k+1)+\ldots + 2S(2k-2) + k-1 + S(2k-1) = S(0)+S(1)+\ldots + S(k-1) + S(k)+S(k+1)+\ldots + S(2k-2) + 2k-1,$$ где мы использовали предположение из предыдущего случая.

Это значит, что $S(t+i)=S(2a_i)+1$. Можно интерпретировать это как то, что мы получаем $2a_i$ заменой в двоичной записи $t+i$ одной единицы на ноль. Это означает, что $a_{t-2s+1} = t-s$, потому что единица в конце числа $t+t-2s+1 = 2(t-s)+1$ обязана быть заменена и ничего другого мы поменять не можем.

Опять рассмотрим два случая. Если $t=2k$, то нам остается сопоставить числам $2k$, $2k+2$, $\ldots$, $4k-2$ числа $0$, $2$, $4$, $\ldots$, $2k-2$ заменяя ровно одну единицу. Поделим на два, ничего не изменится. $k$, $k+1$, $\ldots$, $2k-1$ надо сопоставить $0$, $1$, $\ldots$, $k-1$. Докажем по индукции, что существует ровно один способ это сделать. Пусть $2^{m-1}<k\le 2^m$, тогда $k\le 2^m \le 2k-1$, тогда $2^m$ должно быть сопоставлено 0. Аналогично, любое число $x\ge 2^m$ должно быть сопоставлено $x-2^m$, потому что если мы не поменяем первую единицу, то оно будет $\ge 2^m \ge k$. Останется сопоставить $k$, $\ldots$, $2^m-1$ числам $2k-2^m$, $2k+1-2^m$, $\ldots$, $k-1$, меняя единицу в двоичной записи. Все эти числа $\le 2^m-1$, поэтому отнимем каждое от $2^m-1$, тогда все цифры в двоичной записи поменяются. Теперь нужно сопоставить $2^{m}-k$, $\ldots$, $2^{m+1}-1-2k$ числам $0$, $1$, $\ldots$, $2^{m}-1-k$, заменяя единицу, что возможно сделать единственным образом по предположению, так как $2^m-k \le k-1$.

Остается случай $t=2k-1$. Делая те же шаги, получаем, что нужно сопоставить $k$, $k+1$, $\ldots$, $2k-2$ числам $0$, $1$, $\ldots$, $k-2$, меняя единицу. Также по индукции докажем, что существует ровно один способ сделать это. Как и в прошлом случае, существует степень двойки $2^m$ между $k$ и $2k-2$, и начиная с нее все сопоставления определены. Все что остается это сопоставить $k$, $\ldots$, $2^m-1$ числам $2k-1-2^m$, $2k-2^m$, $\ldots$, $k-2$. Также как и в прошлом случае отнимем все числа от $2^m-1$. Выйдет, что нужно сопоставить $2^m+1-k$, $\ldots$, $2^{m+1}-2k$ числам $0$, $1$, $\ldots$, $2^m-k-1$, что возможно сделать единственным образом, так как $2^m+1-k \le k-1$.

Замечание. Случаи четного и нечетного можно объединить в один, если знать как пользоваться функциями $\lfloor$ $\rfloor$ и $\lceil$ $\rceil$.

Решил настроится?