My problem! Original problem statement wrote: Let $n$ be a positive integer. Prove that among the first $n$ multiples of three, there are more numbers with an even number of 1s in binary than numbers with an odd number of 1s in binary.

Badly cooked writeup, dm if fakesolve. $k \le 2$ is obvious. We now claim that \[ a_n = \sum_{i=1}^n (-1)^{s(3i)} \ge 3 \]for all $k \ge 3$. Take the base case of $k = 3, \dots, 11$. Claim: We have that \[ \sum_{i=0, 3 \mid (i+j)}^{2^{2n}-1} (-1)^{s(i)} = \varepsilon(j) \cdot 3^{n-1} \]where $\varepsilon(3k) = 2, \varepsilon(3k+1) = \varepsilon(3k+2) = -1$. Proof. Take $(1 + xy)^n(1 + xy^2)^n$, ROUF of degree $3$ on $y$ and sub $x = -1$. $\blacksquare$ Then, for a fixed $k = 2^{2a} b + r, j \in \{0, 1, 2\}, r \le 2^a - 1$, we have that \begin{align*} \sum_{i=0, 3 \mid i}^{2^{2a} b + r} (-1)^{s(3i)} &= \sum_{i=0}^{b} \sum_{j=0, 3 \mid 2^a i + j}^{\min\{2^{2a} - 1, r\}} (-1)^{s(i) + s(j)} \\ &\ge \sum_{i=0}^{b} \varepsilon(i) (-1)^{s(i)} 3^{a-1} - (2^{2a} - 1) \\ &\ge \sum_{i=0}^{b} (\varepsilon(i) + 1) (-1)^{s(i)} 3^{a-1} - (3^{a-1} + 2^{2a} - 1) \\ &= \sum_{i=0, 3 \mid i}^{b} (-1)^{s(i)} 3^a - (3^{a-1} + 2^{2a} - 1) = 3^a \cdot a_b - (3^{a-1} + 2^{2a} - 1) \\ \end{align*}where $r = k - 2^a i$ is a remainder and $t \in \{0, 1, 2\}$ Then note that if $a_b \ge 3$ and $a = 1$, it follows that $3^a \cdot a_b - (3^{a-1} + 2^a - 1) \ge 3$. The result follows by induction.

Probably a very bad writeup, but whatever. We define $$S_r(a,b) = \sum_{\substack{n\in [a,b) \\ n\equiv r\ (\text{mod } 3)}} (-1)^{s_2(n)} \quad\text{and}\quad S_r(n) = S_r(0,n).$$Notice the use of half-open interval so that $S_r(a,c) =S_r(a,b)+S_r(b,c)$. The problem is equivalent to showing that $S_0(n+1)>1$ for all $n$ that is a multiple of $3$. Lemma. For any positive integer $n$, the following table displays the values of $S_i(2^n)$ for $i=0,1,2$. $$\begin{tabular}{c|ccc} $n$ & $S_0(2^n)$ & $S_1(2^n)$ & $S_2(2^n)$ \\ \hline $2k-1$ & $3^{k-1}$ & $-3^{k-1}$ & 0 \\ $2k$ & $2\cdot 3^{k-1}$ & $-3^{k-1}$ & $-3^{k-1}$ \end{tabular}$$ Proof. Routine computation, either by induction or by generating functions. $\blacksquare$ We will now prove the problem. Take a binary expansion of $n+1$: $$n+1 = a_\ell\cdot 2^\ell+ a_{\ell-1}\cdot 2^{\ell-1} + \dots + a_0\cdot 2^0 \quad a_i\in\{0,1\}$$We also define $$t_{\ell+1}=0 \qquad t_i = a_\ell\cdot 2^\ell + a_{\ell-1}\cdot 2^{\ell-1} + \dots + a_i\cdot 2^i.$$Thus, we may split the summation $S_0(n)$ into blocks $$S_0(n) = \sum_{i=0}^{\ell} S_0(t_{i+1}, t_i) = \sum_{i=0}^{\ell} T_i,$$where $T_i = S_0(t_{i+1}, t_i) = S_0(t_{i+1}, t_{i+1}+a_i\cdot 2^i)$. Observe that if $a_i=0$, then $T_i=0$. For nonzero blocks, the block in sum $T_i$ is of the size $2^{a_i}$, so we may apply the above lemma. However, we have the following claim that blocks some possibilities. Claim. For any $k$, we have $T_{2k-1} + T_{2k} \geq -2\cdot 3^{k-1}$. Proof. From the lemma, $T_i$ must correspond to one entry of the table in the lemma, its negation, or zero (if $a_i=0$), depending on the parity of $s_2(t_i)$ and $t_i\bmod 3$. In particular, to violate the inequality, we must have $$a_{2k-1}=a_{2k}=1,\quad T_{2k-1} = -3^{k-1},\quad T_{2k} = -2\cdot 3^{k-1}.$$We show that this is impossible. The last equality implies $t_{2k+1}\equiv 0\pmod 3$ and $s_2(t_{2k+1})$ is even. Thus, $s_2(t_{2k})$ is odd and $t_{2k} = t_{2k+1}+2^{2k}\equiv 1\pmod 3$. This means that when counting $S_0(t_{2k}, t_{2k}+2^{2k-1})$, the trailing $2k-1$ digits must be $2\pmod 3$ to count all multiples of $3$. This forces $T_{2k-1}=S_0(t_{2k}, t_{2k}+2^{2k-1}) = 0$ by the table, a contradiction. $\blacksquare$ The claim gives the following bounds: \begin{align*} T_1 + T_2 &\geq -2 \\ T_3 + T_4 &\geq -2\cdot 3^1 \\ T_5 + T_6 &\geq -2\cdot 3^2 \\ &\vdots \end{align*}Moreover, note that $T_0 = S_0(n,n+1) \geq -1$. Now, we split into two cases. If $\boldsymbol \ell$ is even, then set $\ell=2m$, so $$T_{2m} = 2\cdot 3^m,\qquad T_{2m-1} \in \{0, S_0(2^{2m}, 2^{2m}+2^{2m-1})\} = 0,$$so we have \begin{align*} S_0(n+1) &=T_0+\dots+T_{\ell}\\ &\geq 2\cdot 3^m - 2(3^{m-1}+3^{m-2}+\dots+3^0)-1\\ &= 3^m-1\geq 2. \end{align*} If $\boldsymbol \ell$ is odd, then set $\ell=2m+1$, so $$T_{2m+1} = 2\cdot 3^{m+1},\quad T_{2m} \in \{0, S_0(2^{2m+1}, 2^{2m+1}+2^{2m})\} \in \{0, 3^m\},$$and $T_{2m-1}\geq -3^m$. Thus, we have \begin{align*} S_0(n+1) &=T_0+\dots+T_{\ell} \\ &\geq 2\cdot 3^{m+1} - 3^m - 2(3^{m-1}+3^{m-2}+\dots+3^0) - 1 \\ &= 3^m \geq 3. \end{align*}(Check $m=0$ manually).

Very nice. Let $S(n) = \sum_{i=1}^n (-1)^{s(3i)}$. First, we claim that $S(8k) = 3S(2k)$ for all positive integers $k$. Proof. Consider 8 consecutive multiples of 3. Their last three digits look like this: $000, 011, 110, 001, 100, 111, 010, 101$. Now, partition those 8 tails into the three sets $\{000, 011, 110\}, \{001, 100, 111\}, \{010, 101\}$. In each of the sets, the heads of each of those tails will be the same. Therefore, in the first set, either all three numbers have an odd digit sum or an even digit sum. Similarly, in the second set, all three numbers have an odd digit sum or an even digit sum, and in the third set, the digit sums are opposite parity. Therefore, the sum of $(-1)^{s(j)}$ is just \begin{align*} \sum_{j = 8k}^{8k+7} (-1)^{s(j)} &= (-1)^{s(\text{head}000)}+(-1)^{s(\text{head}011)}+(-1)^{s(\text{head}110)}+(-1)^{s(\text{head}001)}+(-1)^{s(\text{head}100)}+(-1)^{s(\text{head}111)}+(-1)^{s(\text{head}010)}+(-1)^{s(\text{head}101)} \\ &= \left((-1)^{s(\text{head}000)}+(-1)^{s(\text{head}011)}+(-1)^{s(\text{head}110)}\right)+\left((-1)^{s(\text{head}001)}+(-1)^{s(\text{head}100)}+(-1)^{s(\text{head}111)}\right)+\left((-1)^{s(\text{head}010)}+(-1)^{s(\text{head}101)} \right) \\ &= 3\left((-1)^{s(\text{head}000)} + (-1)^{s(\text{head}100)}\right) \\ &= 3\left((-1)^{s(\text{head}0)} + (-1)^{s(\text{head}1)}\right). \\ \end{align*} The claim is quite apparent to see from here, because we have reduced every set of 8 consecutive numbers into a set of 2 consecutive numbers, while multiplying by $3$. $\blacksquare$ Base cases show that all of the $S(i)$ from 1 to 8 are positive. Now by $S(8k) = 3S(2k) > 0$ for $k\ge 2$. Additionally, $S(2k)$ is even and positive, so $S(8k) \ge 3\cdot 2 = 6$. Furthermore, $S(8k + 8)$ is also at least $6$, meaning $S(8k+6)$ is also at least $6$. It is obvious now that $S(8k+3)$ can't be less than $3$, since $S(8k+3) = S(8k) \pm 3$. We are done. $\square$ Remark. We can actually improve on many of these bounds quite easily, since $S(k) \ge 3$ for all $k \ge 3$ implies that $S(8k) = 3S(2k) \ge 12$, since $S(2k)$ must be even and at least $3$ for all $k\ge 2$. Therefore $S(8k+3) \ge 9$ for all $k \ge 2$. Then we can repeat in this fashion to get larger and larger bounds on $S(k)$. The graph of $S$ also looks interesting, attached below from $n = 1$ to $2^{23}$.

2022 HMMT November Guts #26 wrote: Compute the smallest multiple of 63 with an odd number of ones in its base two representation. Proposed by: Holden Mui

Bonus: Prove that \[\sum_{i=1}^n (-1)^{s(1434i)} > 0\]for all positive integers $n$.

Thanks to YaoAOPS for the writeup. Define \[ f(k) = \sum_{i=0, i \equiv k \pmod{3}}^{k} (-1)^i. \] This $f$ satisfies the same conditions as in ISL 2008 A4 by direct checking, so using post #10 there, we get $f(3p) \ge 2$ for $p \ge 2$. Since we also have $f(3) \ge 2$, we are done.

you thought 5 inductive cases was bad? well now i have $\Theta(\log n)$. too lazy to do an actual writeup small $n$ is easy. now note that $3(2^n-1)$ in binary is $10\underbrace{1\ldots 1}_{n-2 \text{ ones}}01$ except for $n=1$ where it's $11$. the idea is to split the binary rep of $k$ into blocks of consecutive ones and note that the interaction (via carrying) between different blocks upon multiplication by $3$ is pretty limited. we are going to first WLOG $n$ is odd and split the numbers at most $n$ into groups by the last few digits: $00$ and $01$ are in a group If $B$ is a block of size at least $2$, then $B0$ and $B1$ are in a group $010$ and $011$ are in a group In the first group we pair up $s00$ and $s01$ and note that these both have the same digit sum parity as $s$ does ($s$ is a binary string) and we can induct down (handle $1$ separately; $3$ has even digit sum anyways). In the latter note that $s0$ and $s1$ will actually have opposite digit sum parity because of what $3(2^n-1)$ looks like: importantly, because $B$ has at least $2$ digits, changing between $B0$ and $B1$ doesn't change the largest $1$ bit's position so the behavior of carrying doesn't change. Thus these numbers don't contribute anything in either direction. The last case is a bit of a headache because now carries start to occur. Numbers in this class either end in $110101\ldots 0101d$ or $00101\ldots 0101d$ where $d$ is a single digit. Consider a given choice of digits except for the rightmost. Simulating the carrying process, if the number falls in the former case it's not hard to see that the two choice of $d$ result in different digit sum parities, and in the latter the two choices of $d$ have the same digit sum parity. Moreover $11 \times 00101\ldots 0101d$ actually has even digit sum, so $s00101\ldots 0101d$ and $s$ have the same digit sum and we can once again induct down (again handling $s=0$ separately since $00101\ldots 0101d$ yields even digit sum anyways). In summary, some groups/"subgroups" we split into have more even digit sums than odds (these are the ones where we induct), and some have exactly the same, so the desired claim is true for $n$ as well. We still need to handle $n$ even, but for non-tiny $n$ this can simply be achieved by looking at our proof for $n-1$ and noting that e.g. the $00$ and $01$ group will actually yield at least $3$ more even sums than odd and $3-1>0$ still.