Bài toán 35.[IMC 2015, Day 1, Problem 2] Với mỗi số nguyên dương $n$, đặt $f(n)$ là số sau khi viết $n$ thành hệ nhị phân và thay mỗi số $0$ bằng số $1$ và ngược lại. Ví dụ $n=23$ sẽ trở thành $10111$ trong hệ nhị phân, vì thế $f(n)$ sẽ là $1000$ trong hệ nhị phân, khi đó $f(23)=8$. Chứng minh rằng: $$\sum_{k=1}^{n}f(k)\le \dfrac{n^2}{4}$$ Đẳng thức xảy ra khi nào? (Đề xuất bởi Stephan Wagner, Đại học Stellenbosch)

Bài toán 35.[IMC 2015, Day 1, Problem 2] Với mỗi số nguyên dương $n$, đặt $f(n)$ là số sau khi viết $n$ thành hệ nhị phân và thay mỗi số $0$ bằng số $1$ và ngược lại. Ví dụ $n=23$ sẽ trở thành $10111$ trong hệ nhị phân, vì thế $f(n)$ sẽ là $1000$ trong hệ nhị phân, khi đó $f(23)=8$. Chứng minh rằng: $$\sum_{k=1}^{n}f(k)\le \dfrac{n^2}{4}$$ Đẳng thức xảy ra khi nào? (Đề xuất bởi Stephan Wagner, Đại học Stellenbosch)

Lời giải

Nếu $r$ và $k$ là những số nguyên dương sao cho $2^{r-1}\le k\le 2^r, k$ sẽ có $r$ chữ số trong hệ nhị phân, nên $k+f(k)=\overline{11\dots1}=2^r-1$ (Biểu diễn nhị phân có $r$ chữ số $1$.)
Giả sử rằng $2^{s-1}\le n\le 2^s-1$. Khi đó: { \begin{align*} \frac{n(n+1)}{2}+\sum_{k=1}^{n} f(k) &=\sum_{k=1}^{n}(k+f(k)) \\ &=\sum_{r=1}^{s-1} \sum_{2^{r-1} \leqslant k < 2^{r}}(k+f(k))+\sum_{s^{s}-1 \leq k \leqslant n}(k+f(k))=\\ &=\sum_{r=1}^{s-1} s^{r-1} \times\left(2^{r}-1\right)+\left(n-2^{s-1}+1\right) \times\left(2^{s}-1\right)=\\ &=\sum_{r=1}^{s-1} 2^{2 r-1}-\sum_{r=1}^{s-1} 2^{r-1}+\left(n-2^{s-1}+1\right)\left(2^{s}-1\right)=\\ &=\frac{2}{3}\left(4^{s-1}-1\right)-\left(2^{s-1}-1\right)+\left(2^{s}-1\right) n-2^{s-1}+3 \times 2^{s-1}-1=\\ &=\left(2^{s}-1\right) n-\frac{1}{3} 4^{s}+2^{s}-\frac{2}{3}. \end{align*}} Và khi đó { \begin{align*} \frac{n^{2}}{4}-\sum_{k=1}^{n} f(k) &=\frac{n^{2}}{4}-\left(\left(2^{s}-1\right) n-\frac{1}{3} 4^{s}+2^{s}-\frac{2}{3}-\frac{n(n+1)}{2}\right)=\\ &=\frac{3}{4} n^{2}-\left(2^{s}-\frac{3}{2}\right) n+\frac{1}{3} 4^{s}-2^{s}+\frac{2}{3}=\\ &=\frac{3}{4}\left(n-\frac{2^{s-1}-2}{3}\right)\left(n-\frac{2^{s+1}-4}{3}\right). \end{align*}} Để ý rằng hiệu của hai nhân tử cuối cùng nhỏ hơn $1$, và một trong số chúng sẽ là số nguyên: $\dfrac{2^{s+1}-2}{3}$ là số nguyên nếu $s$ chẵn, và $\dfrac{2^{s+1}-4}{3}$ là số nguyên nếu $s$ lẻ. Chính vì thế, một trong số chúng phải bằng $0$, dẫn đến tích bằng $0$, hoặc cả hai nhân tử đều phải cùng dấu, dẫn đến tích luôn luôn dương. Điều này giải quyết bài toán và cho thấy rằng đẳng thức xảy ra khi $n=\dfrac{2^{s+1}-2}{3}$ (nếu $s$ lẻ) hoặc $n=\dfrac{2^{s+1}-4}{3}$ (nếu $s$ chẵn).