We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/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
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
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
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
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, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
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
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
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
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
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
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
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

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
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
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
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
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
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
Friday, Apr 11 - Jun 27
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
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
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

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
Monday, Mar 24 - Jun 16
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
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
k i Suggestion Form
jwelsh   0
May 6, 2021
Hello!

Given the number of suggestions we’ve been receiving, we’re transitioning to a suggestion form. If you have a suggestion for the AoPS website, please submit the Google Form:
Suggestion Form

To keep all new suggestions together, any new suggestion threads posted will be deleted.

Please remember that if you find a bug outside of FTW! (after refreshing to make sure it’s not a glitch), make sure you’re following the How to write a bug report instructions and using the proper format to report the bug.

Please check the FTW! thread for bugs and post any new ones in the For the Win! and Other Games Support Forum.
0 replies
jwelsh
May 6, 2021
0 replies
k i Read me first / How to write a bug report
slester   3
N May 4, 2019 by LauraZed
Greetings, AoPS users!

If you're reading this post, that means you've come across some kind of bug, error, or misbehavior, which nobody likes! To help us developers solve the problem as quickly as possible, we need enough information to understand what happened. Following these guidelines will help us squash those bugs more effectively.

Before submitting a bug report, please confirm the issue exists in other browsers or other computers if you have access to them.

For a list of many common questions and issues, please see our user created FAQ, Community FAQ, or For the Win! FAQ.

What is a bug?
A bug is a misbehavior that is reproducible. If a refresh makes it go away 100% of the time, then it isn't a bug, but rather a glitch. That's when your browser has some strange file cached, or for some reason doesn't render the page like it should. Please don't report glitches, since we generally cannot fix them. A glitch that happens more than a few times, though, could be an intermittent bug.

If something is wrong in the wiki, you can change it! The AoPS Wiki is user-editable, and it may be defaced from time to time. You can revert these changes yourself, but if you notice a particular user defacing the wiki, please let an admin know.

The subject
The subject line should explain as clearly as possible what went wrong.

Bad: Forum doesn't work
Good: Switching between threads quickly shows blank page.

The report
Use this format to report bugs. Be as specific as possible. If you don't know the answer exactly, give us as much information as you know. Attaching a screenshot is helpful if you can take one.

Summary of the problem:
Page URL:
Steps to reproduce:
1.
2.
3.
...
Expected behavior:
Frequency:
Operating system(s):
Browser(s), including version:
Additional information:


If your computer or tablet is school issued, please indicate this under Additional information.

Example
Summary of the problem: When I click back and forth between two threads in the site support section, the content of the threads no longer show up. (See attached screenshot.)
Page URL: http://artofproblemsolving.com/community/c10_site_support
Steps to reproduce:
1. Go to the Site Support forum.
2. Click on any thread.
3. Click quickly on a different thread.
Expected behavior: To see the second thread.
Frequency: Every time
Operating system: Mac OS X
Browser: Chrome and Firefox
Additional information: Only happens in the Site Support forum. My tablet is school issued, but I have the problem at both school and home.

How to take a screenshot
Mac OS X: If you type ⌘+Shift+4, you'll get a "crosshairs" that lets you take a custom screenshot size. Just click and drag to select the area you want to take a picture of. If you type ⌘+Shift+4+space, you can take a screenshot of a specific window. All screenshots will show up on your desktop.

Windows: Hit the Windows logo key+PrtScn, and a screenshot of your entire screen. Alternatively, you can hit Alt+PrtScn to take a screenshot of the currently selected window. All screenshots are saved to the Pictures → Screenshots folder.

Advanced
If you're a bit more comfortable with how browsers work, you can also show us what happens in the JavaScript console.

In Chrome, type CTRL+Shift+J (Windows, Linux) or ⌘+Option+J (Mac).
In Firefox, type CTRL+Shift+K (Windows, Linux) or ⌘+Option+K (Mac).
In Internet Explorer, it's the F12 key.
In Safari, first enable the Develop menu: Preferences → Advanced, click "Show Develop menu in menu bar." Then either go to Develop → Show Error console or type Option+⌘+C.

It'll look something like this:
IMAGE
3 replies
slester
Apr 9, 2015
LauraZed
May 4, 2019
k i Community Safety
dcouchman   0
Jan 18, 2018
If you find content on the AoPS Community that makes you concerned for a user's health or safety, please alert AoPS Administrators using the report button (Z) or by emailing sheriff@aops.com . You should provide a description of the content and a link in your message. If it's an emergency, call 911 or whatever the local emergency services are in your country.

Please also use those steps to alert us if bullying behavior is being directed at you or another user. Content that is "unlawful, harmful, threatening, abusive, harassing, tortuous, defamatory, vulgar, obscene, libelous, invasive of another's privacy, hateful, or racially, ethnically or otherwise objectionable" (AoPS Terms of Service 5.d) or that otherwise bullies people is not tolerated on AoPS, and accounts that post such content may be terminated or suspended.
0 replies
dcouchman
Jan 18, 2018
0 replies
Simple vector geometry existence
AndreiVila   2
N 32 minutes ago by sunken rock
Source: Romanian District Olympiad 2025 9.1
Let $ABCD$ be a parallelogram of center $O$. Prove that for any point $M\in (AB)$, there exist unique points $N\in (OC)$ and $P\in (OD)$ such that $O$ is the center of mass of $\triangle MNP$.
2 replies
AndreiVila
Mar 8, 2025
sunken rock
32 minutes ago
Inequality and function
srnjbr   3
N 35 minutes ago by pco
Find all f:R--R such that for all x,y, yf(x)+f(y)>=f(xy)
3 replies
srnjbr
2 hours ago
pco
35 minutes ago
divisibility
srnjbr   1
N 35 minutes ago by mathprodigy2011
Find all natural numbers n such that there exists a natural number l such that for every m members of the natural numbers the number m+m^2+...m^l is divisible by n.
1 reply
srnjbr
2 hours ago
mathprodigy2011
35 minutes ago
CMI Entrance 19#6
bubu_2001   5
N 43 minutes ago by quasar_lord
$(a)$ Compute -
\begin{align*}
\frac{\mathrm{d}}{\mathrm{d}x} \bigg[ \int_{0}^{e^x} \log ( t ) \cos^4 ( t ) \mathrm{d}t \bigg]
\end{align*}$(b)$ For $x > 0 $ define $F ( x ) = \int_{1}^{x} t \log ( t ) \mathrm{d}t . $

$1.$ Determine the open interval(s) (if any) where $F ( x )$ is decreasing and all the open interval(s) (if any) where $F ( x )$ is increasing.

$2.$ Determine all the local minima of $F ( x )$ (if any) and all the local maxima of $F ( x )$ (if any) $.$
5 replies
bubu_2001
Nov 1, 2019
quasar_lord
43 minutes ago
k AoPS Academy: Exporting rich format results in broken BBCode.
Minium   1
N Wednesday at 9:06 PM by jlacosta
When exporting a rich format document in the writing tab into the message board, bold formatting specifically is broken and results in broken BBCode.
Page URL: virtual.aopsacademy.org/class/<any writing class works here>/writing

TO REPRODUCE
1. enter "Lorem ipsum".
2. apply bold to "Lorem"
3. apply italic to "ip".
4. click the Post Draft on Message Board
5. read the contents of the message board post.

FOR EXAMPLE
When I format "Lorem ipsum" (in the writing tab of course), but when I export to post it, I get

[code]Lorem[/b] ipsum[/code].

Notice that the first bolding does not start, only ends.
1 reply
Minium
Mar 18, 2025
jlacosta
Wednesday at 9:06 PM
k How to report tags
Craftybutterfly   6
N Mar 19, 2025 by Demetri
Not sure if this belongs in site support but how do you report tags for topics? I recently noticed in one of the topics I made on site support had really weird tags.
6 replies
Craftybutterfly
Mar 19, 2025
Demetri
Mar 19, 2025
delete tag
o.k.oo   5
N Mar 19, 2025 by Zestra
The tag section for the question I shared is deleted after a while. What should not be done? Thanks.
5 replies
o.k.oo
Mar 18, 2025
Zestra
Mar 19, 2025
Rating Up Not Occuring
CatsRule222   2
N Mar 19, 2025 by aidan0626
Bug: In the state round, I answered 10 questions correctly without the rating changing at all (rating 43 currently) in the other rounds, it always works.
URL: https://artofproblemsolving.com/mathcounts_trainer/play
How to Recreate:
1. Get to mathcounts trainer rating 43 on state round, and it will glitch.
2 replies
CatsRule222
Mar 19, 2025
aidan0626
Mar 19, 2025
k Pressing &#039;go down button&#039; always creates a gray box on the last post
Craftybutterfly   18
N Mar 18, 2025 by jlacosta
Summary of the problem: Pressing go down to last post button always creates a gray box overlapping last post
Page URL: any forum
Steps to reproduce:
1. Go to any topic in a forum
2. The gray box at the bottom overlaps part of the first post
Expected behavior: Should not show a gray box
Frequency: 100% of the time
Operating system(s): Linux HP EliteBook 835 G8 Notebook PC
Browser(s), including version: Chrome 133.0.6943.142 (Official Build) (64-bit) (cohort: Stable)
Additional information: It works on any other device, on my iPhone XR, a MacOS, and my iPad. Took the screenshot a month ago. The gray box still appears
18 replies
Craftybutterfly
Mar 12, 2025
jlacosta
Mar 18, 2025
k The My classes tab shows cyan even though im on community
Craftybutterfly   10
N Mar 18, 2025 by jlacosta
Summary of the problem: The My classes tab shows cyan even though I'm on community. Notice the tabs next to the AoPS Online words.
Page URL: artofproblemsolving.com/community
Steps to reproduce:
1. Press on my classes next to the AoPS Online
2. Then press on community tab
Expected behavior: My Classes tab should be dark blue
Frequency: 100%
Operating system(s): HP EliteBook 835 G8 Notebook PC
Browser(s), including version: Chrome: 134.0.6998.89 (Official Build) (64-bit) (cohort: Stable)
Additional information: It happens on this specific computer only.
10 replies
Craftybutterfly
Mar 17, 2025
jlacosta
Mar 18, 2025
k Happy St. Patrick&#039;s Day!
A_Crabby_Crab   62
N Mar 18, 2025 by Moonshot
A very happy St. Patrick's day to all!
62 replies
A_Crabby_Crab
Mar 17, 2025
Moonshot
Mar 18, 2025
Mathcounts Trainer Leaderboard
ChristianYoo   3
N Mar 18, 2025 by Craftybutterfly
The leaderboard is broken.
3 replies
ChristianYoo
Mar 18, 2025
Craftybutterfly
Mar 18, 2025
Minor Color Issue
KangarooPrecise   3
N Mar 18, 2025 by BrighterFrog11
In my AOPS class, there are points on your report where your red bar turns orange, and your orange turns green, well my orange bar passed the small green mark but the bar did not turn green. I can't take a screenshot, but my orange bar should be green according to the color marking.
3 replies
KangarooPrecise
Mar 18, 2025
BrighterFrog11
Mar 18, 2025
k Negative accuracy?
DarintheBoy   3
N Mar 17, 2025 by DarintheBoy
Slow and Steady (Accuracy) I
Gain 100 Accuracy XP per day in each of the next 2 days. (-19 XP on day 1)

How did this happen? Has anyone else had this?
3 replies
DarintheBoy
Mar 17, 2025
DarintheBoy
Mar 17, 2025
Number of regions at most $\frac{n(n+1)}{3}$
lambruscokid   5
N Feb 12, 2013 by math154
Source: Argentina TST Iberoamerican 2008 problem 6
The plane is divided into regions by $ n \ge 3$ lines, no two of which are parallel, and no three of which are concurrent. Some regions are coloured , in such a way that no two coloured regions share a common segment or half-line of their borders. Prove that the number of coloured regions is at most $ \frac{n(n+1)}{3}$
5 replies
lambruscokid
Aug 27, 2009
math154
Feb 12, 2013
Number of regions at most $\frac{n(n+1)}{3}$
G H J
Source: Argentina TST Iberoamerican 2008 problem 6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lambruscokid
264 posts
#1 • 2 Y
Y by Adventure10, Mango247
The plane is divided into regions by $ n \ge 3$ lines, no two of which are parallel, and no three of which are concurrent. Some regions are coloured , in such a way that no two coloured regions share a common segment or half-line of their borders. Prove that the number of coloured regions is at most $ \frac{n(n+1)}{3}$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fwolth
202 posts
#2 • 1 Y
Y by Adventure10
Note that two regions share a common segment or half-line only if they also share a vertex. Furthermore, every pair of lines forms exactly one vertex and there are $ 1 + \binom{n + 1}{2}$ regions. Let $ v_R$ be the number of vertices of region $ R$ and denote $ V = \sum v_R$. Noticing that each intersection adds four vertices to $ V$ and that each line intersects every other line in distinct points, there $ v = 4\binom{n}{2}$, and this is $ \le$ the number of sides with double counting (it would be $ =$, but we have the unbounded regions). Finally, we observe that every side is counted exactly twice, so there are at least $ 2\binom{n}{2}$ sides.

Suppose there were more than $ \frac {n(n + 1)}{3}$ colored regions. Since no side is counted twice here, there are exactly $ \frac {2n(n + 1)}{3}$ sides counted. But this is $ > 2\binom{n}{2}$; contradiction.

This seems to make the bound seem relatively weak, so I probably screwed up somewhere. It's late though, so I don't have time to check.

EDIT:

The above is flawed in two ways. Firstly, I only proved there are at least $ 2\binom{n}{2}$ sides with double counting, when I need an upper bound rather than zero bound. It turns out there are *exactly* $ 2\binom{n}{2} + 2n$ sides.

Furthermore, the last inequality I used isn't actually true. :oops: I have a solution now, but unfortunately once again it's late and I don't have time to type it up. It rests on the lemma that there are always exactly three regions with 2 sides.

It's worth noting that the desired bound is 2/3 the total number of regions, so this may lead to a nicer proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fwolth
202 posts
#3 • 2 Y
Y by Adventure10, Mango247
Now that it's morning and I'm more sane, here's my solution:

Lemma: There are always $ 2n$ unbounded regions.
Proof: Induction. Note that all other regions have the same number of vertices and sides and unbounded regions have one more side than vertex; hence the total side sum count is exactly $ 2\binom{n}{2}+2n=n(n+1)$ as I noted above.

Lemma: There are always exactly three regions with two sides.
Proof: They must be unbounded; induction by considering cases of what unbounded regions the $ n+1$th line cuts through.

So suppose we have chosen $ \frac{n(n+1)}{3}$ regions and none share a side; we want to prove that this consumes more than the number of sides itself. To do this, we use a weighted average. Let $ x$ be the number of regions with exactly three sides; if we can show that $ 6+3x+4(\frac{n(n+1)}{3}-x-3)> n(n+1)$, or rearranging, $ 3x<n(n+1)-18$. Assume for the sake of contradiction $ 3x\ge n(n+1)-18$. However, $ 3x$ is simply the number of total edges we can have in summing over all the 3-regions, with $ n(n+1)$ edges total; we conclude that we can have at most $ 18$ edges in the sum of all other regions. Since there are always exactly 3 regions with 2 sides, we can have at most $ 12$ edges for 4+-sided ones, or at most 3 regions with more than 3 sides.

Lemma: For all $ n\ge 5$, there are at least 4 4+-sided regions.
Proof: Induction; use casework similar to our second lemma.

We can check $ n=3$ and $ n=4$ by hand.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JBL
16123 posts
#4 • 2 Y
Y by Adventure10, Mango247
fwolth wrote:
Lemma: There are always exactly three regions with two sides.
If we have five lines in the form of a regular pentagon, are there not five such regions?

Also, the first lemma has a very simple explanation: imagine zooming out so far that all of the pairwise intersections of the lines appear to collapse to a single point.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fwolth
202 posts
#5 • 1 Y
Y by Adventure10
Hmmm this is true. Let's try this then.

Since no three lines concur and no two are parallel, there are $ \binom{n + 1}{2} + 1$ regions formed, so it suffices to prove that we have fewer than $ 2/3$ of the regions colored. Now imagine the following process: Pick an arbitrary region and take one region bordering it and call them group $ G_1$. Repeat until we can no longer do so. Then we will have a number of groups $ G_k$ and various one-region "pockets" not included in any group but bordered by regions in groups (we cannot have more than two bordering regions in a pocket or we could make a group of them).

Clearly, only one of the two regions in each group can be colored. If we can show that we can select the groups in a way such that there are more groups than pockets, then we're done. To do this, we prove the stronger statement that in any connected bipartite graph where every vertex has at least degree two (lemma: the graph resulting by interpreting regions as vertices is bipartite. proof: no odd cycles, assume there was one, but each line passes through cycle twice, contradiction) we can remove pairs of adjacent vertices until fewer than a third of them are left.

Noticing the degree-two condition means that the subgraph of lesser order in the bipartite representation has at least half the number of vertices as the one with larger order, it suffices to show that for each vertex on the subgraph of smaller order, we can pick one of the vertices it's connected to on the other side so that we don't pick the same vertex for any two vertices. This is possible because if at any given point we come on a vertex so that all of the vertices (let there be $ v$ of them) it's connected to on the opposite side are already taken, then we would have to have at least $ v$ on the original vertex's side to have no choice, all connected to only that vertex's $ v$ connections. If either the graph isn't connected or there are more vertices on the original vertex's subgraph, contradiction. Otherwise, some connection preventing the original vertex is obligated by another similar situation; however, we can repeat the same logic for this with the same two cases. We clearly cannot have the second cause every time or this would be circular reasoning This concludes the proof.

The last part seems a bit imprecise; I'll try to find a better argument.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#6 • 2 Y
Y by Adventure10, Mango247
fwolth wrote:
Lemma: There are always $ 2n$ unbounded regions.
This is essentially all you need to solve the problem. If we "zoom out" as JBL said (or equivalently, place everything in a sufficiently large circle) then the unbounded regions form a $2n$-cycle. If $S\subseteq F$ is the set of colored faces, then $S$ can have at most half of this cycle and thus at most $\frac{1}{2}(2n)=n$ unbounded faces (of degree at least two); everything else in $S$ has at least three edges. It immediately follows that
\[ 3|S| - n \le \sum_{f\in S}\deg{f} \le |E| = n^2, \]as desired.

By Theorem 2(3) here, the bound is tight for infinitely many $n$ (just include the line at infinity to get the $n$ boundary triangles, and note that no two triangles share a side).
Z K Y
N Quick Reply
G
H
=
a