Plan ahead for the next school year. Schedule your class today!

G
Topic
First Poster
Last Poster
k a July Highlights and 2025 AoPS Online Class Information
jwelsh   0
Jul 1, 2025
We are halfway through summer, so be sure to carve out some time to keep your skills sharp and explore challenging topics at AoPS Online and our AoPS Academies (including the Virtual Campus)!

[list][*]Over 60 summer classes are starting at the Virtual Campus on July 7th - check out the math and language arts options for middle through high school levels.
[*]At AoPS Online, we have accelerated sections where you can complete a course in half the time by meeting twice/week instead of once/week, starting on July 8th:
[list][*]MATHCOUNTS/AMC 8 Basics
[*]MATHCOUNTS/AMC 8 Advanced
[*]AMC Problem Series[/list]
[*]Plus, AoPS Online has a special seminar July 14 - 17 that is outside the standard fare: Paradoxes and Infinity
[*]We are expanding our in-person AoPS Academy locations - are you looking for a strong community of problem solvers, exemplary instruction, and math and language arts options? Look to see if we have a location near you and enroll in summer camps or academic year classes today! New locations include campuses in California, Georgia, New York, Illinois, and Oregon and more coming soon![/list]

MOP (Math Olympiad Summer Program) just ended and the IMO (International Mathematical Olympiad) is right around the corner! This year’s IMO will be held in Australia, July 10th - 20th. Congratulations to all the MOP students for reaching this incredible level and best of luck to all selected to represent their countries at this year’s IMO! Did you know that, in the last 10 years, 59 USA International Math Olympiad team members have medaled and have taken over 360 AoPS Online courses. Take advantage of our Worldwide Online Olympiad Training (WOOT) courses
and train with the best! Please note that early bird pricing ends August 19th!
Are you tired of the heat and thinking about Fall? You can plan your Fall schedule now with classes at either AoPS Online, AoPS Academy Virtual Campus, or one of our AoPS Academies around the US.

Our full course list for upcoming classes is below:
All classes start 7:30pm ET/4:30pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Wednesday, Jul 16 - Oct 29
Sunday, Aug 17 - Dec 14
Tuesday, Aug 26 - Dec 16
Friday, Sep 5 - Jan 16
Monday, Sep 8 - Jan 12
Tuesday, Sep 16 - Jan 20 (4:30 - 5:45 pm ET/1:30 - 2:45 pm PT)
Sunday, Sep 21 - Jan 25
Thursday, Sep 25 - Jan 29
Wednesday, Oct 22 - Feb 25
Tuesday, Nov 4 - Mar 10
Friday, Dec 12 - Apr 10

Prealgebra 2 Self-Paced

Prealgebra 2
Friday, Jul 25 - Nov 21
Sunday, Aug 17 - Dec 14
Tuesday, Sep 9 - Jan 13
Thursday, Sep 25 - Jan 29
Sunday, Oct 19 - Feb 22
Monday, Oct 27 - Mar 2
Wednesday, Nov 12 - Mar 18

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Tuesday, Jul 15 - Oct 28
Sunday, Aug 17 - Dec 14
Wednesday, Aug 27 - Dec 17
Friday, Sep 5 - Jan 16
Thursday, Sep 11 - Jan 15
Sunday, Sep 28 - Feb 1
Monday, Oct 6 - Feb 9
Tuesday, Oct 21 - Feb 24
Sunday, Nov 9 - Mar 15
Friday, Dec 5 - Apr 3

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Wednesday, Jul 2 - Sep 17
Sunday, Jul 27 - Oct 19
Monday, Aug 11 - Nov 3
Wednesday, Sep 3 - Nov 19
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Friday, Oct 3 - Jan 16
Sunday, Oct 19 - Jan 25
Tuesday, Nov 4 - Feb 10
Sunday, Dec 7 - Mar 8

Introduction to Number Theory
Tuesday, Jul 15 - Sep 30
Wednesday, Aug 13 - Oct 29
Friday, Sep 12 - Dec 12
Sunday, Oct 26 - Feb 1
Monday, Dec 1 - Mar 2

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Friday, Jul 18 - Nov 14
Thursday, Aug 7 - Nov 20
Monday, Aug 18 - Dec 15
Sunday, Sep 7 - Jan 11
Thursday, Sep 11 - Jan 15
Wednesday, Sep 24 - Jan 28
Sunday, Oct 26 - Mar 1
Tuesday, Nov 4 - Mar 10
Monday, Dec 1 - Mar 30

Introduction to Geometry
Monday, Jul 14 - Jan 19
Wednesday, Aug 13 - Feb 11
Tuesday, Aug 26 - Feb 24
Sunday, Sep 7 - Mar 8
Thursday, Sep 11 - Mar 12
Wednesday, Sep 24 - Mar 25
Sunday, Oct 26 - Apr 26
Monday, Nov 3 - May 4
Friday, Dec 5 - May 29

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)
Sat & Sun, Sep 13 - Sep 14 (1:00 - 4:00 PM PT/4:00 - 7:00 PM ET)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22
Friday, Aug 8 - Feb 20
Tuesday, Aug 26 - Feb 24
Sunday, Sep 28 - Mar 29
Wednesday, Oct 8 - Mar 8
Sunday, Nov 16 - May 17
Thursday, Dec 11 - Jun 4

Intermediate Counting & Probability
Sunday, Sep 28 - Feb 15
Tuesday, Nov 4 - Mar 24

Intermediate Number Theory
Wednesday, Sep 24 - Dec 17

Precalculus
Wednesday, Aug 6 - Jan 21
Tuesday, Sep 9 - Feb 24
Sunday, Sep 21 - Mar 8
Monday, Oct 20 - Apr 6
Sunday, Dec 14 - May 31

Advanced: Grades 9-12

Calculus
Sunday, Sep 7 - Mar 15
Wednesday, Sep 24 - Apr 1
Friday, Nov 14 - May 22

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Wednesday, Sep 3 - Nov 19
Tuesday, Sep 16 - Dec 9
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Oct 6 - Jan 12
Thursday, Oct 16 - Jan 22
Tues, Thurs & Sun, Dec 9 - Jan 18 (meets three times a week!)

MATHCOUNTS/AMC 8 Advanced
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Tuesday, Aug 26 - Nov 11
Thursday, Sep 4 - Nov 20
Friday, Sep 12 - Dec 12
Monday, Sep 15 - Dec 8
Sunday, Oct 5 - Jan 11
Tues, Thurs & Sun, Dec 2 - Jan 11 (meets three times a week!)
Mon, Wed & Fri, Dec 8 - Jan 16 (meets three times a week!)

AMC 10 Problem Series
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 10 - Nov 2
Thursday, Aug 14 - Oct 30
Tuesday, Aug 19 - Nov 4
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Mon, Wed & Fri, Oct 6 - Nov 3 (meets three times a week!)
Tue, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 10 Final Fives
Friday, Aug 15 - Sep 12
Sunday, Sep 7 - Sep 28
Tuesday, Sep 9 - Sep 30
Monday, Sep 22 - Oct 13
Sunday, Sep 28 - Oct 19 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, Oct 8 - Oct 29
Thursday, Oct 9 - Oct 30

AMC 12 Problem Series
Wednesday, Aug 6 - Oct 22
Sunday, Aug 10 - Nov 2
Monday, Aug 18 - Nov 10
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Tues, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 12 Final Fives
Thursday, Sep 4 - Sep 25
Sunday, Sep 28 - Oct 19
Tuesday, Oct 7 - Oct 28

AIME Problem Series A
Thursday, Oct 23 - Jan 29

AIME Problem Series B
Tuesday, Sep 2 - Nov 18

F=ma Problem Series
Tuesday, Sep 16 - Dec 9
Friday, Oct 17 - Jan 30

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT


Programming

Introduction to Programming with Python
Thursday, Aug 14 - Oct 30
Sunday, Sep 7 - Nov 23
Tuesday, Dec 2 - Mar 3

Intermediate Programming with Python
Friday, Oct 3 - Jan 16

USACO Bronze Problem Series
Wednesday, Sep 3 - Dec 3
Thursday, Oct 30 - Feb 5
Tuesday, Dec 2 - Mar 3

Physics

Introduction to Physics
Tuesday, Sep 2 - Nov 18
Sunday, Oct 5 - Jan 11
Wednesday, Dec 10 - Mar 11

Physics 1: Mechanics
Sunday, Sep 21 - Mar 22
Sunday, Oct 26 - Apr 26
0 replies
jwelsh
Jul 1, 2025
0 replies
Couples at a round table
Stear14   0
3 minutes ago
(a) $\ $ Consider $\ N\ $ married couples seated around a circular table, with each couple initially positioned diametrically opposite each other. In each minute, any number of disjoint pairs of adjacent individuals may simultaneously swap seats. Prove that $\ \lfloor N/2 \rfloor\ $ minutes are required to ensure that every married couple is seated next to each other.

(b) $\ $ Consider $\ N\ $ married couples seated around a circular table. Each minute, a number of disjoint pairs of adjacent people may simultaneously swap seats. Determine the minimum number of minutes required to guarantee that, no matter the initial seating arrangement, every married couple ends up seated together.

Dictum: Inspired by ISL 2024 C3
0 replies
Stear14
3 minutes ago
0 replies
IMO Shortlist 2014 G3
hajimbrak   47
N 8 minutes ago by eg4334
Let $\Omega$ and $O$ be the circumcircle and the circumcentre of an acute-angled triangle $ABC$ with $AB > BC$. The angle bisector of $\angle ABC$ intersects $\Omega$ at $M \ne B$. Let $\Gamma$ be the circle with diameter $BM$. The angle bisectors of $\angle AOB$ and $\angle BOC$ intersect $\Gamma$ at points $P$ and $Q,$ respectively. The point $R$ is chosen on the line $P Q$ so that $BR = MR$. Prove that $BR\parallel AC$.
(Here we always assume that an angle bisector is a ray.)

Proposed by Sergey Berlov, Russia
47 replies
hajimbrak
Jul 11, 2015
eg4334
8 minutes ago
Next term is sum of three largest proper divisors
vsamc   13
N 15 minutes ago by amir_ali
Source: 2025 IMO P4
A proper divisor of a positive integer $N$ is a positive divisor of $N$ other than $N$ itself.

The infinite sequence $a_1, a_2, \cdots$ consists of positive integers, each of which has at least three proper divisors. For each $n\geq 1$, the integer $a_{n+1}$ is the sum of the three largest proper divisors of $a_n$.

Determine all possible values of $a_1$.

Proposed by Paulius Aleknavičius, Lithuania
13 replies
vsamc
Yesterday at 9:53 PM
amir_ali
15 minutes ago
IMO Shortlist 2012, Algebra 5
lyukhson   37
N 16 minutes ago by bin_sherlo
Source: IMO Shortlist 2012, Algebra 5
Find all functions $f:\mathbb{R} \rightarrow \mathbb{R}$ that satisfy the conditions
\[f(1+xy)-f(x+y)=f(x)f(y) \quad \text{for all } x,y \in \mathbb{R},\]
and $f(-1) \neq 0$.
37 replies
lyukhson
Jul 29, 2013
bin_sherlo
16 minutes ago
A robust fact about 5-cycles
math_explorer   2
N May 2, 2016 by math_explorer
[quote]Lemma 3. (Barrington, 1986) There are two five-cycles $\sigma_1$ and $\sigma_2$ in $S_5$ whose commutator is a five-cycle. (The commutator of $a$ and $b$ is $aba^{-1}b^{-1}$.)

Proof. $(12345)(13542)(54321)(24531) = (13254).$[/quote]

Someday I want to write a paper and include a lemma with a proof like this.

Uh, is it just me or is this proof actually incorrect...? I keep getting $(14352)$. I think Mr. Barrington composed his permutations the wrong way. (Fortunately for complexity theory, the lemma is robust to this issue! :P)
2 replies
math_explorer
May 2, 2016
math_explorer
May 2, 2016
Deep geometric facts
math_explorer   2
N Apr 27, 2016 by math_explorer
From my survey in progress.

[quote]Lemma. For any $k$, there exists a configuration of $k$ half-planes such that every half-plane contains some point not in any other half-plane.

Proof. Fix a circle and draw $k$ distinct tangents to it. For each tangent, take the half-plane defined by it that does not contain the circle.

Corollary. A [communication complexity] protocol exists for computing EQUALITY with private randomness and positive bias in which Alice communicates 2 bits to Bob and Bob outputs the answer.[/quote]

Every time I think I might never need to think about Euclidean geometry again...
2 replies
math_explorer
Apr 27, 2016
math_explorer
Apr 27, 2016
No more topics!
Binary multiples of three
tapir1729   8
N May 21, 2025 by Mathandski
Source: TSTST 2024, problem 5
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
8 replies
tapir1729
Jun 24, 2024
Mathandski
May 21, 2025
Binary multiples of three
G H J
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.
tapir1729
71 posts
#1 • 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.
The_Turtle
254 posts
#2 • 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.
YaoAOPS
1629 posts
#3
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.
MarkBcc168
1631 posts
#4
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.
kred9
1022 posts
#5 • 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.
a1267ab
225 posts
#6 • 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.
pikapika007
308 posts
#7 • 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.
IAmTheHazard
5006 posts
#8
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.
Mathandski
776 posts
#9
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
=
a