OMC238(D)

　$1$ 以上 $50$ 以下の整数の集合を，最大の奇数の約数が同じである集合，すなわち $$\{1,2,4,...,32\},\{3,6,...,48\},\{5,10,20,40\},\cdots, \{49\}$$ に分割し，順に $U_1,U_3,...,U_{49}$ とする．
　$1$ 以上 $49$ 以下の相異なる奇数 $i,j$ と $x\in U_i$ および $y\in U_j$ に対して，$x\in A$ かどうかは $y\in A$ かどうかに影響しないので，$k=1,3,...,49$ に対して，$U_k\cap A$ を定めれば良い．$U_k\cap A$ の定め方が $u_k$ だけあるとする．$U_k$ の要素を小さい順に並べたとき，条件より隣り合う要素がどちらも $A$ の要素になることはないので，$u_k$ は次の数に等しい．

• コインを左右に $|U_k|$ 個並べる方法であって，裏向きのコインが隣り合わないような並べ方の数．

コインが $n$ 個あるときの並べ方が $F_n$ だけあるとすると，一番左のコインの表裏で場合分けすることで，次の漸化式を得る． $$F_{n+2}=F_{n+1}+F_n$$ これと $F_1=2,F_2=3$ より，$F_3=5,F_4=8,F_5=13,F_6=21$ である．
　$U_k$ の要素の数を調べると， $$|U_k|= \left\{ \begin{aligned} & 6 \ (k=1) \\ & 5 \ (k=3) \\ & 4 \ (k=5) \\ & 3 \ (k=7,9,11) \\ & 2 \ (k=13,15,...,25) \\ & 1 \ (k=27,29,...,49) \end{aligned} \right.$$ であるので，$N$ の値は次のように計算できる． $$\begin{aligned} N&=u_1\times u_3\times \cdots \times u_{49}\\ &=F_{|U_1|}\times F_{|U_3|}\times \cdots \times F_{|U_{49}|}\\ &=F_6\times F_5 \times F_4 \times F_3^3 \times F_2^7 \times F_1^{12}\\ &=21\times 13 \times 8 \times 5^3 \times 3^7 \times 2^{12}\\ &=2^{15}\cdot 3^{8}\cdot 5^{3}\cdot 7\cdot 13 \end{aligned}$$ これの正の約数の個数は $\bf2304$ である．