Summer is a great time to explore cool problems to keep your skills sharp!  Schedule a class today!

G
Topic
First Poster
Last Poster
k a June Highlights and 2025 AoPS Online Class Information
jlacosta   0
Jun 2, 2025
Congratulations to all the mathletes who competed at National MATHCOUNTS! If you missed the exciting Countdown Round, you can watch the video at this link. Are you interested in training for MATHCOUNTS or AMC 10 contests? How would you like to train for these math competitions in half the time? We have accelerated sections which meet twice per week instead of once starting on July 8th (7:30pm ET). These sections fill quickly so enroll today!

[list][*]MATHCOUNTS/AMC 8 Basics
[*]MATHCOUNTS/AMC 8 Advanced
[*]AMC 10 Problem Series[/list]
For those interested in Olympiad level training in math, computer science, physics, and chemistry, be sure to enroll in our WOOT courses before August 19th to take advantage of early bird pricing!

Summer camps are starting this 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 a transformative 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][*]June 5th, Thursday, 7:30pm ET: Open Discussion with Ben Kornell and Andrew Sutherland, Art of Problem Solving's incoming CEO Ben Kornell and CPO Andrew Sutherland host an Ask Me Anything-style chat. Come ask your questions and get to know our incoming CEO & CPO!
[*]June 9th, Monday, 7:30pm ET, Game Jam: Operation Shuffle!, Come join us to play our second round of Operation Shuffle! If you enjoy number sense, logic, and a healthy dose of luck, this is the game for you. No specific math background is required; all are welcome.[/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, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
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
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
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
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
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
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
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
Tuesday, Nov 4 - Feb 10
Sunday, Dec 7 - Mar 8

Introduction to Number Theory
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
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
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
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, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
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!)

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
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, Jun 22 - Nov 2
Sunday, Sep 28 - Feb 15
Tuesday, Nov 4 - Mar 24

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

Precalculus
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8
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

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

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

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
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!)
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
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
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
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!)
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
Monday, Jun 30 - Jul 21
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
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
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
Sunday, Jun 22 - Sep 21
Tuesday, Sep 2 - Nov 18

F=ma Problem Series
Wednesday, Jun 11 - Aug 27
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
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
Thursday, Aug 14 - Oct 30
Sunday, Sep 7 - Nov 23
Tuesday, Dec 2 - Mar 3

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22
Friday, Oct 3 - Jan 16

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

Physics

Introduction to Physics
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15
Tuesday, Sep 2 - Nov 18
Sunday, Oct 5 - Jan 11
Wednesday, Dec 10 - Mar 11

Physics 1: Mechanics
Monday, Jun 23 - Dec 15
Sunday, Sep 21 - Mar 22
Sunday, Oct 26 - Apr 26

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Jun 2, 2025
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
tangent circles
m4thbl3nd3r   0
a few seconds ago
Let $O,H,T$ be circumcenter, orthocenter and A-HM point of triangle $ABC$. Let $AH,AT$ intersect $(O)$ at $K,N$, respectively. Let $XYZ$ be the triangle formed by $TH,BC,KN$. Prove that $(XYZ)$ is tangent to $(O).$
0 replies
m4thbl3nd3r
a few seconds ago
0 replies
Brilliant Problem
M11100111001Y1R   9
N 12 minutes ago by The5
Source: Iran TST 2025 Test 3 Problem 3
Find all sequences \( (a_n) \) of natural numbers such that for every pair of natural numbers \( r \) and \( s \), the following inequality holds:
\[
\frac{1}{2} < \frac{\gcd(a_r, a_s)}{\gcd(r, s)} < 2
\]
9 replies
M11100111001Y1R
May 27, 2025
The5
12 minutes ago
Draw sqrt(2024)
shanelin-sigma   1
N 20 minutes ago by CrazyInMath
Source: 2024/12/24 TCFMSG Mock p10
On a big plane, two points with length $1$ are given. Prove that one can only use straightedge (which draws a straight line passing two drawn points) and compass (which draws a circle with a chosen radius equal to the distance of two drawn points and centered at a drawn points) to construct a line and two points on it with length $\sqrt{2024}$ in only $10$ steps (Namely, the total number of circles and straight lines drawn is at most $10$.)
1 reply
shanelin-sigma
Dec 24, 2024
CrazyInMath
20 minutes ago
A beautiful Lemoine point problem
phonghatemath   3
N 28 minutes ago by orengo42
Source: my teacher
Given triangle $ABC$ inscribed in a circle with center $O$. $P$ is any point not on (O). $AP, BP, CP$ intersect $(O)$ at $A', B', C'$. Let $L, L'$ be the Lemoine points of triangle $ABC, A'B'C'$ respectively. Prove that $P, L, L'$ are collinear.
3 replies
phonghatemath
Today at 5:01 AM
orengo42
28 minutes ago
Serbian selection contest for the IMO 2025 - P1
OgnjenTesic   4
N 39 minutes ago by Mathgloggers
Source: Serbian selection contest for the IMO 2025
Let \( p \geq 7 \) be a prime number and \( m \in \mathbb{N} \). Prove that
\[\left| p^m - (p - 2)! \right| > p^2.\]Proposed by Miloš Milićev
4 replies
OgnjenTesic
May 22, 2025
Mathgloggers
39 minutes ago
Complex number
soruz   1
N 43 minutes ago by Mathzeus1024
$i)$ Determine $z \in \mathbb{C} $ such that $2|z| \ge |z^n-3|, \forall n \in  \mathbb N^*.$
$ii)$ Determine $z \in \mathbb{C} $ such that $2|z| \ge |z^n+3|, \forall n \in  \mathbb N^*.$
1 reply
soruz
Nov 28, 2024
Mathzeus1024
43 minutes ago
k colorings and triangles
Rijul saini   2
N an hour ago by kotmhn
Source: LMAO Revenge 2025 Day 1 Problem 3
In the city of Timbuktu, there is an orphanage. It shelters children from the new mysterious disease that causes children to explode. There are m children in the orphanage. To try to cure this disease, a mad scientist named Myla has come up with an innovative cure. She ties every child to every other child using medicinal ropes. Every child is connected to every other child using one of $k$ different ropes. She then performs a experiment that causes $3$ children, each connected to each other with the same type of rope, to be cured. Two experiments are said to be of the same type, if each of the ropes connecting the children has the same medicine imbued in it. She then unties them and lets them go back home.

We let $f(n, k)$ be the minimum m such that Myla can perform at least $n$ experiments of the same type. Prove that:

$i.$ For every $k \in \mathbb N$ there exists a $N_k \in N$ and $a_k, b_k \in \mathbb Z$ such that for all $n > N_k$, \[f(n, k) = a_kn + b_k.\]
$ii.$ Find the value of $a_k$ for every $k \in \mathbb N$.
2 replies
Rijul saini
Wednesday at 7:11 PM
kotmhn
an hour ago
IMO ShortList 2008, Number Theory problem 1
April   65
N an hour ago by Siddharthmaybe
Source: IMO ShortList 2008, Number Theory problem 1
Let $n$ be a positive integer and let $p$ be a prime number. Prove that if $a$, $b$, $c$ are integers (not necessarily positive) satisfying the equations \[ a^n + pb = b^n + pc = c^n + pa\] then $a = b = c$.

Proposed by Angelo Di Pasquale, Australia
65 replies
April
Jul 9, 2009
Siddharthmaybe
an hour ago
Aloo and Batata play game on N-gon
guptaamitu1   0
an hour ago
Source: LMAO revenge 2025 P6
Aloo and Batata are playing a game. They are given a regular $n$-gon, where $n > 2$ is an even integer. At the start, a line joining two vertices is chosen arbitrarily and one of its endpoints is chosen as its pivot. Now, Aloo rotates the line around the pivot either clockwise or anti-clockwise until it passes through another vertex of the $n$-gon. Then, the new vertex becomes the pivot and Batata again chooses to rotate the line clockwise or anti-clockwise
about the pivot. The player who moves the line into a position it has already been in (i.e. it passes through the same two vertices of the $n$-gon it was in at a previous time) loses.
Find all $n$ such that Batata always has a winning strategy irrespective of the starting edge.

Proposed by Anik Sardar, Om Patil and Anudip Giri
0 replies
guptaamitu1
an hour ago
0 replies
Trig Inequality back in Olympiads!
guptaamitu1   0
an hour ago
Source: LMAO revenge 2025 P5
Let $x,y,z \in \mathbb R$ be such that $x + y + z = \frac{\pi}{2}$ and $0 < x,y,z \le \frac{\pi}{4}$. Prove that:
$$  \left( \frac{\sin x - \sin y}{\cos z} \right)^2  \le 1 - 8 \sin x \sin y \sin z $$
Proposed by Shreyas Deshpande
0 replies
guptaamitu1
an hour ago
0 replies
Reflection of (BHC) in AH
guptaamitu1   0
an hour ago
Source: LMAO revenge 2025 P4
Let $ABC$ be a triangle with orthocentre $H$. Let $D,E,F$ be the foot of altitudes of $A,B,C$ onto the opposite sides, respectively. Consider $\omega$, the reflection of $\odot(BHC)$ about line $AH$. Let line $EF$ cut $\omega$ at distinct points $X,Y$, and let $H'$ be the orthocenter of $\triangle AYD$. Prove that points $A,H',X,D$ are concyclic.

Proposed by Mandar Kasulkar
0 replies
guptaamitu1
an hour ago
0 replies
King's Constrained Walk
Hellowings   2
N an hour ago by Hellowings
Source: Own
Given an n x n chessboard, with a king starting at any square, the king's task is to visit each square in the board exactly once (essentially an open path); this king moves how a king in chess would.
However, we are allowed to place k numbers on the board of any value such that for each number A we placed on the board, the king must be in the position of that number A on its Ath square in its journey, with the starting square as its 1st square.
Suppose after we placed k numbers, there is one and only one way to complete the king's task (this includes placing the king in a starting square), find the minimum value of k set by n.

Should've put one of its tag as "Open problem"; I have no idea how to tackle this problem either.
2 replies
Hellowings
May 30, 2025
Hellowings
an hour ago
Nut equation
giangtruong13   2
N 2 hours ago by Mathzeus1024
Source: Mie black fiends
Solve the quadratic equation: $$[4(\sqrt{(1+x)^3})^2-3\sqrt{1+x^2}](4x^3+3x)=2$$
2 replies
giangtruong13
Apr 1, 2025
Mathzeus1024
2 hours ago
Euler line problem
m4thbl3nd3r   2
N 2 hours ago by m4thbl3nd3r
Let $O,H$ be the circumcenter and orthocenter of triangle $ABC$ and $E,F$ be intersections of $OH$ with $AB,AC$. Let $H',O'$ be orthocenter and circumcenter of triangle $AEF$. Prove that $O'H'\parallel BC.$
2 replies
m4thbl3nd3r
3 hours ago
m4thbl3nd3r
2 hours ago
subsets of {1,2,...,mn}
N.T.TUAN   11
N May 15, 2025 by MathLuis
Source: USA TST 2005, Problem 1
Let $n$ be an integer greater than $1$. For a positive integer $m$, let $S_{m}= \{ 1,2,\ldots, mn\}$. Suppose that there exists a $2n$-element set $T$ such that
(a) each element of $T$ is an $m$-element subset of $S_{m}$;
(b) each pair of elements of $T$ shares at most one common element;
and
(c) each element of $S_{m}$ is contained in exactly two elements of $T$.

Determine the maximum possible value of $m$ in terms of $n$.
11 replies
N.T.TUAN
May 14, 2007
MathLuis
May 15, 2025
subsets of {1,2,...,mn}
G H J
Source: USA TST 2005, Problem 1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
N.T.TUAN
3595 posts
#1 • 8 Y
Y by mathematicsy, Adventure10, Mango247, and 5 other users
Let $n$ be an integer greater than $1$. For a positive integer $m$, let $S_{m}= \{ 1,2,\ldots, mn\}$. Suppose that there exists a $2n$-element set $T$ such that
(a) each element of $T$ is an $m$-element subset of $S_{m}$;
(b) each pair of elements of $T$ shares at most one common element;
and
(c) each element of $S_{m}$ is contained in exactly two elements of $T$.

Determine the maximum possible value of $m$ in terms of $n$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TomciO
552 posts
#2 • 9 Y
Y by mathematicsy, SSaad, Adventure10, AlastorMoody, Mango247, and 4 other users
Let the sets $ A_{1}, A_{2}, ..., A_{2n}$ be the elements of $ T$. Then for each $ n \in S$ there is exactly one, unique, pair of $ i, j$ such that $ A_{i}\cap A_{j}= \{n\}$ (second and third condition), there are possibly some empty intersections, so the number of intersection is not less then the number of elements of $ S$. In other words: $ \binom{2n}{2}\geq mn$ or $ m \leq 2n-1$. We will show that $ m=2n-1$ is attainable. We construct $ A_{1}, ..., A_{2n}$ as follows. $ A_{1}=\{1,2,...,2n-1\}$. If we have constructed $ A_{1}, ..., A_{k}$ then for $ A_{k+1}$ we take an element on the $ k$-th position from each of the builded sets and for the rest of elements we choose smallest, unused elements of $ S$. So it goes like:
$ A_{1}=\{1,2,...,2n-1\}$
$ A_{2}=\{1,2n,...,4n-3\}$
$ A_{3}=\{2,2n,4n-2...,6n-6\}$
$ A_{4}=\{3, 2n+1, 4n-2, 6n-5, ..., 8n-10\}$
...
$ A_{2n}=\{2n-1, 4n-3, 6n-6, 8n-10, ..., (2n-1)n\}$

It's easy to verify that such construction satisfies all required conditions.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
epitomy01
240 posts
#3 • 4 Y
Y by Adventure10, Mango247, and 2 other users
Here's another way of thinking about the problem:
Consider a table with $ mn$ columns and $ 2n$ rows. Let each of the $ 2n$ rows represent each subset that is an element of $ T$, and each of the $ mn$ columns represent a subset; for each element that is an a certain subset of $ T$, in the row representing that subset, mark the relevant box. The given conditions tell us that: Each row has $ m$ marked squares, and each column has $ 2$ marked squares; and it's easy to see that each pair of elements in $ T$ shares at most one common element, iff there are no rectangles in the figure. So we have to find the largest $ m$, so that there are no rectangles.
Suppose $ m \geq 2n$. WLOG (for convenience) the first row in the figure has the first $ m$ squares marked. Also WLOG, that the 2nd row has the 1st square marked, the 3rd row has the 2nd square marked ... the 2n-th row has the $ 2n-1$-th square marked (to satisfy the condition that each column has 2 marked squares). Consider the $ 2n$-th row. We must have one marked square apart from the one already marked, but we easily see that marking any of the remaining of $ 2n-1$ squares will complete a rectangle - which gives us a desired contradiction.
When $ m = 2n-1$, greedy principle does the job. Mark the first $ 2n-1$ squares of the first row. Starting from the $ 1$-st square in the $ 2$-nd row, tick the diagonal going down. Now mark, the next set of $ 2n-2$ squares, and mark the diagonal downwards again - keep doing this, and some simple computations show that when you finish you just finish filling the table.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DangChienbn
67 posts
#4 • 5 Y
Y by Adventure10, Mango247, and 3 other users
Oh. This problem is very easy. If you have a graph with the vertexs is all sets. If two vertex are conected, we have two sets respect to two sets have common elements. So by the given conditions, we have each sides is respect to elements of the set
$S_m$.
Easily, we have $m_{max}=2n-1$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
brian22
339 posts
#5 • 2 Y
Y by Adventure10, Mango247
I got a solution similar to DangChien's, but the write-up is a bit more formal.

Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_pi_rate
1218 posts
#6 • 2 Y
Y by Adventure10, Mango247
ANSWER: The maximum possible value of $m$ is $m=2n-1$.

PROOF: Let $T=\{A_1,A_2, \dots ,A_{2n}\}$. Consider a $mn \times 2n$ matrix with all entries either $0$ or $1$, such that $a_ij=1$ iff $j \in A_i$. Call a triplet of the form $(i,A_j,A_k)$ nice if $i \in A_j$ and $i \in A_k$. We count the number of nice triplets in two different ways:-
  • First fix an element $i$. Then, as $i$ is present in exactly two unique sets $A_j$ and $A_k$ according to problem condition $(c)$, so we get that $$\text{Total number of nice triplets}=\sum_{i=1}^{mn} \binom{2}{2} =mn$$
  • This time, we choose two sets $A_j$ and $A_k$ in $\binom{2n}{2}$ ways. Then, according to condition $(b)$, these two sets have atmost one common element, which gives $$\text{Total number of nice triplets} \leq \binom{2n}{2}$$
Thus, we get that $mn \leq \frac{2n(2n-1)}{2} \Rightarrow m \leq 2n-1$. Now, all that needs to be done is show that this bound is achievable.

Let us take $S=\{1,2, \dots ,n(2n-1)\}$ for $m=2n-1$. Then we define the elements of $T=\{A_1,A_2, \dots ,A_{2n}\}$ as follows:-
\[\displaystyle A_i = \left\{ \begin{array}{lr}  \{x:x=(p-1)(2n-1)+q \cup (n-1)(2n-1)+i \text{ for } 1 \leq p \leq n \text{ and } 1 \leq q \leq 2\} & \text{when}\ \ 1 \leq i \leq n-1 \\ \\ \{x:x=a(2n-1) \cup (n-1)(2n-1)+b \text{ for } 1 \leq a \leq n \text{ and } n \leq b \leq 2n-1\} & \text{when}\ \ i=n \\ \\ \{x:x=(i-n-1)(2n-1)+j \text{ for } 1 \leq j \leq 2n-1\} & \text{when}\ \ n+1 \leq i \leq 2n \end{array} \right.\]Then one can easily see that this set $T$ satisfies all the three conditions given in the problem statement. Hence, done. $\blacksquare$
This post has been edited 1 time. Last edited by math_pi_rate, Dec 18, 2018, 3:37 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shankarmath
544 posts
#7 • 2 Y
Y by Adventure10, Mango247
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anurag27826
93 posts
#9 • 2 Y
Y by GeoKing, cursed_tangent1434
Easy problem. Solved with geoking and myself.

The bound is pretty easy to get consider a $\binom{2n}{2} \text{x } mn$ incidence matrix, where the rows represent the pair of $A_{i}$ and the column $j$ represents the number $j$. If the number $j$ is in the i'th pair, we put 1 in the $(i,j)$ cell. Note that for each element, there is a pair of set and the intersection of any set is atmost 1. So we get $\binom{2n}{2} \geq mn$, by further simplifying one can get $m \leq 2n-1$. For construction, note that this incidence matrix is a square, and now diagonally fill $1$ to finish.
This post has been edited 3 times. Last edited by anurag27826, Jun 2, 2023, 2:36 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
quantam13
128 posts
#10
Y by
Neat double counting problem :) My construction is one that I have not seen on the thread :(

Double count the number $X$ of pairs $(e, T_1, T_2)$ where $e\in T_1, T_2\in T$. Fixing $T_1$ and $T_2$ and using condition (b), we get that $X\le \binom{2n}{2}$. Fixing $e$ and using (c), we get that $X=mn$. Combining the two, we get a bound $m\le 2n-1$.


For the construction, consider $2n$ lines in general position, which can easily be checked to work
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AshAuktober
1016 posts
#11
Y by
Double counting the number $\mathcal{T}$ of triples \[(A_i, A_j, x \in A_i\cap A_j)\]gives us $mn \le \binom{2n}{n}$, i.e. $\boxed{m \le 2n-1}$.

The construction is a greedy algorithm.
This post has been edited 1 time. Last edited by AshAuktober, Apr 28, 2025, 2:51 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
de-Kirschbaum
204 posts
#12
Y by
Note that by condition b and c we have that $\binom{2n}{2} \geq mn \implies 2n-1 \geq m$. The equality is achieved by greedy.
This post has been edited 1 time. Last edited by de-Kirschbaum, May 13, 2025, 1:06 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathLuis
1562 posts
#13
Y by
Counting the number of intersections in $T$ using conditions b and c we get that $\binom{2n}{2} \ge mn$ or just $2n-1 \ge m$. To show $m=2n-1$ can be achieved basically just go greedy and take $A_1$ as $1,2, \cdots 2n-1$, then construct the sets inductively by having all $A_1, \cdots A_k$ built, then the idea is that $A_{k+1}$ will have the k-th element repeated from each of the $A_i$'s built before and the rest of terms is the smallest terms not choosen before, clearly this just works so we are done :cool:.
Z K Y
N Quick Reply
G
H
=
a