2018年JJMO本選4問目の解答、解説

数論と組み合わせの複合問題です。

問題

kを2以上の正の整数とし、A=2^k-1とする。
まずA/2以下の正の奇数lを黒板に書き、次の操作をk-1回繰り返す。

操作…直前に書かれた整数をnとしたとき、A-nを割り切る最大の奇数を黒板に書く。

このとき、最初に書いたものも含めてlが黒板に2回以上書かれることを示せ。

考え方

A=2^k-1を二進法で表すと、11…(1がk個)…1となることや、ある正の整数xを割り切る最大の奇数は、xを二進法で表したときに末尾の0をすべて取り除いた値といえることに気づくと、二進法が鍵を握っているように見えます。
メタいけれど、操作×整数の複合問題はp進法とmodがほとんどですから、この2点のうちどっちかと思っておいてもいいかも…?

Aからの引き算や、末尾の0を取り除くという計算は、連続した0,1のブロックごとに変化する操作のため、二進法表記をブロック的に解釈すれば良さそうです。

上記のことを踏まえて、解答を作っていきます。

解答

lをk桁満の2進法で表現することを考える。
l≦A/2=(2^k-1)/2=2^(k-1)-0.5
より、lは2^(k-1)-1以下のため、桁数は(k-1)桁以下である
さらにlは奇数のため、k桁満の2進法で表現すると、先頭には0が、末尾には1が存在する。

このような値の二進法は、
l=0..(0がa₁個)..01..(1がa₂個)..10..(0がa₃個)..0……1..(1がan個)..1 (2)
と、nおよび配列{a₁,a₂,…,an}によって一意的に表せるため、これをlの配列表現と呼称する。
ただし、nはk以下の正の偶数、a₁,a₂,…,anは正の整数であり、a₁+a₂+…+an=kを満たすものとする。

ここで、Aは二進法で11..(1がk個)..1 (2)と表せるので、
2進法における筆算を考えると、A-lの二進法はlの1,0を反転させたものであり、
A-l=
1..(1がa₁個)..10..(0がa₂個)..01..(1がa₃個)..1……0..(0がan個)..0 (2)

そして、ある正の整数xを割り切る最大の正の奇数は、xを二進法で表したときに末尾の0をすべて取り除いた値といえるため、「操作」によって得られる値は
1..(1がa₁個)..10..(0がa₂個)..01..(1がa₃個)..1……1..(1がa_(n-1)個)..1 (2)

上記の値の桁数はa₁+a₂+…+a_(n-1)=k-anのため、これをk桁満で表すと、先頭にan個の0が付き、

0..(0がan個)..01..(1がa₁個)..10..(0がa₂個)..0……1..(1がa_(n-1)個)..1 (2)

よって、正の奇数に対する「操作」とは、配列表現において、
{a₁,a₂,…,an}を{an,a₁,a₂,…,a_(n-1)}と並び替える操作である。

上記のような配列の並び替えは、n回繰り返すことでもとに戻る、すなわち操作によって得られる整数がlであると言える。

そのため、n≦k-1の場合題意が成り立つと言える。
また、n=kの場合については、a₁+a₂+…+an=kより{a₁,a₂,…,an}={1,1,…,1}となり、これは並び替えに対して不変なため、同様に題意が成り立つ。

よって、k-1回の操作によって、最初に書いたものも含めてlが黒板に2回以上書かれることが示された。…(答)

感想

とてもきれいな良問でした。
今回のようなバイナリや、より複数種類のデータが並ぶ場合においても、同じ種類のものが連続して並ぶ部分列ごとに分割して考察するのが有効なパターンは、数え切れないほどあります。