The 35th Japanese Mathematical Olympiad

\boxed{1064} $$\text{For a positive integer }k,\text{ denote the maximum nonnegative integer }i\text{ such that }{2}^i\text{ divides }k\text{ by }{v}_2(k).\text{ Note that }{v}_2(kl)=v_2(k)+v_2(l)\text{ holds for any positive integers }k\text{ and }l,\text{ and that }{v}_2\left(\frac{k}{2}\right)=v_2(k)-1\text{ holds for any positive even number }k.$$ Lemma 1. Let $s$ and $t$ be positive integers. If $v_2(s)\ne v_2(t)$, we have $v_2(s+t)=\min \{v_2(s),v_2(t)\}$.

If $v_2(s)=v_2(t)$, we have $v_2(s+t)>v_2(s)$. Proof. We can write $s=2^{v_2(s)}x$, $t=2^{v_2(t)}y$ for some odd integers $x,y$. In the case of $v_2(s)<v_2(t)$, we have $s+t=2^{v_2(s)}(x+2^{v_2(t)-v_2(s)}y)$. Since $2^{v_2(t)-v_2(s)}y$ is even, $x+2^{v_2(t)-v_2(s)}y$ is odd. Thus $v_2(s+t)=v_2(s)=\min \{v_2(s),v_2(t)\}$ holds. In the case of $v_2(s)>v_2(t)$ the same argument shows that $v_2(s+t)=\min \{v_2(s),v_2(t)\}$. In the case of $v_2(s)=v_2(t)$, we have $s+t=2^{v_2(s)}x+2^{v_2(s)}y=2^{v_2(s)}(x+y)$. Since $x+y$ is even, we have $v_2(s+t)>v_2(s)$. ■

Lemma 2. If $s,t\in \mathbb{N}$ satisfy $v_2(s)=v_2(t)\ge 1$, we have: $$\bullet v_2\left(t+\frac{s}{2}\right)=v_2\left(\frac{s}{2}\right)=v_2(s)-1,$$ $$\bullet v_2\left(s+\frac{t}{2}\right)=v_2\left(\frac{t}{2}\right)=v_2(s)-1.$$ Proof. Since $v_2\left(\frac{s}{2}\right)=v_2(s)-1<v_2(s)=v_2(t)$, we have $v_2\left(t+\frac{s}{2}\right)=\min \{v_2(t),v_2\left(\frac{s}{2}\right)\}=v_2\left(\frac{s}{2}\right)$ by Lemma 1. Thus we have $v_2\left(t+\frac{s}{2}\right)=v_2\left(\frac{s}{2}\right)=v_2(s)-1$. Similarly $v_2\left(s+\frac{t}{2}\right)=v_2\left(\frac{t}{2}\right)=v_2(t)-1=v_2(s)-1$ holds. ■

We will show that, if $a_1,a_2,\dots$ and $b_1,b_2,\dots$ satisfy the condition of the problem, $v_2(a_1)\ne v_2(b_1)$ holds. Assume $v_2(a_1)=v_2(b_1)$. If $v_2(a_1)=v_2(b_1)=0$, $a_2$ cannot be an integer. If $v_2(a_1)=v_2(b_1)=k\ge 1$, Lemma 2 shows inductively that $v_2(a_n)=v_2(b_n)=k-n+1$ for $n\le k+1$. However, when $n=k+1$ we have $v_2(a_n)=v_2(b_n)=0$, then $a_{n+1}$ cannot be an integer. This is a contradiction and we conclude that $v_2(a_1)\ne v_2(b_1)$. Next we will show that, for any integers $1\le s,t\le 40$ with $v_2(s)\ne v_2(t)$, there exists sequences $a_1,a_2,\dots$ and $b_1,b_2,\dots$ such that $a_1=s$ and $b_1=t$. Lemma 3. If $s,t\in \mathbb{N}$ satisfy $v_2(s)\ne v_2(t)$, at least one of the following statements hold: $s$ is even and $v_2\left(t+\frac{s}{2}\right)\ne v_2\left(\frac{s}{2}\right)$ holds. $t$ is even and $v_2\left(s+\frac{t}{2}\right)\ne v_2\left(\frac{t}{2}\right)$ holds. Proof. We will show that if $v_2(s)>v_2(t)$ the first condition holds. $s$ is even because $v_2(s)\ge 1$. If $v_2(s)=v_2(t)+1$, we have $v_2\left(\frac{s}{2}\right)=v_2(s)-1=v_2(t)$ and thus $v_2\left(t+\frac{s}{2}\right)>v_2\left(\frac{s}{2}\right)$ by Lemma 1. If $v_2(s)\ge v_2(t)+2$, we have $v_2\left(\frac{s}{2}\right)=v_2(s)-1>v_2(t)$ and thus $v_2\left(t+\frac{s}{2}\right)=\min \{v_2(t),v_2\left(\frac{s}{2}\right)\}=v_2(t)<v_2\left(\frac{s}{2}\right)$ by Lemma 1.

Let $a_1=s,b_1=t$. Then for $n=1,2,\dots$ we can proceed inductively as follows: Since $v_2(a_n)\ne v_2(b_n)$, Lemma 3 shows that at least one of $(x,y)=\left(\frac{a_n}{2},b_n+\frac{a_n}{2}\right)$, $\left(a_n+\frac{b_n}{2},\frac{b_n}{2}\right)$ is a pair such that $v_2(x)\ne v_2(y)$. We set $a_{n+1}=x,b_{n+1}=y$ for such $(x,y)$. The resulting sequences $a_1,a_2,\dots$ and $b_1,b_2,\dots$ meet the condition of the problem. Therefore the answer is the number of pairs of integers $(s,t)$ with $1\le s,t\le 40$ such that $v_2(s)\ne v_2(t)$. Note that $v_2(n)\le 5$ for $1\le n\le 40$ because $40<2^6$. For $k\in \{0,1,\dots ,5\}$, the number $f(k)$ of integers $1\le n\le 40$ such that $v_2(n)=k$ is $\lfloor \frac{40}{2^k}\rfloor -\lfloor \frac{40}{2^{k+1}}\rfloor$. Thus we can calculate $$f(0)=20,f(1)=10,f(2)=5,f(3)=3,f(4)=1,f(5)=1.$$ The number of pairs of integers $(s,t)$ with $1\le s,t\le 40$ such that $v_2(s)=v_2(t)$ is ${\sum }_{k=0}^{5}f(k{)}^2=536$. Therefore, the answer is $40^2-536=1064$.