This year’s contest had some interesting problems. I’ll present some example solutions to the less technically challenging of the lot.
Problem A1: Let . Define a recursive sequence by letting be the sum of and the product of its distinct prime factors. So the sequence goes . Prove that the product of the first primes is in this sequence.
Solution A1: Let the primes be . We claim that for every , is in the sequence. Clearly is in this sequence. Now suppose is in this sequence. The sequence then continues, . Eventually, we will reach a because the only distinct prime factors of are . Therefore is a term of the sequence.
Problem A2: Consider the operation that is defined by . Let and be permutations of . Find all such permutations that maximize
Solution A2: For the , we expand. This is . is constant so we maximize the fraction by picking . For the , we expand as well. The expression expands to
Since is a factor in every term, we must maximize to maximize the expression. Thus . Now occurs in all the remaining terms, etc. Thus .
Problem B1: Find such that
Solution B1: for all real . Notice is non-negative on a bounded interval. Thus the integral achieves its maximum on this interval. so .
Problem B2: Prove that the number
is divisible by for all primes .
Solution B2: This solution is a bit more involved unfortunately.
We begin by making the computation
We then take a slight detour into Maclaurin series. The closest fraction of the form to is exactly of the form . This is motivated by expanding . By analyzing the error, we determine that it is indeed at most , meaning that a different choice of yields a larger error.
Now let be an odd number. We can easily see that
where . Therefore , because then the error term is . We can also see that
where . We then see that . Let us substitute . We obtain,
We can then compute
and with a bit more magic we get
Problem B3: Let be a ﬁnite simple graph and let be the largest number of vertices of any clique in . Suppose that we label each vertex of with a non-negative real number, so that the sum of all such labels is . Deﬁne the value of an edge to be the product of the labels of the two vertices at its ends. Deﬁne the value of a labeling to be the sum of values of the edges.
Prove that the maximum possible value of a labeling of is .
Solution B3: We first solve it for complete graphs of size . Clearly the claimed maximum value is achieved by letting each vertex have value . Each edge has value and there are of them. Therefore the labeling of this graph has value . We now prove that this is a maximum. Let be the values. The value is computed as
Suppose for some . Assume WLOG that they are . We replace and with . Compute
Since , this new labeling achieves a greater value. Since any labeling where two values differ is not maximal, our labeling must be maximal.
To prove the more general case, we first note that increases as increases so if we can force all the vertices not on the maximal clique to be zero, we win. Consider any two vertices not connected by an edge, say and . The value of the labeling is then linear in and , as the value is computed as , where is the sum of the vertices connected to , is the sum of the vertices connected to , and is the value of the graph with removed. This is achieves its maximum at either or depending on the values of . We repeat this process, until every pair of non-connected vertices has one labelled with value . We can then remove them from our graph. as they contribute nothing to our labeling. Our graph is now complete, which we know how to maximize. Different choices of zero assignments lead to different resulting complete graphs, but there is always a set of zero assignments that removes all vertices not belonging to the maximal clique.
Bonus Problem (2019 AIME I-14): Find the smallest odd factor of .
Bonus Solution: This odd factor must be prime. Notice , or . Therefore because we understand order. The smallest such primes are . Checking , we get , which is not the case for , so the answer is .