NACLO 2014
by KingSmasher3, Mar 28, 2014, 4:07 AM
This post has been edited 1 time. Last edited by KingSmasher3, Mar 28, 2014, 4:10 AM
Go Broncos!
by KingSmasher3, Oct 10, 2013, 3:14 AM
We are 5-0 now after the game-winning field goal in the 51-48 game last week against the Cowboys. 
This post has been edited 1 time. Last edited by KingSmasher3, Oct 10, 2013, 3:15 AM
Zsigmondy's Theorem
by KingSmasher3, Oct 10, 2013, 3:02 AM
Continuing my NT adventures...
ISL 2000 N4: Find all triplets of positive integers
such that 
.
_______
From Zsigmondy's Theorem,
has a prime factor that is not a factor of 
unless 
and 
Hence, we see that the given statement holds only if 
with 
ISL 1997 #14: Let
be positive integers such that 
and 
Prove that if 
and 
have the same prime divisors, then 
is a power of 2.
_______
Without loss of generality, let
By Zsigmondy's Theorem, 
has a prime factor that is not a factor of 
unless 
or 
is a power of 
and 
We can check that the first case does not yield any possible value of 
so we are done.
MOP 2001: Find all quadruples of positive integers
such that 
is a prime number, 
and 
_______
Obviously
If
and 
is composite, then by Zsigmondy's theorem, 
cannot be a power of a prime. The only exception to this theorem occurs when 
which clearly does not work. Therefore, must be prime. We have 
implying that 
It follows that 
must be odd, so 
Thus, 
with 
Now we know that 
and 
so cannot be prime.
If
by Zsigmondy's theorem, cannot be a power of a prime. The only exception occurs when 
is a power of and 
Let 
Then 
or 
It is clear that this only holds when 
Hence, our only solution is
ISL 2002 N3: Let
be distinct primes greater than 
. Show that 
has at least 
divisors.
_______
Let
be the product of a subset of 
Then clearly, 
Now, let 
and 
Since there are 
possible values for 
by Zsigmondy's Theorem, 
has at least distinct prime factors, which means at least 
total factors. Note that the exceptional case 
does not occur because all primes 
are greater than 
Alternate Solution: We induct on
Clearly when 
has at least 
factors: 
Now given two integers 
with 
we have
![\[\gcd(2^a+1, 2^b+1) | \gcd(2^{2a}-1,2^{2b}-1) = 2^{\gcd(2a,2b)}-1 = 3.
\]](//latex.artofproblemsolving.com/4/c/9/4c9d18138f5f70da71a74b12c7c06f1aa63ab99e.png)
This can be seen by applying the Euclidean Algorithm. Furthermore, we can easily show that
is a multiple of but not 
if and only if 
We have 
and 
is a factor of and thus 
so by the two facts stated above, 
is a factor of 
and is relatively prime to 
It follows that 
has at least 
factors. It can be seen that 
so has at least factors (for every divisor 
we have 
) as desired.
ISL 2000 N4: Find all triplets of positive integers
such that 
._______
From Zsigmondy's Theorem,
has a prime factor that is not a factor of 
unless 
and 
Hence, we see that the given statement holds only if 
with 
ISL 1997 #14: Let
be positive integers such that 
and 
Prove that if 
and 
have the same prime divisors, then 
is a power of 2._______
Without loss of generality, let
By Zsigmondy's Theorem, 
has a prime factor that is not a factor of 
unless 
or 
is a power of 
and 
We can check that the first case does not yield any possible value of 
so we are done.MOP 2001: Find all quadruples of positive integers
such that 
is a prime number, 
and 
_______
Obviously
If
and 
is composite, then by Zsigmondy's theorem, 
cannot be a power of a prime. The only exception to this theorem occurs when 
which clearly does not work. Therefore, must be prime. We have 
implying that 
It follows that 
must be odd, so 
Thus, 
with 
Now we know that 
and 
so cannot be prime.If
by Zsigmondy's theorem, cannot be a power of a prime. The only exception occurs when 
is a power of and 
Let 
Then 
or 
It is clear that this only holds when 
Hence, our only solution is
ISL 2002 N3: Let
be distinct primes greater than 
. Show that 
has at least 
divisors._______
Let
be the product of a subset of 
Then clearly, 
Now, let 
and 
Since there are 
possible values for 
by Zsigmondy's Theorem, 
has at least distinct prime factors, which means at least 
total factors. Note that the exceptional case 
does not occur because all primes 
are greater than 
Alternate Solution: We induct on
Clearly when 
has at least 
factors: 
Now given two integers 
with 
we have![\[\gcd(2^a+1, 2^b+1) | \gcd(2^{2a}-1,2^{2b}-1) = 2^{\gcd(2a,2b)}-1 = 3.
\]](http://latex.artofproblemsolving.com/4/c/9/4c9d18138f5f70da71a74b12c7c06f1aa63ab99e.png)
This can be seen by applying the Euclidean Algorithm. Furthermore, we can easily show that
is a multiple of but not 
if and only if 
We have 
and 
is a factor of and thus 
so by the two facts stated above, 
is a factor of 
and is relatively prime to 
It follows that 
has at least 
factors. It can be seen that 
so has at least factors (for every divisor 
we have 
) as desired.This post has been edited 6 times. Last edited by KingSmasher3, Jan 5, 2014, 7:07 PM
IMO Shortlist NT
by KingSmasher3, Sep 6, 2013, 3:13 AM
1995 NT #1: Let 
be a positive integer. Show that there are infinitely many perfect squares of the form 
where 
is a positive integer.
_______
Clearly, for each if there is one perfect square that is 
then there are infinitely many perfect squares. We proceed with induction on . When 
we have 
Suppose that the result holds for some 
Then we have 
for some 
If 
we try to find 
such that 
It is clear that such a exists because we need for 
which has roots, such as 
Our induction is complete. Therefore, the result holds for all 
1999 NT #3: Prove that there exists two strictly increasing sequences
and 
such that 
divides 
for every natural n.
_______
Note that for each
if there exists a 
such that 
or equivalently, if 
is a quadratic residue mod 
then we can find a such that 
Additionally, it is clear that if is a quadratic residue of 
and 
then it is a quadratic residue of 
It claim that this is true for all 
In fact, we can generalize this to all primes 
not just 
Clearly, is now a quadratic residue of 
We now prove the stronger statement that is a quadratic residue of all 
We proceed by induction on It is true for 
Assume that it holds for some It follows that 
for some If 
we find such that 
Let 
Then we have 
or 
Since we can obviously find such an our induction is complete, and we are done.
Main point(s): These problems demonstrate a trick in using induction to determine the existence of certain quadratic residues for powers.
be a positive integer. Show that there are infinitely many perfect squares of the form 
where 
is a positive integer._______
Clearly, for each
if there is one perfect square that is 
then there are infinitely many perfect squares. We proceed with induction on . When 
we have 
Suppose that the result holds for some 
Then we have 
for some 
If 
we try to find 
such that 
It is clear that such a exists because we need for 
which has roots, such as 
Our induction is complete. Therefore, the result holds for all 
1999 NT #3: Prove that there exists two strictly increasing sequences
and 
such that 
divides 
for every natural n._______
Note that for each
if there exists a 
such that 
or equivalently, if 
is a quadratic residue mod 
then we can find a such that 
Additionally, it is clear that if is a quadratic residue of 
and 
then it is a quadratic residue of 
It claim that this is true for all 
In fact, we can generalize this to all primes 
not just 
Clearly, is now a quadratic residue of 
We now prove the stronger statement that is a quadratic residue of all 
We proceed by induction on It is true for 
Assume that it holds for some It follows that 
for some If 
we find such that 
Let 
Then we have 
or 
Since we can obviously find such an our induction is complete, and we are done.Main point(s): These problems demonstrate a trick in using induction to determine the existence of certain quadratic residues for powers.
This post has been edited 2 times. Last edited by KingSmasher3, Oct 10, 2013, 3:10 AM
IMO Shortlist 1995 Combo #3
by KingSmasher3, Aug 20, 2013, 11:12 PM
Determine all integers 
for which there exist points 
in the plane, no three collinear, and real numbers 
such that for 
, the area of 
is 
.
_______
I claim that for
the given statement is impossible. Consider 5 points in the plane with corresponding numbers 
and 
We have 3 possible arrangements of these 5 points.
Arrangement 1: They form a convex pentagon. By triangulating the pentagon, we see that the area is
for 
Thus 
is constant. It follows that 
meaning that all 5 numbers are equal. But this is impossible since it would imply that 
are collinear.
Now note that if we have three points with a fourth inside the triangle, the fourth point has a value equal to the additive inverse of the average of the three points. Additionally, given convex quadrilateral
we have 
Arrangement 2: Four points form a convex quadrilateral with the fifth point inside. The four outer points form 4 triangles. The fifth point must lie within two of these triangles. Then by the above note, two adjacent vertices on the quadrilateral must have equal values. This makes the quadrilateral a trapezoid, so the two other points must be equal as well. However, the fifth point forms a convex quadrilateral with three of the four points of the original quadrilateral. From the above note, this implies that the fifth point must lie on one of the parallel sides of the trapezoid.
Arrangement 3: Two points lie inside a triangle formed by the other three points. By the above note, the two points inside must have equal values. Hence, the segments they form must be parallel to all three sides of the triangle, which is obviously impossible.
When
we can arrange the four points in a square and assign equal values to all four.
for which there exist points 
in the plane, no three collinear, and real numbers 
such that for 
, the area of 
is 
._______
I claim that for
the given statement is impossible. Consider 5 points in the plane with corresponding numbers 
and 
We have 3 possible arrangements of these 5 points.Arrangement 1: They form a convex pentagon. By triangulating the pentagon, we see that the area is
for 
Thus 
is constant. It follows that 
meaning that all 5 numbers are equal. But this is impossible since it would imply that 
are collinear.Now note that if we have three points with a fourth inside the triangle, the fourth point has a value equal to the additive inverse of the average of the three points. Additionally, given convex quadrilateral
we have 
Arrangement 2: Four points form a convex quadrilateral with the fifth point inside. The four outer points form 4 triangles. The fifth point must lie within two of these triangles. Then by the above note, two adjacent vertices on the quadrilateral must have equal values. This makes the quadrilateral a trapezoid, so the two other points must be equal as well. However, the fifth point forms a convex quadrilateral with three of the four points of the original quadrilateral. From the above note, this implies that the fifth point must lie on one of the parallel sides of the trapezoid.
Arrangement 3: Two points lie inside a triangle formed by the other three points. By the above note, the two points inside must have equal values. Hence, the segments they form must be parallel to all three sides of the triangle, which is obviously impossible.
When
we can arrange the four points in a square and assign equal values to all four.This post has been edited 1 time. Last edited by KingSmasher3, Oct 10, 2013, 3:09 AM
USAMO 2008 Problem #2
by KingSmasher3, Apr 16, 2013, 11:37 PM
Let 
be an acute, scalene triangle, and let 
, 
, and 
be the midpoints of 
, 
, and 
, respectively. Let the perpendicular bisectors of and 
intersect ray 
in points 
and 
respectively, and let lines 
and 
intersect in point 
, inside of triangle . Prove that points 
, , , and all lie on one circle.
_______
Clearly,
and 
intersect at 
the circumcenter of 
Let 
and 
Then 
Furthermore, 
Hence 
is cyclic. Let the tangents to the circumcircle of 
meet at 
We know that 
also lies on the circumcircle of 
Now,
is a symmedian of 
so it follows that 
and 
Let 
be the intersection of with the circumcircle of 
We know that 
so 
Then 
Since 
and both lie on the same circle, 
In other words, 
and are collinear.
Since
is right, 
is right as well. Thus, 
is cyclic as desired.
Main Point(s): First step is to notice that is cyclic. This leads to the fact that is right, which leads to trying to prove that 
is a line. Symmedians should come to mind.
be an acute, scalene triangle, and let 
, 
, and 
be the midpoints of 
, 
, and 
, respectively. Let the perpendicular bisectors of and 
intersect ray 
in points 
and 
respectively, and let lines 
and 
intersect in point 
, inside of triangle . Prove that points 
, , , and all lie on one circle._______
Clearly,
and 
intersect at 
the circumcenter of 
Let 
and 
Then 
Furthermore, 
Hence 
is cyclic. Let the tangents to the circumcircle of 
meet at 
We know that 
also lies on the circumcircle of 
Now,
is a symmedian of 
so it follows that 
and 
Let 
be the intersection of with the circumcircle of 
We know that 
so 
Then 
Since 
and both lie on the same circle, 
In other words, 
and are collinear.Since
is right, 
is right as well. Thus, 
is cyclic as desired.Main Point(s): First step is to notice that
is cyclic. This leads to the fact that is right, which leads to trying to prove that 
is a line. Symmedians should come to mind.USAMO 2006 Problem #2
by KingSmasher3, Apr 13, 2013, 3:54 AM
For a given positive integer find, in terms of , the minimum value of for which there is a set of 
distinct positive integers that has sum greater than but every subset of size has sum at most 
_______
Let the
distinct positive integers be 
in increasing order. Since the integers are distinct,
![\[\frac{N}{2} \ge \sum_{i=k+2}^{2k+1} a_i \ge \sum_{i=1}^{k-1} a_i + k(k+1).\]](//latex.artofproblemsolving.com/8/7/e/87ebe69eb8190c5c680858b672a33e1b8e7741f2.png)
We are also given,
![\[ a_{k+1} + \sum_{i=k+2}^{2k+1} a_i + \sum_{i=1}^{k-1} a_i > N.\]](//latex.artofproblemsolving.com/a/5/b/a5bad43fdda9af81f53e350e3b302c481b7f1cad.png)
These two inequalities tell us that
or 
Hence,
![\[N \ge 2\sum_{i=k+2}^{2k+1} a_i \ge \sum_{i=1}^{k} (a_{k+1}+i) \ge 2k^3+3k^2+3k.\]](//latex.artofproblemsolving.com/b/3/f/b3f5fad280ddaadb796ab194217a6706a8b7af8f.png)
We can check that this minimal value does indeed hold for the set
We are done.
Main Point(s): The fact that the integers are distinct is very useful in determining the bounds for 
Compare max subset of and min subset of
find, in terms of , the minimum value of for which there is a set of 
distinct positive integers that has sum greater than but every subset of size has sum at most 
_______
Let the
distinct positive integers be 
in increasing order. Since the integers are distinct,![\[\frac{N}{2} \ge \sum_{i=k+2}^{2k+1} a_i \ge \sum_{i=1}^{k-1} a_i + k(k+1).\]](http://latex.artofproblemsolving.com/8/7/e/87ebe69eb8190c5c680858b672a33e1b8e7741f2.png)
We are also given,
![\[ a_{k+1} + \sum_{i=k+2}^{2k+1} a_i + \sum_{i=1}^{k-1} a_i > N.\]](http://latex.artofproblemsolving.com/a/5/b/a5bad43fdda9af81f53e350e3b302c481b7f1cad.png)
These two inequalities tell us that
or 
Hence,![\[N \ge 2\sum_{i=k+2}^{2k+1} a_i \ge \sum_{i=1}^{k} (a_{k+1}+i) \ge 2k^3+3k^2+3k.\]](http://latex.artofproblemsolving.com/b/3/f/b3f5fad280ddaadb796ab194217a6706a8b7af8f.png)
We can check that this minimal value does indeed hold for the set
We are done.Main Point(s): The fact that the
integers are distinct is very useful in determining the bounds for 
Compare max subset of and min subset of This post has been edited 1 time. Last edited by KingSmasher3, Apr 13, 2013, 3:57 AM
USAMO 2011 Problem #5
by KingSmasher3, Apr 12, 2013, 11:39 PM
Let 
be a given point inside quadrilateral 
. Points 
and 
are located within such that
$\begin{align*}\angle Q_1BC&=\angle ABP,&\angle Q_1CB&=\angle DCP,& \angle Q_2AD&=\angle BAP,& \angle Q_2DA&=\angle CDP.\end{align*}$
Prove that
if and only if 
.
_______
If
then obviously we are done. If not, then let 
be the intersection of 
and 
Without loss of generality let be close to 
and 
than 
and 
Now note that from the given angles, is the isogonal conjugate of in 
and the isogonal conjugate of in 
This implies that both and lie on the reflection of 
over the angle bisector of 
In other words, 
are collinear. However, this is a contradiction if either or 
Therefore, if either orif 
so we are done.
Main Point(s): When given the angle configuration as in this problem, isogonal conjugates should come to mind.
be a given point inside quadrilateral 
. Points 
and 
are located within such that$\begin{align*}\angle Q_1BC&=\angle ABP,&\angle Q_1CB&=\angle DCP,& \angle Q_2AD&=\angle BAP,& \angle Q_2DA&=\angle CDP.\end{align*}$
Prove that
if and only if 
._______
If
then obviously we are done. If not, then let 
be the intersection of 
and 
Without loss of generality let be close to 
and 
than 
and 
Now note that from the given angles, is the isogonal conjugate of in 
and the isogonal conjugate of in 
This implies that both and lie on the reflection of 
over the angle bisector of 
In other words, 
are collinear. However, this is a contradiction if either or 
Therefore,
if either orif 
so we are done.Main Point(s): When given the angle configuration as in this problem, isogonal conjugates should come to mind.
This post has been edited 1 time. Last edited by KingSmasher3, Apr 12, 2013, 11:39 PM
USAMO 2010 Problem #5
by KingSmasher3, Apr 10, 2013, 11:08 PM
Let 
where is an odd prime, and let![\[
S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)}
\]](//latex.artofproblemsolving.com/c/0/b/c0bf0826fbe8897ebaf0d4b3c861120d502baefd.png)
Prove that if 
for integers 
and , then 
is divisible by .
_______
First note that for any
we have
![\[\frac{2}{(k-1)(k)(k+1)}=\frac{1}{k-1}-\frac{2}{k}+\frac{1}{k+1}=\frac{1}{k-1}+\frac{1}{k}+\frac{1}{k+1}-\frac{3}{k}.
\]](//latex.artofproblemsolving.com/f/5/a/f5afa1d2c839b44c5f903dea7b72dd0ad8a8de28.png)
Applying this to the problem,
![\[2S_q=\sum_{i=2}^{\frac{3p-1}{2}} \frac{1}{i} - \sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i}=\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}-1.\]](//latex.artofproblemsolving.com/3/8/d/38decc6baecc8d7f07bc19f9abedff25ddda7fc5.png)
It follows that,
![\[\frac{1}{p}-2S_q= 1+\frac{1}{p}-\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}.\]](//latex.artofproblemsolving.com/d/8/c/d8ca41ea8f8b43a60aaaefa002c44887f5d1740a.png)
Consequently,
![\[\frac{m-n}{n}=\frac{1}{p}-2S_q-1= \frac{1}{p}-\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}
\]](//latex.artofproblemsolving.com/f/e/c/fec4a69412e504bcad74e9e36acb95536492601f.png)
![\[=-\left(\frac{1}{\frac{p+1}{2}}+\frac{1}{\frac{p+3}{2}} + \cdots + \frac{1}{p-1}+\frac{1}{p+1}+ \cdots \frac{1}{\frac{3p-1}{2}}\right).\]](//latex.artofproblemsolving.com/c/7/6/c764e49bfefb8cc4494e9add3fc27b14169df104.png)
Now, the numerator of (the absolute value of) this sum is
![\[\sum_{i=\frac{p+1}{2}}^{p-1} \frac{P}{i} + \sum_{i=p+1}^{\frac{3p-1}{2}} \frac{P}{i} = \sum_{j=1}^{\frac{p-1}{2}} \frac{P}{p-j} + \frac{p+j},\]](//latex.artofproblemsolving.com/6/6/f/66f12de4eb3f043b4dc6ca293aa567fab30f1689.png)
where
This sum is clearly 
so 
is a multiple of as desired.
Main Point(s): When given a product in the denominator such as this one, consider using partial fraction decomposition to greatly simplify the problem.
where is an odd prime, and let![\[
S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)}
\]](http://latex.artofproblemsolving.com/c/0/b/c0bf0826fbe8897ebaf0d4b3c861120d502baefd.png)
Prove that if 
for integers 
and , then 
is divisible by ._______
First note that for any
we have![\[\frac{2}{(k-1)(k)(k+1)}=\frac{1}{k-1}-\frac{2}{k}+\frac{1}{k+1}=\frac{1}{k-1}+\frac{1}{k}+\frac{1}{k+1}-\frac{3}{k}.
\]](http://latex.artofproblemsolving.com/f/5/a/f5afa1d2c839b44c5f903dea7b72dd0ad8a8de28.png)
Applying this to the problem,
![\[2S_q=\sum_{i=2}^{\frac{3p-1}{2}} \frac{1}{i} - \sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i}=\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}-1.\]](http://latex.artofproblemsolving.com/3/8/d/38decc6baecc8d7f07bc19f9abedff25ddda7fc5.png)
It follows that,
![\[\frac{1}{p}-2S_q= 1+\frac{1}{p}-\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}.\]](http://latex.artofproblemsolving.com/d/8/c/d8ca41ea8f8b43a60aaaefa002c44887f5d1740a.png)
Consequently,
![\[\frac{m-n}{n}=\frac{1}{p}-2S_q-1= \frac{1}{p}-\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}
\]](http://latex.artofproblemsolving.com/f/e/c/fec4a69412e504bcad74e9e36acb95536492601f.png)
![\[=-\left(\frac{1}{\frac{p+1}{2}}+\frac{1}{\frac{p+3}{2}} + \cdots + \frac{1}{p-1}+\frac{1}{p+1}+ \cdots \frac{1}{\frac{3p-1}{2}}\right).\]](http://latex.artofproblemsolving.com/c/7/6/c764e49bfefb8cc4494e9add3fc27b14169df104.png)
Now, the numerator of (the absolute value of) this sum is
![\[\sum_{i=\frac{p+1}{2}}^{p-1} \frac{P}{i} + \sum_{i=p+1}^{\frac{3p-1}{2}} \frac{P}{i} = \sum_{j=1}^{\frac{p-1}{2}} \frac{P}{p-j} + \frac{p+j},\]](http://latex.artofproblemsolving.com/6/6/f/66f12de4eb3f043b4dc6ca293aa567fab30f1689.png)
where
This sum is clearly 
so 
is a multiple of as desired.Main Point(s): When given a product in the denominator such as this one, consider using partial fraction decomposition to greatly simplify the problem.
[img]http://s03.flagcounter.com/count/OsVD/bg_E8F2FF/txt_000000/border_CCCCCC/columns_2/maxflags_18/viewers_0/labels_1/pageviews_0/flags_1/[/img][/url]
March 2014
October 2013
September 2013
August 2013
April 2013