OMC231(F)

点数: 500

Writer: shakayami

　非負整数 $x,y$ に対して，それらの排他的論理和 (XOR) を $f(x,y)$ で表します．

排他的論理和の定義

　非負整数

x

に対して，

x

を二進法で表したときの右から

i

桁目（＝

x

の

2^{i-1}

の位）を

d_i(x)

とします．ただし，

x

の桁数が

i

未満であるとき

d_i(x)=0

とします．このとき，

f(x,y)

を以下をみたす非負整数として定めます：

任意の $i=1,2,\ldots$ について， $d_i\bigl(f(x,y)\bigr)=\begin{cases} 0& \bigl(d_i(x)=d_i(y)\bigl)\\ 1& \bigl(d_i(x)\neq d_i(y)\bigr) \end{cases}$ である．

　非負整数 $a,b,c$ に対して，以下の漸化式によって数列 $\{x_n\}_{n=0,1,\ldots}$ を定めます． $x_0=a , \quad x_1=b , \quad x_2=c ,\quad x_{n+3}=f(x_{n+2},x_n) \quad (n=0,1,\ldots)$ このとき，以下の極限値 $F(a,b,c)$ がつねに存在することが証明できます． $F(a,b,c)=\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}x_k$ 以下の値は互いに素な正整数 $A,B$ を用いて $\dfrac{A}{B}$ と表せるので， $A+B$ の値を解答してください． $\dfrac{\displaystyle\sum_{a=0}^{2^{12}-1}\sum_{b=0}^{2^{12}-1}\sum_{c=0}^{2^{12}-1}F(a,b,c)^2}{\displaystyle\sum_{a=0}^{2^{12}-1}\sum_{b=0}^{2^{12}-1}\sum_{c=0}^{2^{12}-1}F(a,b,c)}$

解答を提出するにはログインしてください.