解説

方針・初手

$x,y$ は正の整数であり、$x$ も $1$ から $n$ までの整数に限られる。

まず $x$ を固定し、そのとき許される $y$ の個数を数える。対数の不等式は、底 $2$ が $1$ より大きいことと $x,y>0$ を用いて、通常の不等式に直す。

解法1

条件は

$$ x>0,\quad y>0,\quad \log_2 \frac{y}{x}\le x\le n

$$

である。格子点なので $x,y$ は整数である。

$x$ は正の整数で $x\le n$ を満たすから、

$$ x=1,2,\dots,n

$$

である。

次に、$x$ を固定する。底 $2$ は $1$ より大きいので、対数関数は単調増加である。したがって

$$ \log_2 \frac{y}{x}\le x

$$

は

$$ \frac{y}{x}\le 2^x

$$

と同値である。ここで $x>0$ より、両辺に $x$ を掛けて

$$ y\le x2^x

$$

を得る。

また $y$ は正の整数であるから、固定した $x$ に対して $y$ の取り得る値は

$$ 1,2,\dots,x2^x

$$

であり、その個数は $x2^x$ 個である。

よって求める格子点の総数は

$$ \sum_{x=1}^{n}x2^x

$$

である。

この和を計算する。まず

$$ S=\sum_{x=1}^{n}x2^x

$$

とおくと、

$$ 2S=\sum_{x=1}^{n}x2^{x+1}

$$

である。これらを具体的に並べると

$$ S=1\cdot 2+2\cdot 2^2+3\cdot 2^3+\cdots+n2^n

$$

$$ 2S=1\cdot 2^2+2\cdot 2^3+3\cdot 2^4+\cdots+n2^{n+1}

$$

である。よって $2S-S$ をとると、

$$ \begin{aligned} S &=-2-(2^2+2^3+\cdots+2^n)+n2^{n+1} \\ &=n2^{n+1}-2-\sum_{k=2}^{n}2^k \end{aligned}

$$

となる。ここで

$$ \sum_{k=2}^{n}2^k=2^{n+1}-4

$$

より、

$$ \begin{aligned} S &=n2^{n+1}-2-(2^{n+1}-4) \\ &=(n-1)2^{n+1}+2 \end{aligned}

$$

である。

したがって、求める格子点の個数は

$$ (n-1)2^{n+1}+2

$$

である。

解説

この問題では、対数不等式をそのまま扱うのではなく、$x$ を固定して $y$ の範囲に直すのが基本である。

$x,y>0$ が与えられているため、$\log_2 \frac{y}{x}$ は定義され、さらに底 $2$ の対数関数が単調増加であることから、

$$ \log_2 \frac{y}{x}\le x

$$

を

$$ y\le x2^x

$$

に変形できる。

あとは、各 $x=1,2,\dots,n$ について $y$ が $1$ から $x2^x$ まで動くことを数え上げ、最後に等比数列を含む和 $\sum x2^x$ を計算すればよい。

答え

$$ (n-1)2^{n+1}+2

$$