Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

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, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
interesting functional
Pomegranat   2
N 23 minutes ago by Pomegranat
Source: I don't know sorry
Find all functions \( f : \mathbb{R}^+ \to \mathbb{R}^+ \) such that for all positive real numbers \( x \) and \( y \), the following equation holds:
\[
\frac{x + f(y)}{x f(y)} = f\left( \frac{1}{y} + f\left( \frac{1}{x} \right) \right)
\]
2 replies
Pomegranat
2 hours ago
Pomegranat
23 minutes ago
Function equation algebra
TUAN2k8   1
N 25 minutes ago by TUAN2k8
Source: Balkan MO 2025
Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that for all $x \in \mathbb{R}$ and $y \in \mathbb{R}$,
\begin{align}
f(x+yf(x))+y=xy+f(x+y).
\end{align}
1 reply
TUAN2k8
40 minutes ago
TUAN2k8
25 minutes ago
Functional equation with a twist (it's number theory)
Davdav1232   1
N 25 minutes ago by NO_SQUARES
Source: Israel TST 8 2025 p2
Prove that for all primes \( p \) such that \( p \equiv 3 \pmod{4} \) or \( p \equiv 5 \pmod{8} \), there exist integers
\[
1 \leq a_1 < a_2 < \cdots < a_{(p-1)/2} < p
\]such that
\[
\prod_{\substack{1 \leq i < j \leq (p-1)/2}} (a_i + a_j)^2 \equiv 1 \pmod{p}.
\]
1 reply
Davdav1232
Thursday at 8:32 PM
NO_SQUARES
25 minutes ago
Coolabra
Titibuuu   3
N an hour ago by sqing
Let \( a, b, c \) be distinct real numbers such that
\[
a + b + c + \frac{1}{abc} = \frac{19}{2}
\]Find the maximum possible value of \( a \).
3 replies
Titibuuu
Today at 2:21 AM
sqing
an hour ago
HMMT Masters Round
rrusczyk   0
Feb 16, 2011
For those of you college students who miss the camaraderie and challenge of on-site math competitions, the Harvard-MIT Math Tournament offers a college competition. Here's a note from Maria Monks and Rishi Gupta, AoPSers who are running the competition:

[quote="Maria Monks and Rishi Gupta"]
The HMMT (Harvard-MIT Math Tournament) Masters Round is an annual math contest for undergraduates, written by former HMMT directors and problem czars. The contest aims to bring the spirit of competition and the art of problem solving into higher mathematics, with challenging problems in abstract algebra, analysis, topology, combinatorics, calculus, linear algebra, and number theory at the undergraduate level. The Masters Round will consist of a 4 hour, proof-based test with 10 questions of varying difficulty.

Any student currently enrolled in an undergraduate institution is eligible to compete, and awards are given to the top 7 undergraduates. Additionally, there will be prizes awarded for particularly clever or elegant solutions. College graduates may also compete, but they will not be eligible for awards.

The team scoring is as follows. Any undergraduate institution with more than five participating undergraduates automatically becomes a team, and that team comprises all the undergraduates from that school. A school's team score is the sum of the ranks of the top 5 individuals from that school, after all non-team participants are removed from the results. Ties are broken by the 6th place individuals from the respective schools.

Problem submissions from college graduates are welcome. Please send any ideas you may have to hmmt-masters@mit.edu. College graduates are also invited to help grade after the contest on April 2, including those who are competing unofficially, and free dinner will be provided for volunteers.

The second annual Masters Round will be held at Harvard University in the Science Center, Hall A, on April 2, 2011. For details and to sign up, please visit http://hmmt.mit.edu/masters. Hope to see you there![/quote]
0 replies
rrusczyk
Feb 16, 2011
0 replies
AMC changes
DPatrick   3
N Dec 2, 2010 by dragon96
Today the American Mathematics Competitions announced changes to the AMC10/12 - AIME - USA(J)MO series of contests for high school students.

There are two major changes:

1. The cutoff score to advance from the AMC10 to the AIME is still 120, but in the event that fewer than 2.5% of all students score 120 or higher, they will lower the cutoff score so that the top 2.5% of students advance. (In previous years this percentage was 1%.) (Also, no changes for advancement from AMC12 to AIME: it's still 100 or the top 5%.)

2. Students can qualify for the USAMO only by taking the AMC12. Students can qualify for the USAJMO only by taking the AMC10. If a student takes both the AMC10 and AMC12 and qualifies for both olympiads, he or she must take the USAMO.

Official rules are on the AMC's website. Discussion continues on our AMC forum.
3 replies
DPatrick
Dec 1, 2010
dragon96
Dec 2, 2010
Math Prize for Girls
DPatrick   1
N Nov 15, 2010 by fprosk
Congratulations to all the winners and participants in the 2010 Math Prize for Girls, which was held this past weekend in New York.

Ravi Boppana, the director of the contest, has very graciously posted all of the problems on our forum.
1 reply
DPatrick
Nov 15, 2010
fprosk
Nov 15, 2010
USAMTS 2010-11 has started!
DPatrick   0
Oct 8, 2010
The 2010-11 edition of the USA Mathematical Talent Search is now underway. The Round 1 problems have been posted on http://www.usamts.org, and the deadline to submit solutions is November 22.

The USAMTS is different from most math contests: you get several weeks to think about the problems. You can use any resources you like to help you explore the problems (other than asking other people). Then you write up full solutions showing all your work. You'll not only receive scores for your work, but you'll also receive individual feedback on your solutions.

For those who have participated in the past, you'll notice a new format for 2010-11: we're doing 2 rounds of 6 problems each this year. There are many, many more activities in the math contest universe now as compared to when the USAMTS was founded in the late 1980s, and as such we felt that a more streamlined USAMTS would give students more opportunity to participate in both the USAMTS and in other mathematical activities.
0 replies
DPatrick
Oct 8, 2010
0 replies
International Math Olympiad Problems Now Available
rrusczyk   1
N Jul 9, 2010 by phiReKaLk6781
The problems from the 2010 International Math Olympiad are now available here (in many languages). You can join discussion of the problems on AoPS here. Best of luck to all our community members at the IMO!
1 reply
rrusczyk
Jul 8, 2010
phiReKaLk6781
Jul 9, 2010
No more topics!
Cono Sur Olympiad 2011, Problem 6
Leicich   22
N Mar 30, 2025 by cosinesine
Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ has at most $2$ black cells. Find the maximum amount of black cells that the board may have.
22 replies
Leicich
Aug 23, 2014
cosinesine
Mar 30, 2025
Cono Sur Olympiad 2011, Problem 6
G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leicich
235 posts
#1 • 3 Y
Y by Adventure10, ItsBesi, ktyotaka
Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ has at most $2$ black cells. Find the maximum amount of black cells that the board may have.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
junioragd
314 posts
#2 • 2 Y
Y by Adventure10, Mango247
Easy for 6.The answer is (2*n+1)*(n+1).Just mark the rows 1,2,...2*n+1.Now,example for (n+1)*(2*n+1):Let rows 1,3,5...2*n+1 be black.Now,it is easy to see that the number of black cells in 2 adjacent rows is at most 2*n+2(but iff in both rows we have n+1 cell),or the maximum is 2*n+1(This can be proven very easy,but I don't have enough time).Now,if the number in the first row is n+1,we easy get that the maximum is (n+1)*(2*n+1),if it is n,we get the maximum is (n+1)*(2*n+1)-1,if it is an arbitary integer x different from this two,it is easy to see that maximum is (n+1)*(2*n+1),so we are finished.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
edfearay123
92 posts
#3 • 1 Y
Y by GeoKing
The answer is $(2n+1)$x$(n+1)$. So we separeted the board in sub board $2\times 2$, in L-triminos and $1\times 1$ sub board in this form, for example $n=2$ and $n=3$.

In the diagonal L-triminos and $1\times 1$. It's easy see, we have $n^2$ $2\times 2$, $n$ L-triminos and $(n+1)$ sub board of $1\times 1$. We note that in each $2\times 2$ there are at most $2$ black cells, in each L-triminos there are at most $2$ black cells, and in each $1\times 1$ there is at most $1$ black cell. In total, there are $n^2\times 2+n\times 2+(n+1)\times 1= 2n^2+3n+1=(2n+1)(n+1)$ and this is the answer. The example for all n is colored columns $1,3,5...,2n+1$
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
508669
1040 posts
#4 • 1 Y
Y by starchan
Leicich wrote:
Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ has at most $2$ black cells. Find the maximum amount of black cells that the board may have.

I promise I will write/try to write solution in proper manner that is actually proper proof writing.

I promise I will write/try to write solution in proper manner that is actually proper proof writing.

I promise I will write/try to write solution in proper manner that is actually proper proof writing.

I promise I will write/try to write solution in proper manner that is actually proper proof writing.

I promise I will write/try to write solution in proper manner that is actually proper proof writing.

Dolution : We first make an observation : The condition for coloring are hereditary , i.e, if a coloring of board of size $2k+1$ by $2k+1$ is called as $\mathcal{D}_1$ which satisfies all conditions of the problem, then we can remove last $2$ rows and last $2$ columns and still the condition would be satisfied. We will use this but in the opposite direction, being careful because the converse of the statement I made above doesn't hold true.

We induct on $k$. Let us say that alternative row coloring has been optimal choice of coloring for some $k$, base case $3$ fails to work due to pigeon hole principle as two square cannot cover $2$ spots in every $2$ by $2$ square in the $3$ by $3$ square grid so $\boxed{6}$ is maximum for $k=3$, only way of acheiving it is the column or row coloring. Now, we can see that PHP argument also tells us that best coloring for $2$ by $k$ is $k$ by alternative row or a full column or vice versa.

Now we see that if we combine $2k+1$ by $2k+1$, $2$ by $2k+1$ and $2$ by $2k+3$ rectangle together in a particular manner, we get a $2k+3$ by $2k+3$ square. Now, we know that we have combined three objects will optimal coloring. It seems that overall this huger coloring is also optimal, we'll call this coloring $\mathcal{D}_1$. Also let us call these three rectangle as $a, b, c$ respectively. Suppose there exists better coloring. Then at least one of the rectangles $a, b, c$ of this new coloring has more marked squares than the rectangle in the coloring we claimed to be optimal. This contradicts the fact that $a, b, c$ were given optimal coloring.

Now I'll leave it to the reader in what way should we color these rectangles and then arrange them.
This post has been edited 1 time. Last edited by 508669, Oct 16, 2020, 8:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
arzhang2001
250 posts
#5 • 1 Y
Y by thinkinghard
thats too easy by partitioning the check board you can easily understand the answer is $(n+1)(2n+1)$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
508669
1040 posts
#6
Y by
No I intentionally left the trivial part so the reader just doesn't read and leave
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
oVlad
1746 posts
#7 • 1 Y
Y by hakN
We claim that the answer is $(2n+1)(n+1).$ To prove this, we induct on $n{}.$ The base case is trivial; assume that this bound holds for $n{}.$ We will prove that it also holds for $n+1.{}$

Let the cell on the $i$-th row and $j$-th column be $C_{i,j}$ and split the board into an L-shaped piece $\mathcal{L}$ and a $(2n+1)\times (2n+1)$ board $\mathcal{B}$ with the upper-left vertex $C_{1,3}.$

By the induction hypothesis we can have at most $(2n+1)(n+1)$ black squares in $\mathcal{B}.$ Hence, there are at least $4n+6$ black squares in $\mathcal{L}.$ Now, divide $\mathcal{L}$ into several ($2n+1$, more specifically) $2\times 2$ squares and the four unit squares $C_{2n+3,1},C_{2n+3,2}$ and $C_{2n+2,3},C_{2n+3,3}.$

Observe that any $2\times 2$ square has at most 2 black squares and $\mathcal{L}$ has at least $4n+6$ black squares, hence $C_{2n+3,1},C_{2n+3,2}$ and $C_{2n+2,3},C_{2n+3,3}$ must all be black. However, by a symmetrical decomposition of $\mathcal{L}$ we can deduce that $C_{2n+3,1},C_{2n+2,1}$ and $C_{2n+1,1},C_{2n+1,2}$ must all be black as well.

Hence, the lower-left $2\times 2$ square must have at least $3$ black squares in it, which is a contradiction. Therefore, our bound holds for an $2n+3\times 2n+3$ board as well. Equality can be obtained by a chessboard coloring, where $C_{1,1}$ is black.
This post has been edited 3 times. Last edited by oVlad, Jan 10, 2024, 10:19 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
starchan
1609 posts
#8
Y by
First we will show that amongst $2$ consecutive rows of the board, there are atmost $2n+1$ black cells. Let's forget the rest of the board for now, and we will show that if we only consider the problem's constraints in the subgrid here, it will still give the required result. Consider each location such that the black square is in the bottom and there is a white cell just to the top of it.
Note that we can shift such black cells up without affecting the problem's property.This gives if some cell of the bottom row is black, then the one above it is black as well. So, if there are $2n+2$ cells colored black, (after this movement, the numner of black cells hasn't changed so don't panic) then the first row must be completely black and at least one of the bottom row cells should be black as well. But then if we consider a $2 \times 2$ board containing that bottom cell, it has $3$ black cells, a contradiction. Thus there are at most $2n
+1$ cells as such. Now, divide the original board into $n$ such $2 \times 2n+1$ boards and one $1 \times 2n+1$ array. This immediately gives that there are at most $(n+1)(2n+1)$ black cells in the entire board. And this is achievable, for if we number the rows of the board from $1$ to $2n+1$ and color the odd rows black completely then the board satisfies our conditions and has $(n+1)(2n+1)$ colored cells. Thus the answer to the problem is $(n+1)(2n+1)$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DottedCaculator
7352 posts
#9
Y by
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
554183
484 posts
#10
Y by
I present two solutions out of which one might be completely wrong, so kindly let me know if it is

Solution 1: Induction
I claim that the maximum number of black cells is $(n+1)(2n+1)$. The base case clearly holds true. Now let the assertion hold true for all $n \in \{1,2, \dots, k-1\}$. Partition the $(2k+1) \times (2k+1)$ board into four rectangles, of dimensions $(2k-1) \times (2k-1), 2 \times (2k-1), 2 \times (2k-1), 2 \times 2$ respectively. First note that any $2 \times (2x+1)$ box has a maximum of $2x+2$ black cells in it (divide it into a box of dimension $2 \times 2k$ which cannot have more than $2k$ black cells) with equality when each of the two columns have $x+1$ black cells and each black cell in one column has an adjacent black cell in the other column. Now if the $2 \times 2$ box has $0$ black cells, we get the maximum as $k(2k-1)+2(2k)=2k^2+3k$ which is less than $(k+1)(2k+1)$. If the $2 \times 2$ box has $1$ black cell, the maximum is $2k^2+3k+1$. If it has $2$ black cells, however, one $2 \times (2k-1)$ box is forced to have $2k-1$ black cells (equality can’t ever hold) so the maximum remains the same and we are done.

Solution 2 :
FTSOC assume that some $(2n+1) \times (2n+1)$ box can have at least $(2n+1)(n+1)+1$ black cells while following the given condition. This means that some column has at least $n+2$ black cells. Call such a column good, else call it bad. We make two cases. In the first case, the leftmost column isn’t good. Since we know a good column exists, choose the leftmost one, and pair it with the column on its left, and delete it. So we are left with $(n+1)(2n+1)-(2n+1)+1$ cells and $2n-1$ columns. In general, it is easy to prove that $(n+1)(2n+1)+1-(2n+1)k > (n+1)(2n+1-2k)$ which means that every time we can pair a good column with its adjacent bad column, we can delete them and by php we can always find another good column. Back to the main problem, we just keep choosing the leftmost good column at each step and we can always pair it with an adjacent bad column (in this case just pair every good column with its leftmost column) because no two good columns can be adjacent. Therefore at least $n$ of the box’s columns should be good, and at maximum it can have $(2n+1)n+(2n+1)=(2n+1)(n+1)$ black cells, contradiction. In the second case, the leftmost column is good. As usual, keep choosing the leftmost good column and pair it with its adjacent left column if possible (it might not be if it’s already deleted ; in that case choose the right one). If at some point we are able to pair it with its left column, do that and keep pairing the good columns after that with their left ones. This means we can always pair a good column with an adjacent bad column, so we are done by the same reasoning as in the above case. However if it’s not possible, it would mean that column $1,3, \dots,(2n-1)$ are good which means that the maximum is $n(2n+1)+(2n+1)=(2n+1)(n+1)$, contradiction.


P.S. sorry for the bad writeup :p
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5001 posts
#11
Y by
Forgot to post this lol

The answer is $(n+1)(2n+1)$, which can be achieved by coloring every other row black, starting with the uppermost (so we get $n+1$ colored rows). To show that this is an upper bound I will use induction, with the base case of $n=0$ being clear.
Call the shape formed by removing the top-right $2n-1\times 2n-1$ board from a $2n+1\times 2n+1$ board a "$2n+1$ L". By inductive hypothesis it suffices to show that at most $4n+1$ cells in a $2n+1$ L are black. We again use induction for this. For the base case of $n=1$, divide the $3$ L as such:
[asy]
        draw((0,3)--(2,3));
        draw((0,2)--(3,2));
        draw((0,1)--(3,1));
        draw((0,0)--(3,0));
        draw((0,3)--(0,0));
        draw((1,3)--(1,0));
        draw((2,3)--(2,0));
        draw((3,2)--(3,0));

        draw((0.1,2.9)--(1.9,2.9)--(1.9,1.1)--(0.1,1.1)--cycle, red);
        draw((2.9,0.1)--(2.9,1.9)--(1.1,1.9)--(1.1,0.1)--cycle, blue);
        draw((0.1,0.1)--(0.9,0.1)--(0.9,0.9)--(0.1,0.9)--cycle, green);
[/asy]
Then,
$$\text{\# of black cells} \leq \text{\# of black cells in green} + \text{\# of black cells in red} + \text{\# of black cells in blue} \leq 1+2+2=5,$$as desired. Now, a $2n+1$ L is simply a $2n-1$ L with two $2 \times 2$ squares added to both "ends" of the L, which increases the number of black cells by at most $4$. Therefore, by inductive hypothesis there are at most $4n+1$ black cells in a $2n+1$ L, so we're done. $\blacksquare$

Remark: If at first you can't induct, try, try again
This post has been edited 2 times. Last edited by IAmTheHazard, Dec 20, 2021, 10:51 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
channing421
1353 posts
#12
Y by
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8862 posts
#13
Y by
Here's an odd solution.

The answer is $(2n+1)(n+1)$, where equality holds when we color all the odd-indexed rows black.

Label each black square with $1$ and white square with $-1$. For double counting reasons, it suffices to show that we can have at most $4$ corner black squares and $6n-4$ edge black squares. Actually, we will show the stronger conclusion that we can have at most $6n$ black squares along the outer periphery.

Assume for the sake of contradiction that $6n$ is not optimal. Divide the $(2n+1) \times (2n+1)$ square into $n-1$ layers in succession wrapped around one center square, and define the value of each layer to be the sum of the values of it squares, counted by multiplicity according to how many $2 \times 2$ squares with one edge along the edge of this layer the square belongs to. This means that the value of the outer periphery of squares is greater than $6n \cdot 2 - 4 - 2\cdot 4n = 8n-4$.

Claim. The absolute value of the value of each successive layer comprised of the outer periphery of the square contained within the previous layer decreases by at most $8$ each layer.

Proof. The layer of $2 \times 2$ squares that are formed by squares within the two layers must have values summing to zero. On the other hand, this value equals $$0 = \text{Value} = \text{Value of outer layer} \ +\ \text{Value of inner layer} \ -\ 2\ \cdot \ \text{Value of four corner squares}.$$As the value of the four corner squares is at most $\pm 4$, this implies the result. $\blacksquare$

This means that the value of the final layer has absolute value at least $5$. However, using the previous equality again, this implies that the value of the center square has absolute value greater than $1$ (as it is counted in four of the $2 \times 2$ squares), contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
gvole
201 posts
#14
Y by
Notice each connected component is a stick, you can extend sticks on the edge of the board, and if there is no stick on the edge you can push one to it. Now you get a stick along one edge of the board. Delete the last 2 rows and repeat.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#15
Y by
Solution from Twitch Solves ISL:

The answer is $(n+1)(2n+1)$ achieved by coloring all the odd numbered rows.
We proceed by induction on $n$ with the base case $n=0$ being clear. For the other direction, we are going to decompose our $(2n+1)\times(2n+1)$ board into a $2 \times 2$ square, two $2 \times (2n-1)$ strips, and a $(2n-1) \times (2n-1)$ square, as shown below.

[asy]
size(6cm); filldraw(box( (0,0), (2,7) ), palegreen, blue+1); filldraw(box( (2,7), (9,9) ), palegreen, blue+1); filldraw(box( (0,7), (2,9) ), palered, blue+1); for (int i=0; i<=9; ++i) { draw( (0,i)--(9,i), grey ); draw( (i,0)--(i,9), grey ); } filldraw(box((2,0), (9,7)), paleyellow, blue+1); label("$(2n-1) \times (2n-1)$", (5.5, 3.5), blue);
[/asy]
To get the bound, we observe that:
  • The red $2 \times 2$ square has at most two black cells.
  • The western green rectangle has at most $2n$ black cells, with equality if and only if the rows of length $2$ are shaded alternating black. The same is true for the northern green rectangle.
  • However, equality cannot simultaneously occur: if the two green rectangles both have $2n$ black cells, then the red $2 \times 2$ square has at most one black cell (at the northwestern corner).
Hence, outside the yellow square, there are at most $(2n + 2n + 2) - 1 = 4n+1$ black squares.
Now, induction gives a bound of \[ \underbrace{n \cdot (2n-1)}_{\text{by IH}} + \underbrace{(4n+1)}_{\text{green/red}} = (n+1)(2n+1). \]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pinkpig
3761 posts
#16
Y by
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
joshualiu315
2534 posts
#17
Y by
The answer is $\boxed{(n+1)(2n+1)}$, achieved by coloring in every other column. Now, we will show that this is true by induction. The base case $n=0$ is vacuous so we move on to the inductive step.

Suppose the inductive hypothesis is true for $n=k-1$. This is equivalent to a $(2k-1) \times (2k-1)$ square having at most $k(2k-1)$ black cells. Notice that a $(2k+1) \times (2k+1)$ square can be dissected into a $(2k-1) \times (2k-1)$ square, two $2 \times (2k-1)$ rectangles, and a $2 \times 2$ square.

WLOG let the $(2k-1) \times (2k-1)$ square be in the bottom-left corner. By the induction hypothesis, the $(2k-1) \times (2k-1)$ contains at most $k(2k-1)$ squares, and we can easily find that the rectangles contain at most $2k$ squares each with a similar tiling configuration. Then, the $2 \times 2$ square contains at most $2$ squares. However, if both equality cases hold for the rectangles, only the top-left square of the $2 \times 2$ square can be colored in, and it is clear that this is optimal.

Hence, the number of squares for a $(2k+1) \times (2k+1)$ square is

\[k(2k-1)+2k+2k+1 = (k+1)(2k+1),\]
completing the induction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
795 posts
#18
Y by
We claim the answer is $\boxed{(2n+1)(n+1)}$, which can be constructed by alternating shading each row. Induct on $n$, with trivial base case $n=0$.

Note that a square with side $2n+3$ can be split into a square with side $2n+1$ (which our inductive hypothesis tells us has at most $(2n+1)(n+1)$ black squares), along with a square of side length 2 (which by definition has at most 2) and two rectangles with dimensions $(2n+1) \times 2$. These rectangles can be further divided into $n$ squares of side length 2 and a $2 \times 1$ rectangle, so they have a maximum of $2n+2$ black squares with equality only when we have alternating $2 \times 1$ black columns.

However, equality cannot hold using the maximum for each of the $2 \times 2$ square and $(2n+1) \times 2$ rectangle, so the next best we can do is $(2n+2) + (2n+2) + 2 - 1 = 4n+5$, from which adding to $(2n+1)(n+1)$ indeed gives us an upper bound of $(2n+3)(n+2)$, which we've shown to be achieveable. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blueprimes
353 posts
#19
Y by
Nuked with sharpness principle :yoda:

The answer is $(n + 1)(2n + 1)$. For construction, color the leftmost column black and alternate black/white columns throughout.

To prove the bound we induct for $n \ge 0$. For the base case, it is clearly $1$ which our bound equals. For the inductive step, assume it is true for $n = k - 1$ for some $k \ge 1$. Note that the bottom-left $(2k - 1) \times (2k - 1)$ subgrid contains at most $k(2k - 1)$ black cells by our inductive hypothesis. The rest of the grid can be partitioned into $2k - 2$ copies of a $2 \times 2$ grid which have at most $4k - 4$ black cells, and a $3 \times 3$ grid missing a corner, which can be easily shown to have at most $5$ black cells. Adding our bounds the total number of black cells is at most
$$k(2k - 1) + 4k - 4 + 5 = 2k^2 + 3k + 1 = (k + 1)(2k + 1)$$as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
575 posts
#20
Y by
We claim that the maximum is $(2n+1)(n+1),$ which is attainable when the rows are filled/not filled in an alternating pattern, with the top row being filled.

Now, for the bound, we proceed with induction on $n.$ The base case, $n=0,$ is trivial so assume that our proposition holds for some integer $n=k \geq 0.$ Then consider a $(2k+3) \times (2k+3)$ board. From the inductive hypothesis, the top left $(2k+1) \times (2k+1)$ board has at most $2k^2+3k+1$ black squares. Then, the rest of the board can be partitioned into a heart-shaped tile with $8$ squares, and two $2 \times 2k$ rectangles. The rectangles each can be separated into $k$ $(2 \times 2)$ squares, each having at most $2$ black cells, therefore the two rectangles combined contribute at most $4k$ black squares.

Finally, for the heart-shape, it is easy to see that we can put at most $5$ black squares. Otherwise, if we have at least $6,$ we can bash all cases to see that they don't work. (It's not too many anyways) Therefore, we have at most $$2k^2+3k+1+4k+5=2k^2+7k+6=(2k+3)(k+2),$$so the bound holds for $n=k+1.$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ryanbear
1056 posts
#21
Y by
https://cdn.aops.com/images/0/4/0/0403a924692dbbba3903a2808314bb5c30fc1dfd.png
This post has been edited 1 time. Last edited by ryanbear, Jan 27, 2025, 7:01 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eg4334
637 posts
#22
Y by
The answer is $\boxed{2n^2+3n+1}$, achieved by alternating rows black with the top row black. We proceed using induction with the base case obvious to show. Now, consider a $2n+1$ grid. Take out a $2n-1$ grid from the bottom right corner to get a "L" shape remaining. We need to show that this shape has at most $2n^2+3n+1 - (2(n-1)^2 + 3(n-1)+1) = 4n+1$ black squares. Partition it into squares as shown in the image below which is easily generalizable. We have this small tetris piece left highlighted in red. It remains to show that this tetris piece cannot be all black which is obvious by considering the square in blue which finishes.
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cosinesine
59 posts
#24
Y by
We show that the answer is $\boxed{2n^2 + 3n + 1}$, achievable by coloring alternate columns black and white.
[asy]
defaultpen(0.5);
fill( box( (1, 1), (8, 2) ), palegreen);
fill( box( (7, 2), (8, 8) ), palegreen);
fill( box( (1, 7), (7, 8) ), palegreen);
fill( box( (1, 1), (2, 7) ), palegreen);
fill( box( (2, 2), (7, 3) ), palered);
fill( box( (6, 3), (7, 7) ), palered);
fill( box( (3, 6), (6, 7) ), palered);
fill( box( (2, 3), (3, 7) ), palered);

draw(box( (1, 1), (3, 3) ), blue + 1);
draw(box( (2, 1), (4, 3) ), orange + 1);
draw(box( (1, 2), (3, 4) ), black + 1);
draw(box( (3, 1), (5, 3) ), yellow + 1);
draw(box( (0, 0), (9, 9)), black + 1 );
label("1", (1.5, 1.5));
label("2", (2.5, 1.5));
label("3", (2.5, 2.5));
label("2", (3.5, 2.5));

for (int i=0; i<=9; ++i) { draw( (0,i)--(9,i), grey ); draw( (i,0)--(i,9), grey ); };


[/asy]

Let $L_k$ be the number of black cells in the $k$th layer, which is the ring of cells on the perimeter of a $2k + 1 \times 2k + 1$ square centered at the center of $Q$. Additionally, let $X_k$ be the number of black squares in the $k$th layer along the diagonals, and let $B = \sum L_i$ be the total number of black cells.



Now consider the set $S_k$ of all $2 \times 2$ squares which contain cells from layers $k$ and $k - 1$. There are $8k - 4$ such squares, one associated with each non diagonal cell of layer $k$. Consider the sum:
\[ R_k = \sum_ {s \in S_k} (\text{ \# of black squares in $S$}) \]As each term of this sum is $\le 2$, this sum is $\le 2(8n - 4)$. Considering each type of square(see diagram), we see:
Each of the $X_k$ diagonal black cells in layer $k$ is counted $1$ time.
Each of the $L_k - X_k$ non-diagonal black cells in layer $k$ is counted $2$ times.
Each of the $X_{k - 1}$ diagonal black cells in layer $k$ is counted $3$ times.
Each of the $L_{k - 1} - X_{k - 1}$ non-diagonal black cells in layer $k$ is counted $2$ times.

Therefore, $R_k = X_k + 2(L_k - X_k) + 3X_{k - 1} + 2(L_{k - 1} - x_{k - 1}) = 2L_k + 2L_{k - 1} + (X_{k - 1} - X_k) \le 2(8n - 4)$.
Thus:
\[ L_k + L_{k - 1} = R_k - \frac{X_{k - 1} - X_k}2 \le 8n - 4 - \frac{X_{k - 1} - X_k}{2} \le 8n - 4 - \frac{0 - 4}{2} = 8n - 2 \]where we have used that by definition, $0 \le X_i \le 4$.
The using the above repeatedly along with $L_0 \le 1$(if $n$ is even) gives us the desired upper bound on $L_0 + L_1 + \dots + L_n = B$.
This post has been edited 1 time. Last edited by cosinesine, Mar 30, 2025, 3:20 AM
Reason: linewidth
Z K Y
N Quick Reply
G
H
=
a