MathLabs

第4問

任意の正整数 tt に対し、0,1,…,t−10,1,\ldots,t-1 の順列 a0,a1,…,at−1a_0,a_1,\ldots,a_{t-1} であって、すべての 0≤i≤t−10\le i\le t-1 について二項係数 (t+i2ai)\binom{t+i}{2a_i} が奇数であり、かつ 2ai≠t+i2a_i\neq t+i を満たすものがただ一つ存在することを証明せよ。
ステップ 6/6: 帰納法が一意な対合わせを構成する
前のステップ次のステップ
∃! pairing of small and big numbers  ⟹  ∃! (a0,…,at−1)\exists!\text{ pairing of small and big numbers}\implies\exists!\ (a_0,\ldots,a_{t-1})
詳しい解説

tt に関する帰納法により、小さい数 {0,…,⌈t/2⌉−1}\{0,\ldots,\lceil t/2\rceil-1\} を大きい数 {⌈t/2⌉,…,t−1}\{\lceil t/2\rceil,\ldots,t-1\} と一意に対合わせでき、対応する各小さい xx とその相手の大きい yy について S(x)⊊S(y)S(x)\subsetneq S(y)、∣S(x)∣=∣S(y)∣−1|S(x)|=|S(y)|-1 が成り立つことが示される:大きい範囲にある唯一の2のべき乗 2a2^a を取り除き、2a2^a を 2a−2a=02^a-2^a=0 と対にする。残りの数はより小さい2つの対合わせ問題に分かれ、全単射 z↦2a−1−zz\mapsto 2^a-1-z で結ばれ、帰納法の仮定によりこれは一意である。t+it+i が奇数の場合の直接公式と合わせると、問題が要求する一意な順列 a0,…,at−1a_0,\ldots,a_{t-1} が得られる。