Binary multiples of three

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Binary multiples of three

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: TSTST 2024, problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

71 posts

#1 h Jun 24, 2024, 6:39 PM • 1 Y

Y by Mathandski

For a positive integer $k$ , let $s(k)$ denote the number of $1$ s in the binary representation of $k$ . Prove that for any positive integer $n$ ,
$\sum_{i=1}^{n}(-1)^{s(3i)} > 0.$ Holden Mui

This post has been edited 1 time. Last edited by tapir1729, Jun 24, 2024, 9:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

254 posts

#2 h Jun 24, 2024, 6:44 PM • 11 Y

Y by ihatemath123, Sedro, sami1618, aidan0626, iamnotgentle, OronSH, Ritwin, Diaoest, MatSeFner, CyclicISLscelesTrapezoid, Mathandski

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.

Solution A

Solution B

Solution C

This post has been edited 3 times. Last edited by The_Turtle, Jun 25, 2024, 5:50 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#3 h Jun 24, 2024, 6:54 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1600 posts

#4 h Jun 24, 2024, 7:51 PM

Y by

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).

This post has been edited 1 time. Last edited by MarkBcc168, Jun 24, 2024, 7:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1022 posts

kred9

#5 h Jun 24, 2024, 8:20 PM • 1 Y

Y by IAmTheHazard

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}$ .
Remark 2. Of course, as soon as I read this problem, I thought of the following problem:

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

Attachments:

This post has been edited 1 time. Last edited by kred9, Jun 24, 2024, 8:21 PM
Reason: improved readability

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

224 posts

#6 h Jun 24, 2024, 11:28 PM • 4 Y

Y by GrantStar, OronSH, khina, CyclicISLscelesTrapezoid

Bonus:

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

308 posts

#7 h Jun 25, 2024, 4:10 AM • 4 Y

Y by YaoAOPS, yofro, IAmTheHazard, Phorphyrion

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.

This post has been edited 7 times. Last edited by pikapika007, Jun 25, 2024, 4:17 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5006 posts

#8 h Jun 26, 2024, 9:29 PM

Y by

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.

This post has been edited 1 time. Last edited by IAmTheHazard, Jun 26, 2024, 9:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

776 posts

#9 h May 21, 2025, 4:28 AM

Y by

Subjective Difficulty Rating

The Sol 3 version of the lemma can be proved with the Sol 2 genfunc idea too

The_Turtle wrote:

Lemma. For any every integer $d$ , $S_r(0, 2^d)$ is given by
$\begin{align*} S_0(0, 2^d) &= \begin{cases} 3^{\frac{d-1}{2}} & \text{$d$ odd} \\ 2 \cdot 3^{\frac{d-2}{2}} & \text{$d$ even} \end{cases} \\ S_1(0, 2^d) &= \begin{cases} -3^{\frac{d-1}{2}} & \text{$d$ odd} \\ -3^{\frac{d-2}{2}} & \text{$d$ even} \end{cases} \\ S_2(0, 2^d) &= \begin{cases} 0 & \text{$d$ odd} \\ -2 \cdot 3^{\frac{d-2}{2}} & \text{$d$ even} \end{cases} \end{align*}$

Note that $\overline{d_1 d_2 \dots d_n} \equiv a \pmod{3}$ if and only if,
$d_n - d_{n-1} + d_{n-2} - \dots \equiv a \pmod{3}$ Furthermore, the sum of digits is even if and only if,
$d_1 + d_2 + \dots + d_n \equiv 0 \pmod{2}$ $\iff d_n - d_{n-1} + d_{n-2} - \dots \equiv 0 \pmod{2}$ Both are satisfied if and only if $d_n - d_{n-1} + d_{n-2} - \dots \equiv$ some $b$ mod 6. We may then use one of the polynomials,
$f(x) = x^{-b} (x+1)^{\frac{n+1}{2}} (\frac1x + 1)^{\frac{n-1}{2}}$ $f(x) = x^{-b} (x+1)^{\frac{n}{2}} (\frac1x + 1)^{\frac{n}{2}}$ Depending on parity of $n$ . Using roots of unity filters...

Ends up being a pretty bashy 5-page writeup.

This post has been edited 4 times. Last edited by Mathandski, May 21, 2025, 4:28 PM
Reason: rerate MOHs

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a