Loading [MathJax]/jax/output/SVG/jax.js

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


Докажите, что для каждого натурального числа t существует единственная перестановка a0,a1,,at1 чисел 0,1,,t1 такая, что для каждого 0it1 выполнено: 2ait+i и биномиальный коэффициент C2ait+i является нечетным числом.
посмотреть в олимпиаде

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

  4
25 дней 2 часов назад #

Заметим сперва, что Ckm нечетно тогда и только тогда, когда в двоичной записи числа m на каждой позиции где стоит 0 также стоит 0 и в двоичной записи числа k (Например, по теореме Люка). То есть S(t+i)S(2ai), где S(n) обозначает количество единиц в двоичной записи n, но на самом деле это неравенство можно усилить до S(t+i)S(2ai)+1=S(ai)+1, потому что t+i2ai.

То есть S(t)+S(t+1)++S(2t1)S(0)++S(t1)+t. Докажем по индукции, что на самом деле для любого t это равенство. Для t=2k, S(2k)+S(2k+1)++S(4k1)=2S(2k)+1+2S(2k+2)+1++2S(4k2)+1=2S(k)+2S(k+1)++2S(2k1)+k=S(0)+S(1)++S(k1)+S(k)+S(k+1)++S(2k1)+2k, где мы использовали S(0)+S(1)++S(k1)+k=S(k)+S(k+1)++S(2k1), по предположению. Для t=2k1, S(2k1)+S(2k)++S(4k3)=S(2k1)+2S(2k)+1+2S(2k+2)+1++2S(4k4)+1=2S(k)+2S(k+1)++2S(2k2)+k1+S(2k1)=2S(k)+2S(k+1)++2S(2k2)+k1+S(2k1)=S(0)+S(1)++S(k1)+S(k)+S(k+1)++S(2k2)+2k1, где мы использовали предположение из предыдущего случая.

Это значит, что S(t+i)=S(2ai)+1. Можно интерпретировать это как то, что мы получаем 2ai заменой в двоичной записи t+i одной единицы на ноль. Это означает, что at2s+1=ts, потому что единица в конце числа t+t2s+1=2(ts)+1 обязана быть заменена и ничего другого мы поменять не можем.

Опять рассмотрим два случая. Если t=2k, то нам остается сопоставить числам 2k, 2k+2, , 4k2 числа 0, 2, 4, , 2k2 заменяя ровно одну единицу. Поделим на два, ничего не изменится. k, k+1, , 2k1 надо сопоставить 0, 1, , k1. Докажем по индукции, что существует ровно один способ это сделать. Пусть 2m1<k2m, тогда k2m2k1, тогда 2m должно быть сопоставлено 0. Аналогично, любое число x2m должно быть сопоставлено x2m, потому что если мы не поменяем первую единицу, то оно будет 2mk. Останется сопоставить k, , 2m1 числам 2k2m, 2k+12m, , k1, меняя единицу в двоичной записи. Все эти числа 2m1, поэтому отнимем каждое от 2m1, тогда все цифры в двоичной записи поменяются. Теперь нужно сопоставить 2mk, , 2m+112k числам 0, 1, , 2m1k, заменяя единицу, что возможно сделать единственным образом по предположению, так как 2mkk1.

Остается случай t=2k1. Делая те же шаги, получаем, что нужно сопоставить k, k+1, , 2k2 числам 0, 1, , k2, меняя единицу. Также по индукции докажем, что существует ровно один способ сделать это. Как и в прошлом случае, существует степень двойки 2m между k и 2k2, и начиная с нее все сопоставления определены. Все что остается это сопоставить k, , 2m1 числам 2k12m, 2k2m, , k2. Также как и в прошлом случае отнимем все числа от 2m1. Выйдет, что нужно сопоставить 2m+1k, , 2m+12k числам 0, 1, , 2mk1, что возможно сделать единственным образом, так как 2m+1kk1.

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

  2
25 дней назад #

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