Азиатско-Тихоокеанская математическая олимпиада, 2024 год
Комментарий/решение:
Заметим сперва, что Ckm нечетно тогда и только тогда, когда в двоичной записи числа m на каждой позиции где стоит 0 также стоит 0 и в двоичной записи числа k (Например, по теореме Люка). То есть S(t+i)≥S(2ai), где S(n) обозначает количество единиц в двоичной записи n, но на самом деле это неравенство можно усилить до S(t+i)≥S(2ai)+1=S(ai)+1, потому что t+i≠2ai.
То есть S(t)+S(t+1)+…+S(2t−1)≥S(0)+…+S(t−1)+t. Докажем по индукции, что на самом деле для любого t это равенство. Для t=2k, S(2k)+S(2k+1)+…+S(4k−1)=2S(2k)+1+2S(2k+2)+1+…+2S(4k−2)+1=2S(k)+2S(k+1)+…+2S(2k−1)+k=S(0)+S(1)+…+S(k−1)+S(k)+S(k+1)+…+S(2k−1)+2k, где мы использовали S(0)+S(1)+…+S(k−1)+k=S(k)+S(k+1)+…+S(2k−1), по предположению. Для t=2k−1, S(2k−1)+S(2k)+…+S(4k−3)=S(2k−1)+2S(2k)+1+2S(2k+2)+1+…+2S(4k−4)+1=2S(k)+2S(k+1)+…+2S(2k−2)+k−1+S(2k−1)=2S(k)+2S(k+1)+…+2S(2k−2)+k−1+S(2k−1)=S(0)+S(1)+…+S(k−1)+S(k)+S(k+1)+…+S(2k−2)+2k−1, где мы использовали предположение из предыдущего случая.
Это значит, что S(t+i)=S(2ai)+1. Можно интерпретировать это как то, что мы получаем 2ai заменой в двоичной записи t+i одной единицы на ноль. Это означает, что at−2s+1=t−s, потому что единица в конце числа t+t−2s+1=2(t−s)+1 обязана быть заменена и ничего другого мы поменять не можем.
Опять рассмотрим два случая. Если t=2k, то нам остается сопоставить числам 2k, 2k+2, …, 4k−2 числа 0, 2, 4, …, 2k−2 заменяя ровно одну единицу. Поделим на два, ничего не изменится. k, k+1, …, 2k−1 надо сопоставить 0, 1, …, k−1. Докажем по индукции, что существует ровно один способ это сделать. Пусть 2m−1<k≤2m, тогда k≤2m≤2k−1, тогда 2m должно быть сопоставлено 0. Аналогично, любое число x≥2m должно быть сопоставлено x−2m, потому что если мы не поменяем первую единицу, то оно будет ≥2m≥k. Останется сопоставить k, …, 2m−1 числам 2k−2m, 2k+1−2m, …, k−1, меняя единицу в двоичной записи. Все эти числа ≤2m−1, поэтому отнимем каждое от 2m−1, тогда все цифры в двоичной записи поменяются. Теперь нужно сопоставить 2m−k, …, 2m+1−1−2k числам 0, 1, …, 2m−1−k, заменяя единицу, что возможно сделать единственным образом по предположению, так как 2m−k≤k−1.
Остается случай t=2k−1. Делая те же шаги, получаем, что нужно сопоставить k, k+1, …, 2k−2 числам 0, 1, …, k−2, меняя единицу. Также по индукции докажем, что существует ровно один способ сделать это. Как и в прошлом случае, существует степень двойки 2m между k и 2k−2, и начиная с нее все сопоставления определены. Все что остается это сопоставить k, …, 2m−1 числам 2k−1−2m, 2k−2m, …, k−2. Также как и в прошлом случае отнимем все числа от 2m−1. Выйдет, что нужно сопоставить 2m+1−k, …, 2m+1−2k числам 0, 1, …, 2m−k−1, что возможно сделать единственным образом, так как 2m+1−k≤k−1.
Замечание. Случаи четного и нечетного можно объединить в один, если знать как пользоваться функциями ⌊ ⌋ и ⌈ ⌉.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.