1994年IMO香港大会3問目の解答、解説

かなり昔の問題で日本語化されてなく、Google翻訳および自分の違和感に頼って翻訳したので、万が一勘違いがあるかもしれません…
数論、組み合わせ論の面白い問題です。(編集中)

問題(翻訳、改)

任意のk∈ℕに対して、f(k)を「集合{k+1,k+2,...,2k}の元であり、2進法で表したときに1がちょうど3回現れるものの個数」とする。
このとき、以下の問いに答えよ。

(a)各m∈ℕに対して、少なくとも1つのk∈ℕが存在し、f(k)=mであることを示せ。

(b)ちょうど1つのk∈ℕが存在し、f(k)=mとなるようなm∈ℕを全て求めよ。

考え方

二進法、一般にn進法における大小関係は、辞書式順序によって与えられます。
さらに、{k+1,k+2,...,2k}の元を2倍、または1/2倍したものからなる集合と元の集合が互いに素であることが


kを2進法によって表した時の最左の桁を2^sの位とすると、{k+1,k+2,...,2k}の元を2進法で表した時の最右