Solution: 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 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.

Solution: 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.

Solution: 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.

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.

Solution: 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
2 points for expressing modulo or in this form.

We will now use induction on . For , we clearly have
Now consider where , and suppose that satisfies the induction hypothesis for the prime . Clearly . Then we have 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.

Solution: 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.