1. Let
and
be positive integers. Prove that there exists a positive integer
such that for every odd integer
, the digits in the base
-
representation of
are all greater than
.
Rubric for Problem 1Solution: We prove this constructively.
Lemma 1: has at most
digits in its base
- representation.
Proof: For the base
representation of
to have more than
digits, we must have
. But this implies
, which is clearly false for
positive.
1 point for proving this lemma.
Fix
. Let the (unique) base
- representation of
be
. Define
and
to be the remainder when
is divided by
. Notice that
and
is odd for
. The solution then hinges on the following construction:
or an equivalent formulation. To prove this construction works, we need to show that
is always an integer between 
and 
inclusive.- This construction is valid.
- All can become arbitrarily large.
1 point for having a construction that uses floors and remainders.
Notice that by definition,
is the remainder when
is divided by
. Thus
is always an integer. Additionally, since
, each coefficient is between
and
.
1 point for showing that is always an integer between and inclusive in the construction chosen.
Notice that this sum equals
since it telescopes.
2 points for showing the construction chosen evaluates to .
Finally, since
, we have
![\[\frac{r_{i+1} n - r_i}{2^i} > \frac{r_{i+1} n}{2^i} - 1 \geq \frac{n}{2^i} - 1 \geq \frac{n}{2^k} - 1.\]](//latex.artofproblemsolving.com/4/2/0/420d26b6099ca264846885e7eef23b2c9c7b2dd0.png)
Thus, each digit is lower bounded by
, which can become arbitrarily large as
becomes arbitrarily large.
2 points for showing that each digit is lower bounded by a value that can become arbitrarily large.
Remark: Deduct 1 point if a value for is given but some 
fails.
2. Let
and
be positive integers with
. Let
be a polynomial of degree
with real coefficients, nonzero constant term, and no repeated roots. Suppose that for any real numbers
such that the polynomial
divides
, the product
is zero. Prove that
has a nonreal root.
Rubric for Problem 2Solution: Suppose
had no nonreal roots. We can assume
has degree
, as we can always find a polynomial
such that
has no nonreal roots. We can also assume
is monic by scaling. Also, the
case is trivial as the constant term must be nonzero, so fix
. Let the roots of
be
.
1 point for reducing to 
.
Consider the degree
polyonmials
which has the
roots
for all integers
. Let
be the coefficient of the
term of
. Then, we have
for all
. Since
, by Pigeonhole Principle, there exists a value of
such that there exists two values of
for which
.
2 points for using Pigeonhole Principle in some manner on roots and degree polynomials.
Suppose WLOG that the two values of
are
and
. Consider the polynomial
with roots
. Then we know that the coefficient of the
term is
in both
and
.
If
is the coefficient of the
term in
, then expanding gives
and
. Since
, solving this gives
. Since
, has two consecutive nonleading coefficients equal to
.
2 points for concluding some polynomial dividing has two consecutive coefficients equal to zero. Some approaches will lead to a polynomial with three consecutive nonzero coefficients in geometric progression (possibly with ratio 
). If this is the case, reward only 1 point.
Lemma 1: A polynomial
with two consecutive nonleading coefficients equal to
cannot have all distinct real roots.
Proof: By Rolle's Theorem, the derivative
has
distinct real roots as well, along with two consecutive nonleading coefficients equal to zero, but one degree lower, by the Power Rule. By doing this repeatedly, we eventually end up with a polynomial where the two consecutive coefficients have degree
and
respectively. But this polynomial has a double root at
, contradiction.
2 points for proving this lemma.
3. Alice the architect and Bob the builder play a game. First, Alice chooses two points
and
in the plane and a subset
of the plane, which are announced to Bob. Next, Bob marks infinitely many points in the plane, designating each a city. He may not place two cities within distance at most one unit of each other, and no three cities he places may be collinear. Finally, roads are constructed between the cities as follows: for each pair
of cities, they are connected with a road along the line segment
if and only if the following condition holds:
For every city
distinct from
and
, there exists
such
that
is directly similar to either
or
.
Alice wins the game if (i) the resulting roads allow for travel between any pair of cities via a finite sequence of roads and (ii) no two roads cross. Otherwise, Bob wins. Determine, with proof, which player has a winning strategy.
Note: 
is
directly similar to
if there exists a sequence of rotations, translations, and dilations sending
to
, 
to
, and
to
.
Rubric for Problem 3Solution: Alice wins by taking
to be the set of points strictly outside the circle with diameter
.
2 points for claiming Alice wins with the correct subset . No points should be rewarded for just claiming Alice wins.
Lemma 1: No two roads can cross.
Proof: The region Alice has chosen means that
is always acute. Suppose two roads
and
cross. Then,
is a convex quadrilateral. Since
is a quadrilateral, one of its angle is not acute, WLOG
. Then
cannot be a road, as
is not acute but there does not exist an
such that
is not acute, contradiction.
1 point for attempting to use angles in a connectivity argument. 1 additional point for completing the argument.
Now we show by induction that any two points are connected by some path.
1 point for mentioning induction on distance between points for connectivity. No points should be rewarded for just the mention of induction.
Suppose any two points with a distance
are connected by some path. This is trivially true for
, as no points are a distance of
apart. We show that any two points with a distance of
are also connected.
Suppose
and
are a distance of
apart. If there are no points in the circle of diameter
, then there is a road between
and
. Otherwise, there is a city
in the circle. Observe that since
is obtuse, we have
. Since
, we must have
, so then
is connected to
, which is connected to
, done.
2 points for completing the induction argument. Deduct 1 point if the base case or 
is not mentioned. Do not reward points if the induction argument is incomplete or incorrect.
4. Let
be the orthocenter of acute triangle
, let
be the foot of the altitude from
to
, and let
be the reflection of
across
. Suppose that the circumcircle of triangle
intersects line
at two distinct points
and
. Prove that
is the midpoint of
.
Rubric for Problem 4![[asy]
size(300);
defaultpen(linewidth(0.6)+fontsize(11));
pair A = (0,6), B = (-3,0), C = (5,0), H = orthocenter(A,B,C), D = foot(A,B,C), P = 2*D - H, F = foot(C,A,B), Xx = 3*C-2*B;
path circ = circumcircle(A,F,P);
pair[] oops = intersectionpoints(circ, Xx--B);
pair X = oops[0], Y = oops[1];
draw(A--B--C--cycle, rgb(0.8,0.1,0.1));
draw(C--F^^A--P, rgb(0.9,0.4,0.1));
draw(circ,rgb(0.1,0.5,0.1));
draw(circumcircle(A,B,C),rgb(0.1,0.1,0.7));
draw(F--X--P--C--Y,rgb(0.8,0.1,0.8));
dot("$A$",A,N,linewidth(3.3));
dot("$B$",B,SW,linewidth(3.3));
dot("$C$",C,SE,linewidth(3.3));
dot("$D$",D,NE,linewidth(3.3));
dot("$F$",F,NW,linewidth(3.3));
dot("$X$",X,SW,linewidth(3.3));
dot("$Y$",Y,SE,linewidth(3.3));
dot("$P$",P,S,linewidth(3.3));
dot("$H$",H,NE,linewidth(3.3));
[/asy]](//latex.artofproblemsolving.com/5/4/b/54b45b4ebef7f8e82abfa7c1daaeee177d6ff3dd.png)
Deduct 1 point if a diagram is missing.
Solution 1: Let
be the center of
. Let
be the intersection of
and the line through
parallel to
. Since
, lies on
. Additionally,
is the
-antipode of
.
2 points for constructing and identifying it lies on . 1 additional point for identifying it as the -antipode of .
Then, we have
. Let
be the foot of the altitude from
to
. Additionally, since
and
, 
is a midline and thus
.
Then
is a midline of
, so
and thus
.
2 points for identifying . Deduct 1 point if insufficient explanation is given for the equal lengths.
Since
and
(by definition), by either HL congruence or the Pythagorean theorem, we must have
.
2 points for drawing this conclusion. Deduct 1 point if insufficient explanation is given for going from to . Do not deduct more than 1 point total for insufficient explanations throughout the entire solution.
Other solutions (including bashes): Since there are many approaches to this problem, for incomplete solutions, reward points as follows.
- 1 point for identifying and proving/citing lies on
.
- 1 point for using the perpendicular bisector of both
and 
to attempt to identify .
If the solution attempts to construct
from the perpendicular bisectors, then prove that
, reward points as follows.
- 1 point for constructing the midpoint of
.
- 1 point for constructing the nine point center of and proving etiher
or 
, or something of similar nature.
- 1 point for showing .
If the solution attempts to construct
such that
, then prove that
lies on the perpendicular bisectors, reward points as follows.
- 1 point for constructing the midpoint of .
- 1 point for showing that lies on the perpendicular bisector of (or showing that
.
- 1 point for showing that lies on the perpendicular bisector of (or showing that
.
The rest of the solution finishes as shown in Solution 1.
Determine, with proof, all positive integers
such that
![\[\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k\]](//latex.artofproblemsolving.com/3/c/5/3c5984d0003c1ca2df2e68841dd9e93ed6c2d27c.png)
is an integer for every positive integer
.
Rubric for Problem 5Solution: The answer is all even integers
. For
, we have
is divisible by
, which is not true for
odd.
1 point for stating the correct answer and showing that odd fail.
Let
be a prime power dividing
. Notice that by definition we have
. Since
, we have
if
and
otherwise, so for each term, either both the numerator are divisible by
, or neither are.
For each term such that
, we have
, so
. This is valid since
has an inverse modulo
. For each term such that
, we can divide out a
from both the numerator and the denominator. Notice that what's left is simply
. Thus, we conclude that
![\[\binom ni \equiv \pm 1 \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor} \pmod{p^a}.\]](//latex.artofproblemsolving.com/0/1/c/01c00beb6efc07ed028fd0273f262b8bfb965d33.png)
2 points for expressing 
modulo or in this form.
We will now use induction on
. For
, we clearly have
![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (\pm 1)^k \equiv p \equiv 0 \pmod p.\]](//latex.artofproblemsolving.com/2/e/c/2ececb6afa8a10e116056cdc57a6c948298d0c29.png)
Now consider
where
, and suppose that
satisfies the induction hypothesis for the prime
. Clearly
. Then we have
![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (\pm 1)^k \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv p\sum_{i=0}^d \binom di^k \pmod {p^a}\]](//latex.artofproblemsolving.com/6/c/9/6c9a4b6aac62b1befef1511451c9fa30993d2cf7.png)
By the induction hypothesis,
divides the inner binomial sum, so since we are multiplying it by
, must divide
.
For all integers
, all even
work for every
. Thus, all even
works for all integers
.
4 points for a complete induction. Deduct 1 point if the synthesis of primes is not mentioned. Deduct 1 point if the base case is missing. Deduct 2 points if both are missing. If the induction is only done for prime powers of instead of all multiples of , reward only 1 point.
Remark: If the expression of 
is incorrect, reward up to 
points total.
6. Let
and
be positive integers with
. There are
cupcakes of different flavors arranged around a circle and
people who like cupcakes. Each person assigns a nonnegative real number score to each cupcake, depending on how much they like the cupcake. Suppose that for each person
, it is possible to partition the circle of
cupcakes into
groups of consecutive cupcakes so that the sum of
's scores of the cupcakes in each group is at least
. Prove that it is possible to distribute the
cupcakes to the
people so that each person
receives cupcakes of total score at least
with respect to
.
Rubric for Problem 6Solution: Call each person's partitions their
bubbles. We can make the following generalization: for each person
, reduce their score on each cupcake by some nonnegative real number so that each bubble's total score is exactly
. This would imply the original problem.
Consider one of people, Evan. Draw a bipartite graph
between the set of people except Evan
and the set of Evan's bubbles
, where a person
is connected to a bubble
if the total score of the cupcakes in that bubble with respect to
is at least
.
1 point for setting up this bipartite graph.
Now we will apply Hall's Marriage Lemma. Hall's Marriage Lemma states that there are two cases:
Case 1: There does not exist a subset
of
such that
. Here,
denotes the set of neighbors of
. Then, it is possible to match each person in
with a bubble in
such that they are connected.
Case 2: This is not the case.
1 additional point for mentioning Hall's Marriage Lemma. Do not reward this point if the proper bipartite graph is not set up.
Lemma 1: If a person
(not Evan) is not connected with a bubble
, then if a different person takes the bubble,
can join together two of their bubbles and still satisfy the hypothesis.
Proof: Since
is not connected with
, their score for that bubble is less than
. Thus
cannot entirely contain any of
's bubbles, so
overlaps with at most two of
's bubbles. Finally, since the combined score of these two bubbles is
, removing the cupcakes of
takes away a score of less than
, so
can combine these two bubbles into one large bubble with a score of at least
. If
overlaps with only one bubble, arbitrarily join that bubble with a neighboring one. This is a reduction from
people.
2 points for observing this reduction step.
First, notice that
. We now apply the following reduction algorithm:
If case 2 applies, there is a bad subset
for which the people in
cannot all be satisfied. Remove the set
and
from the graph, noting that no person in
is connected to any set
not in
. Reapply Hall's Marriage Theorem until either case 1 applies or the set
becomes empty. Notice that throughout this process, no bubble can be connected to a removed person by definition.
When case 1 applies, we can match each person
with a bubble
such that all of them are satisfied. By Lemma 1, this reduction step is valid, as any person removed is not connected to any bubble not removed. Otherwise, the set of people
eventually becomes empty, as more people are removed than bubbles at each removal. Then, we can match Evan with an empty bubble, which is again valid by Lemma 1. In either case, the problem is reduced to fewer people.
If case 1 immediately applies, then we are done. Otherwise, the problem is eventually reduced to one person. When
, the problem is trivial, as they can just take all cupcakes.
3 points for completing the reduction argument using Hall's Marriage Lemma. Deduct 1 point if the argument is complete but the case is not mentioned. 1 point may be rewarded if the argument is incomplete or incorrect but a reduction using the two cases of Hall's Marriage Lemma is seriously attempted.
by bjump, Apr 23, 2025, 4:40 PM 
(i dont remember exactly if it was 8032038 or some other number, so correct me on this)
(i posted this at 12:29) lol
?
and 
be positive integers. Prove that there exists a positive integer 
such that for every odd integer 
,
are all greater than 
.
,
.
and 
to be the remainder when 
is divided by 
.
and 
is odd for 
.
or an equivalent formulation. To prove this construction works, we need to show that
is always an integer between 
and 
inclusive.
is divided by 
.
,
since it telescopes.
,![\[\frac{r_{i+1} n - r_i}{2^i} > \frac{r_{i+1} n}{2^i} - 1 \geq \frac{n}{2^i} - 1 \geq \frac{n}{2^k} - 1.\]](http://latex.artofproblemsolving.com/4/2/0/420d26b6099ca264846885e7eef23b2c9c7b2dd0.png)
Thus, each digit is lower bounded by 
,
becomes arbitrarily large.
fails.
.
be a polynomial of degree 
such that the polynomial 
divides 
is zero. Prove that 
,
such that 
has no nonreal roots. We can also assume 
case is trivial as the constant term must be nonzero, so fix 
.
.
.
which has the 
for all integers 
.
be the coefficient of the 
term of 
for all 
,
for which 
.
and 
.
and 
.
is the coefficient of the 
term in 
and 
.
,
.
,
)
has 
distinct real roots as well, along with two consecutive nonleading coefficients equal to zero, but one degree lower, by the Power Rule. By doing this repeatedly, we eventually end up with a polynomial where the two consecutive coefficients have degree 
,
and 
in the plane and a subset 
of the plane, which are announced to Bob. Next, Bob marks infinitely many points in the plane, designating each a city. He may not place two cities within distance at most one unit of each other, and no three cities he places may be collinear. Finally, roads are constructed between the cities as follows: for each pair 
of cities, they are connected with a road along the line segment 
if and only if the following condition holds:
distinct from 
and 
,
such
is directly similar to either 
or 
.
is directly similar to 
if there exists a sequence of rotations, translations, and dilations sending 
to 
,
to 
,
to 
.
to be the set of points strictly outside the circle with diameter 
.
is always acute. Suppose two roads 
and 
cross. Then, 
is a convex quadrilateral. Since 
.
is not acute but there does not exist an 
such that 
are connected by some path. This is trivially true for 
,
are also connected.
is obtuse, we have 
.
,
,
is not mentioned. Do not reward points if the induction argument is incomplete or incorrect.
be the orthocenter of acute triangle 
,
be the foot of the altitude from 
.
intersects line 
.![[asy]
size(300);
defaultpen(linewidth(0.6)+fontsize(11));
pair A = (0,6), B = (-3,0), C = (5,0), H = orthocenter(A,B,C), D = foot(A,B,C), P = 2*D - H, F = foot(C,A,B), Xx = 3*C-2*B;
path circ = circumcircle(A,F,P);
pair[] oops = intersectionpoints(circ, Xx--B);
pair X = oops[0], Y = oops[1];
draw(A--B--C--cycle, rgb(0.8,0.1,0.1));
draw(C--F^^A--P, rgb(0.9,0.4,0.1));
draw(circ,rgb(0.1,0.5,0.1));
draw(circumcircle(A,B,C),rgb(0.1,0.1,0.7));
draw(F--X--P--C--Y,rgb(0.8,0.1,0.8));
dot("$A$",A,N,linewidth(3.3));
dot("$B$",B,SW,linewidth(3.3));
dot("$C$",C,SE,linewidth(3.3));
dot("$D$",D,NE,linewidth(3.3));
dot("$F$",F,NW,linewidth(3.3));
dot("$X$",X,SW,linewidth(3.3));
dot("$Y$",Y,SE,linewidth(3.3));
dot("$P$",P,S,linewidth(3.3));
dot("$H$",H,NE,linewidth(3.3));
[/asy]](http://latex.artofproblemsolving.com/5/4/b/54b45b4ebef7f8e82abfa7c1daaeee177d6ff3dd.png)
be the center of 
.
be the intersection of 
and the line through 
,
.
be the foot of the altitude from 
and 
,
is a midline and thus 
.
is a midline of 
,
and thus 
.
(by definition), by either HL congruence or the Pythagorean theorem, we must have 
.
.
and 
to attempt to identify 
.
or 
,
.
.![\[\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k\]](http://latex.artofproblemsolving.com/3/c/5/3c5984d0003c1ca2df2e68841dd9e93ed6c2d27c.png)
is an integer for every positive integer 
is divisible by 
,
be a prime power dividing 
.
.
,
if 
and 
otherwise, so for each term, either both the numerator are divisible by 
,
,
,
.
has an inverse modulo 
.![\[\binom ni \equiv \pm 1 \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor} \pmod{p^a}.\]](http://latex.artofproblemsolving.com/0/1/c/01c00beb6efc07ed028fd0273f262b8bfb965d33.png)
modulo 
.
,![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (\pm 1)^k \equiv p \equiv 0 \pmod p.\]](http://latex.artofproblemsolving.com/2/e/c/2ececb6afa8a10e116056cdc57a6c948298d0c29.png)
where 
,
satisfies the induction hypothesis for the prime 
.![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (\pm 1)^k \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv p\sum_{i=0}^d \binom di^k \pmod {p^a}\]](http://latex.artofproblemsolving.com/6/c/9/6c9a4b6aac62b1befef1511451c9fa30993d2cf7.png)
By the induction hypothesis, 
divides the inner binomial sum, so since we are multiplying it by 
.
.
is incorrect, reward up to 
points total.
and 
.
between the set of people except Evan 
if the total score of the cupcakes in that bubble with respect to 
.
denotes the set of neighbors of 
people.
.
from the graph, noting that no person in 
such that the base
is a perfect square and the base
is a perfect cube.
September 2017
February 2017