G
Topic
First Poster
Last Poster
k a April Highlights and 2025 AoPS Online Class Information
jlacosta   0
Yesterday at 3:18 PM
Spring is in full swing and summer is right around the corner, what are your plans? At AoPS Online our schedule has new classes starting now through July, so be sure to keep your skills sharp and be prepared for the Fall school year! Check out the schedule of upcoming classes below.

WOOT early bird pricing is in effect, don’t miss out! If you took MathWOOT Level 2 last year, no worries, it is all new problems this year! Our Worldwide Online Olympiad Training program is for high school level competitors. AoPS designed these courses to help our top students get the deep focus they need to succeed in their specific competition goals. Check out the details at this link for all our WOOT programs in math, computer science, chemistry, and physics.

Looking for summer camps in math and language arts? Be sure to check out the video-based summer camps offered at the Virtual Campus that are 2- to 4-weeks in duration. 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 events:
[list][*]April 3rd (Webinar), 4pm PT/7:00pm ET, Learning with AoPS: Perspectives from a Parent, Math Camp Instructor, and University Professor
[*]April 8th (Math Jam), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS State Discussion
April 9th (Webinar), 4:00pm PT/7:00pm ET, Learn about Video-based Summer Camps at the Virtual Campus
[*]April 10th (Math Jam), 4:30pm PT/7:30pm ET, 2025 MathILy and MathILy-Er Math Jam: Multibackwards Numbers
[*]April 22nd (Webinar), 4:00pm PT/7:00pm ET, Competitive Programming at AoPS (USACO).[/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, 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Yesterday at 3:18 PM
0 replies
Geometry :3c
popop614   0
18 minutes ago
Source: MINE :<
Quadrilateral $ABCD$ has an incenter $I$. Let $M$ be the midpoint of $AC$. Suppose that $MI \perp BI$. $DI$ meets $(BDM)$ again at point $T$. Let points $P$ and $Q$ be such that $T$ is the midpoint of $MP$ and $I$ is the midpoint of $MQ$. Point $S$ lies on the plane such that $AMSQ$ is a parallelogram, and suppose the angle bisectors of $MCQ$ and $MSQ$ concur on $IM$.

The angle bisectors of $\angle PAQ$ and $\angle PCQ$ meet $PQ$ at $X$ and $Y$. Prove that $PX = QY$.
0 replies
+2 w
popop614
18 minutes ago
0 replies
cursed tangent is xiooix
TestX01   2
N an hour ago by TestX01
Source: xiooix and i
Let $ABC$ be a triangle. Let $E$ and $F$ be the intersections of the $B$ and $C$ angle bisectors with the opposite sides. Let $S = (AEF) \cap (ABC)$. Let $W = SL \cap (AEF)$ where $L$ is the major $BC$ arc midpiont.
i)Show that points $S , B , C , W , E$ and $F$ are coconic on a conic $\mathcal{C}$
ii) If $\mathcal{C}$ intersects $(ABC)$ again at $T$, not equal to $B,C$ or $S$, then prove $AL$ and $ST$ concur on $(AEF)$

I will post solution in ~1 week if noone solves.
2 replies
TestX01
Feb 25, 2025
TestX01
an hour ago
Game on a row of 9 squares
EmersonSoriano   2
N an hour ago by Mr.Sharkman
Source: 2018 Peru TST Cono Sur P10
Let $n$ be a positive integer. Alex plays on a row of 9 squares as follows. Initially, all squares are empty. In each turn, Alex must perform exactly one of the following moves:

$(i)\:$ Choose a number of the form $2^j$, with $j$ a non-negative integer, and place it in an empty square.

$(ii)\:$ Choose two (not necessarily consecutive) squares containing the same number, say $2^j$. Replace the number in one of the squares with $2^{j+1}$ and erase the number in the other square.

At the end of the game, one square contains the number $2^n$, while the other squares are empty. Determine, as a function of $n$, the maximum number of turns Alex can make.
2 replies
EmersonSoriano
2 hours ago
Mr.Sharkman
an hour ago
Guessing Point is Hard
MarkBcc168   30
N an hour ago by Circumcircle
Source: IMO Shortlist 2023 G5
Let $ABC$ be an acute-angled triangle with circumcircle $\omega$ and circumcentre $O$. Points $D\neq B$ and $E\neq C$ lie on $\omega$ such that $BD\perp AC$ and $CE\perp AB$. Let $CO$ meet $AB$ at $X$, and $BO$ meet $AC$ at $Y$.

Prove that the circumcircles of triangles $BXD$ and $CYE$ have an intersection lie on line $AO$.

Ivan Chan Kai Chin, Malaysia
30 replies
MarkBcc168
Jul 17, 2024
Circumcircle
an hour ago
Polynomial meets geometry
chirita.andrei   0
Yesterday at 5:42 PM
Source: Own. Proposed for Romanian National Olympiad 2025.
(a) Let $A,B,C$ be collinear points (in order) and $D$ a point in plane. Consider the disc $\mathcal{D}$ of center $D$ and radius $kBD$, for some $k\in(0,1)$. Prove that $\mathcal{D}\cap [AC]$ is either the empty set or a segment of length at most $2kAC$.
(b) Let $n$ be a positive integer and $P(X)\in\mathbb{C}[X]$ be a polynomial of degree $n$. Prove that \[\sup_{x\in[0,1]}|P(x)|\le(2n+1)^{n+1}\int\limits_{0}^{1}|P(x)|\mathrm{d}x.\]
0 replies
chirita.andrei
Yesterday at 5:42 PM
0 replies
Integral inequality with differentiable function
Ciobi_   1
N Yesterday at 3:35 PM by MS_asdfgzxcvb
Source: Romania NMO 2025 12.2
Let $f \colon [0,1] \to \mathbb{R} $ be a differentiable function such that its derivative is an integrable function on $[0,1]$, and $f(1)=0$. Prove that \[ \int_0^1 (xf'(x))^2 dx \geq 12 \cdot \left( \int_0^1 xf(x) dx\right)^2 \]
1 reply
Ciobi_
Yesterday at 2:29 PM
MS_asdfgzxcvb
Yesterday at 3:35 PM
On coefficients of a polynomial over a finite field
Ciobi_   0
Yesterday at 2:59 PM
Source: Romania NMO 2025 12.4
Let $p$ be an odd prime number, and $k$ be an odd number not divisible by $p$. Consider a field $K$ be a field with $kp+1$ elements, and $A = \{x_1,x_2, \dots, x_t\}$ be the set of elements of $K^*$, whose order is not $k$ in the multiplicative group $(K^*,\cdot)$. Prove that the polynomial $P(X)=(X+x_1)(X+x_2)\dots(X+x_t)$ has at least $p$ coefficients equal to $1$.
0 replies
Ciobi_
Yesterday at 2:59 PM
0 replies
On non-negativeness of continuous and polynomial functions
Ciobi_   0
Yesterday at 2:51 PM
Source: Romania NMO 2025 12.3
a) Let $a\in \mathbb{R}$ and $f \colon \mathbb{R} \to \mathbb{R}$ be a continuous function for which there exists an antiderivative $F \colon \mathbb{R} \to \mathbb{R} $, such that $F(x)+a\cdot f(x) \geq 0$, for any $x \in \mathbb{R}$, and$ \lim_{|x| \to \infty} \frac{F(x)}{e^{|\alpha \cdot x|}}=0$ holds for any $\alpha \in \mathbb{R}^*$. Prove that $F(x) \geq 0$ for all $x \in \mathbb{R}$.
b) Let $n\geq 2$ be a positive integer, $g \in \mathbb{R}[X]$, $g = X^n + a_1X^{n-1}+ \dots + a_{n-1}X+a_n$ be a polynomial with all of its roots being real, and $f \colon \mathbb{R} \to \mathbb{R}$ a polynomial function such that $f(x)+a_1\cdot f'(x)+a_2\cdot f^{(2)}(x)+\dots+a_n\cdot f^{(n)}(x) \geq 0$ for any $x \in \mathbb{R}$. Prove that $f(x) \geq 0$ for all $x \in \mathbb{R}$.
0 replies
Ciobi_
Yesterday at 2:51 PM
0 replies
Proving AB-BA is singular from given conditions
Ciobi_   0
Yesterday at 2:04 PM
Source: Romania NMO 2025 11.4
Let $A,B \in \mathcal{M}_n(\mathbb{C})$ be two matrices such that $A+B=AB+BA$. Prove that:
a) if $n$ is odd, then $\det(AB-BA)=0$;
b) if $\text{tr}(A)\neq \text{tr}(B)$, then $\det(AB-BA)=0$.
0 replies
Ciobi_
Yesterday at 2:04 PM
0 replies
Equivalent definition for C^1 functions
Ciobi_   0
Yesterday at 1:54 PM
Source: Romania NMO 2025 11.3
Prove that, for a function $f \colon \mathbb{R} \to \mathbb{R}$, the following $2$ statements are equivalent:
a) $f$ is differentiable, with continuous first derivative.
b) For any $a\in\mathbb{R}$ and for any two sequences $(x_n)_{n\geq 1},(y_n)_{n\geq 1}$, convergent to $a$, such that $x_n \neq y_n$ for any positive integer $n$, the sequence $\left(\frac{f(x_n)-f(y_n)}{x_n-y_n}\right)_{n\geq 1}$ is convergent.
0 replies
Ciobi_
Yesterday at 1:54 PM
0 replies
RREF of some matrices
tommy2007   3
N Yesterday at 1:51 PM by tommy2007
for $\forall n \in \mathbb{N},$
what is the maximum integer that appears in one of the Reduced Row Echelon Forms of $n \times n$ matrices which has only $-1$ and $1$ for their entries?
3 replies
tommy2007
Yesterday at 6:57 AM
tommy2007
Yesterday at 1:51 PM
Finding pairs of functions of class C^2 with a certain property
Ciobi_   0
Yesterday at 1:31 PM
Source: Romania NMO 2025 11.1
Find all pairs of twice differentiable functions $f,g \colon \mathbb{R} \to \mathbb{R}$, with their second derivative being continuous, such that the following holds for all $x,y \in \mathbb{R}$: \[(f(x)-g(y))(f'(x)-g'(y))(f''(x)-g''(y))=0\]
0 replies
Ciobi_
Yesterday at 1:31 PM
0 replies
Inverse of absolute value function
MetaphysicalWukong   2
N Yesterday at 12:32 PM by paxtonw
how does the function have an inverse for k= 101, 203, 305, 509, 611 and 713?

how do we deduce this without graphing software?
2 replies
MetaphysicalWukong
Yesterday at 7:21 AM
paxtonw
Yesterday at 12:32 PM
Unique global minimum points
chirita.andrei   0
Yesterday at 11:06 AM
Source: Own. Proposed for Romanian National Olympiad 2025.
Let $f\colon[0,1]\rightarrow \mathbb{R}$ be a continuous function. Suppose that for each $t\in(0,1)$, the function \[f_t\colon[0,1-t]\rightarrow\mathbb{R}, f_t(x)=f(x+t)-f(x)\]has an unique global minimum point, which we will denote by $g(t)$. Prove that if $\lim\limits_{t\to 0}g(t)=0$, then $g$ is constant zero.
0 replies
chirita.andrei
Yesterday at 11:06 AM
0 replies
IMO 2011 Problem 2
Amir Hossein   46
N Feb 26, 2025 by Mathandski
Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely.
Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

Proposed by Geoffrey Smith, United Kingdom
46 replies
Amir Hossein
Jul 18, 2011
Mathandski
Feb 26, 2025
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Amir Hossein
5452 posts
#1 • 33 Y
Y by LordofAngaband, hwl0304, Davi-8191, anantmudgal09, Ankoganit, Wizard_32, magicarrow, The_Maitreyo1, OlympusHero, myh2910, mathleticguyyy, Lcz, megarnie, squareroot12621, ihatemath123, Deinoncyus_Ban, Adventure10, Mango247, MathLuis, axsolers_24, zhenghua, oVlad, and 11 other users
Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely.
Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

Proposed by Geoffrey Smith, United Kingdom
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pythag011
2453 posts
#2 • 41 Y
Y by vic526tor, Uagu, LordofAngaband, hwl0304, rterte, Wizard_32, A_Math_Lover, Polynom_Efendi, Ultroid999OCPN, OlympusHero, wutf2, samuel, Lcz, math31415926535, Kobayashi, megarnie, rayfish, myh2910, Quidditch, sabkx, OronSH, Adventure10, Mango247, axsolers_24, and 17 other users
I solved it during the competition, as did one other on my team

The solution sketch is as follows:

For each point there is a line going through it that cuts the remaining points into two groups that differ in size at most 1.

Take such a line. I claim it works.

Let P be a point. There is such a line l through it. At some point, the windmill will be parallel to that line (COUNTING ORIENTATION.) At this point, it must be l, or else not both of them can split them in such a way (Remember, everything requires orientation.)

In my opinion is very nice problem.
This post has been edited 1 time. Last edited by pythag011, Jul 18, 2011, 1:59 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mszew
1044 posts
#3 • 2 Y
Y by Adventure10, Mango247
Does a convex hull helps?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pythag011
2453 posts
#4 • 1 Y
Y by Adventure10
mszew wrote:
Does a convex hull helps?

I only know solutions of two people

but they both are same as mine.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Raúl
69 posts
#5 • 2 Y
Y by Adventure10, Mango247
There are ones that claim a solution that consider the convex hull of the midle (say: consider the first convex hull, take it and tepear. We are talking about the last convex hull). The claim is that all lines trought one vertex of that convex hull is one of the vertex we want. But it seams to fail, I don't know: my solution is the one told before (now you know 3 people : ) )
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
preudtanan
30 posts
#6 • 4 Y
Y by buffet, Adventure10, Mango247, and 1 other user
pythag011 wrote:
For each point there is a line going through it that cuts the remaining points into two groups that differ in size at most 1.

Take such a line. I claim it works.

Let P be a point. There is such a line l through it. At some point, the windmill will be parallel to that line (COUNTING ORIENTATION.) At this point, it must be l, or else not both of them can split them in such a way (Remember, everything requires orientation.)

A nice solution to a really nice problem.

Whether this problem deserves to be IMO #2 might be a point of argument (In my humble opinion, it should probably have been switched with the more mundane #3), but this kind of problem that requires some sort of creativity, rather than routine methods, is what we should hope to see more on the IMO.

Congrats to the proposer, and to those who solved the problem :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Umut Varolgunes
279 posts
#7 • 10 Y
Y by OlympusHero, megarnie, Adventure10, Mango247, and 6 other users
I don't know whichever admin did this but it's not acceptable to delete a post without mentioning any excuse. Well, I am hoping that this was an accident, and waiting for an explanation.

Probably what I remembered was this USAMO problem,

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=213018&sid=d2ffc20858331fc25d3a6de15929c8a7#p213018

and this famous one, that is also mentioned in the link I gave,
Quote:
Given $2n+2$ points in the plane, no three collinear, prove that two of them determine a line that separates $n$ of the points from the other $n$.

Having spent time with either of these from before is obviously an advantage. The second problem above looks as a trivial step in the proof of the IMO problem, but trying to use those lines is considerably harder if one has not seen them before the contest.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
preudtanan
30 posts
#8 • 2 Y
Y by Adventure10 and 1 other user
Umut Varolgunes wrote:
Having spent time with either of these from before is obviously an advantage. The second problem above looks as a trivial step in the proof of the IMO problem, but trying to use those lines is considerably harder if one has not seen them before the contest.
While I certainly agree with you that having seen either of the problems you pointed out is an advantage, applying them to this IMO problem is still far from a trivial task. If those background problems gave contestants such a big head start, I would imagine that the USA team, having worked on that recent USAMO problem, would have solved this one without much difficulty. That isn't what happened. I also didn't think of that magical line even though I have seen both of the problems you mentioned.

It is very difficult to propose problems which are so novel that contestants start working on them on equal grounds, and several IMO problems, past and present, have failed much more terribly than this one in that respect. I see the advantage as a reward for those who persevered in studying past problems rather than a sign that a problem doesn't deserve to be on the contest. :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Umut Varolgunes
279 posts
#9 • 3 Y
Y by Adventure10, Mango247, and 1 other user
I did not say that this problem shouldn't have been asked, or that these two problems trivialize the problem. What I said was precisely that having these in mind is an advantage, which you seem to agree too. I also agree on that this is a nice problem, and it should have been asked as the 3rd problem.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
preudtanan
30 posts
#10 • 2 Y
Y by Adventure10, Mango247
Umut Varolgunes wrote:
I did not say that this problem shouldn't have been asked, or that these two problems trivialize the problem. What I said was precisely that having these in mind is an advantage, which you seem to agree too. I also agree on that this is a nice problem, and it should have been asked as the 3rd problem.

Yes, I misread part of what you said, so sorry about that. Now I completely agree with you.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leopoldo Taravilse
9 posts
#11 • 4 Y
Y by Adventure10, Mango247, and 2 other users
I have an idea that may lead to a solution but I'm not sure if it works. At first, you take the Convex Hull and you call that polygon S1, then you take $S_1$ out of $S$ and you take the Convex Hull and call that polygon $S_2$, and keep doing that until you have $S_1, S_2, S_3, \dots, S_n$ and 0, 1 or 2 points left. Now we choose the line $l$ such that it contains points inside $S_1, S_2,\dots, S_n$. Now we move l until it meets one of the points of $S$, but only one, if it touches 2 points in $S$ we generate $l$ again with a different angle (it will still have points inside the polygons, in fact, it will contain segments inside the polygons) and start with process.

Case 1: 0 points left after the last convex hull is removed:

Sn is a polygon: It's easy to see that for every polygon $S_i$ then the line l will always have points inside that polygon because the only way to "get out" of the polygon ethis meeting two consecutive points $v_1$ and $v_2$ of the polygon and leaving the polygon but if it touches $v_1$ and then $v_2$ it means that $v_2$ comes first in clockwise order so the line will then go inside the polygon. (I'm not too good explaining my solutions in English if there's something you don't understand please let me know and I'll try to explain it again). As the angle of the line will rotate forever in clockwise order, then every point in $S_i$ will be met infinitely many times by the line for every polygon Si because there will be a pair of points $(v,w)$ such that the line will meet $v$ and $w$ at the same time infinitely many times (after the second time it meets them the same movements from the first time start again leading to a cicle) and in that cicle every point is met at least once (that's not very hard to prove)

Case 2: 1 or 2 points left after the last convex hull is removed:

In this case we use the same algorithm than in the previous case, we forget about that 1 or 2 points and we can see that every poin inside $S_n$ will be met at least once in the process. So we start with the process until one of the 1 or 2 points inside $S_n$ is met, if it's just one point the idea is the same because the line will rotate forever and a pair of points will be met twice, hence infinitely many times, so evey point in every polygon will be met infinitely many times and the point inside too. If there are two points inside then we must prove that both points will be met in the process, but that's easy because as both points are inside $S_n$, and the line has a segment inside $S_n$ at every moment, and the line reaches the same position infinitely many times, then both points will be met infinitely many times because between moments $M_1$ and $M_2$ where the line has the same position every point inside $S_n$ will be met by the line (it's easy to prove that so I won't do it unless someone asks me to do it).

I'm not sure that my solution is 100% correct, I just think that the idea is correct but I don't know if I prooved it in a correct way.
This post has been edited 1 time. Last edited by Leopoldo Taravilse, Jul 18, 2011, 9:05 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mavropnevma
15142 posts
#12 • 10 Y
Y by OlympusHero, HamstPan38825, Adventure10, Mango247, and 6 other users
To each oriented straight line $\ell$ meeting $\mathcal{S}$ in exactly one point $P$, associate the pair of numbers $\pi_{\ell,P} = (\rho, \lambda)$ of points from $\mathcal{S}$, other than $P$, lying on its right side, respectively left side (clearly $\rho + \lambda =  |\mathcal{S}| - 1$). Our goal is to exhibit such a (fixed) pair $(\rho, \lambda)$ that to each point $P \in \mathcal{S}$ (called anchor) corresponds some distinguished line $\ell$ with $\pi_{\ell,P} = (\rho, \lambda)$. Then starting the windmill on one of these lines will fulfill the requirements, since except at the moment of changing pivots (when the line of the windmill passes through two points), the pair associated to the windmill line stays $(\rho, \lambda)$ (this is easily seen, by the very movement of the windmill). As said above, when the windmill line becomes parallel (and similarly oriented) with one of the distinguished lines, it will have to pass through its anchor point (because of the count of points given by $(\rho, \lambda)$).

Thus, there is nothing magic about having a balanced pair $|\rho - \lambda| \leq 1$; for a convex formation we can use a $(0, |\mathcal{S}| - 1)$ pair; for a square containing a point (other than its centre) we can use a $(1,3)$ pair. However, a pair known to exist for all points of $\mathcal{S}$ is precisely such a balanced pair, by discrete continuity arguments.

In fact the first paragraph even provides a way to measure the correctness of a different approach. Clearly, the lines of every windmill will (except at changing pivots) share a same pair $(\rho, \lambda)$, so for each of the points of $\mathcal{S}$ there must exist some line passing through, with associated pair that of the starting line of the windmill, otherwise such a faulty point will be skipped, and the proof fail.

A final word. A windmill starting on a line $\ell$ through a point $P \in \mathcal{S}$, corresponding to the pair $\pi_{\ell,P}$, will pass precisely through those points and only those as pivots, for which there exists a line having associated the starting pair $\pi_{\ell,P}$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Lepuslapis
78 posts
#13 • 2 Y
Y by Adventure10 and 1 other user
To be frank, I do not see why, the previous post, say, shows that the windmill will pass through every point of $\mathcal{S}$ (but that's probably just me being very stupid).

Here's a different approach to show that any path through the windmill is purely periodic: Reason on pairs of points consecutively visited by the windmill. There are but finitely many such pairs, so one pair must appear more than once. Moreover, it is easy to convince oneself that any pair of points consecutively visited by a windmill uniquely determines the windmill. Thence the process is purely periodic.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mavropnevma
15142 posts
#14 • 3 Y
Y by HamstPan38825, Adventure10, and 1 other user
There cannot be two parallel lines, similarly oriented, passing through different points of $\mathcal{S}$, and having the same associated $(\rho,\lambda)$ pair of number of points situated on their right, respectively left sides. Therefore, since a windmill reaches (infinitely often) all orientations for its lines, and its lines are always around some pivot, the windmill line having the orientation of any of the distinguished lines must have as pivot that line's anchor point.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Lepuslapis
78 posts
#15 • 3 Y
Y by Adventure10, Mango247, and 1 other user
Thanks a lot.
Z K Y
G
H
=
a