Simon Marais Mathematics Competition 2019

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 s_1 = 2. Define a recursive sequence by letting s_{n + 1} be the sum of s_n and the product of its distinct prime factors. So the sequence goes 2, 4, 6, 12, 18, 24, \dots. Prove that the product of the first 2019 primes is in this sequence.

Solution A1: Let the primes be p_1, p_2, \dots. We claim that for every n, \displaystyle{\prod_{i = 1}^n p_i} is in the sequence. Clearly p_1 = 2 is in this sequence. Now suppose N = p_1 \cdots p_j is in this sequence. The sequence then continues, N, 2N, 3N, \dots. Eventually, we will reach a p_{j + 1} N because the only distinct prime factors of N, 2N, \dots, (p_{j + 1} - 1)N are p_1, \dots, p_j. Therefore p_1 \cdots  p_{j + 1} is a term of the sequence.

Problem A2: Consider the operation * that is defined by a * b = a \times (b + 1). Let a_1, \dots, a_n and b_1, \dots, b_n be permutations of 1, \dots, n. Find all such permutations that maximize

    \[ ( \cdots ( (a_1 * a_2) * a_3 ) * \cdots * a_n) \]

and

    \[ b_1 * (b_2 * (b_3 * \cdots * (b_{n - 1} * b_n) \cdots )). \]

Solution A2: For the a_i, we expand. This is a_1 (a_2 + 1) (a_3 + 1) \cdots (a_n + 1) = \dfrac{a_1}{a_1 + 1} \cdot (a_1 + 1) \cdots (a_n + 1). \displaystyle{\prod (a_i + 1)} is constant so we maximize the fraction by picking a_1 = n. For the b_i, we expand as well. The expression expands to

    \[ \sum_{i = 1}^n \prod_{j = 1}^i b_j. \]

Since b_1 is a factor in every term, we must maximize b_1 to maximize the expression. Thus b_1 = n. Now b_2 occurs in all the remaining terms, etc. Thus b_1, \dots, b_n = n, \dots, 1.

Problem B1: Find a, b such that

    \[ \int_a^b e^{\cos (x)}(380 - x - x^2) dx \]

is maximized.

Solution B1: e^x > 0 for all real x. Notice 380 - x - x^2 is non-negative on a bounded interval. Thus the integral achieves its maximum on this interval. 380 - x - x^2 = -(x + 20)(x - 19) so (a, b) = (-20, 19).

Problem B2: Prove that the number

    \[ 1! + 2! + 3! + \cdots + p! - \left\lfloor \frac{(p-1)!}{e} \right\rfloor \]

is divisible by p for all primes p.

Solution B2: This solution is a bit more involved unfortunately.

We begin by making the computation

    \[ \begin{aligned} \sum_{k = 1}^{p - 1} k! &\equiv \dfrac{(p - 1)!}{1} + \dfrac{(p - 1)!}{p - 1} + \dfrac{(p - 1)!}{(p - 1)(p - 2)} + \cdots + \dfrac{(p - 1)!}{(p - 1) \cdots (2)} &\pmod{p} \\ &\equiv \dfrac{-1}{1} + \dfrac{-1}{-1} + \dfrac{-1}{(-1)(-2)} + \cdots + \dfrac{-1}{(-1) \cdots (2 - p)} &\pmod{p} \\ &\equiv -\sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!}. &\pmod{p} \\ \end{aligned} \]

We then take a slight detour into Maclaurin series. The closest fraction of the form \dfrac{q_k}{k!} to \dfrac{1}{e} = e^{-1} is exactly of the form \displaystyle{\sum_{j = 0}^k \dfrac{(-1)^j}{j!}}. This is motivated by expanding \displaystyle{e^x = \sum_{i = 0}^{\infty} \frac{x^i}{i!}}. By analyzing the error, we determine that it is indeed at most \dfrac{1}{(k + 1)!}, meaning that a different choice of q_k yields a larger error.

Now let k be an odd number. We can easily see that

    \[ \displaystyle{\frac{k!}{e} = q_k + \sum_{j = k + 1}^{\infty} \frac{k! (-1)^j}{j!}}, \]

where \displaystyle{\left|\sum_{j = k + 1}^{\infty} \frac{k! (-1)^j}{j!}\right| < 1}. Therefore \displaystyle{q_k = \left\lfloor \frac{k!}{e} \right\rfloor}, because then the error term is > 0. We can also see that

    \[ \displaystyle{\frac{(k + 1)!}{e} = (k + 1)q_k + \sum_{j = k + 1}^{\infty} \frac{(k + 1)! (-1)^j}{j!} = (k + 1)q_k + (-1)^{k + 1} + \sum_{j = k + 2}^{\infty} \frac{(k + 1)! (-1)^j}{j!}}, \]

where \displaystyle{\left|\sum_{j = k + 2}^{\infty} \frac{(k + 1)! (-1)^j}{j!}\right| < 1}. We then see that \displaystyle{(k + 1)q_k = \left\lfloor \frac{(k + 1)!}{e} \right\rfloor}. Let us substitute k = p - 2. We obtain,

    \[ \left \lfloor \frac{(p - 1)!}{e} \right \rfloor \equiv (p - 1) q_{p - 2} \equiv -q_{p - 2} \equiv -\left \lfloor \frac{(p - 2)!}{e} \right \rfloor \pmod{p}. \]

We can then compute

    \[ -(p - 2)! \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} \equiv -q \equiv -\left\lfloor \frac{(p - 2)!}{e} \right\rfloor \equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor \pmod{p}, \]

and with a bit more magic we get

    \[ \begin{aligned} -(p - 1)! \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv (p - 1)\left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ -(-1) \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv -\left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ -\sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ \sum_{k = 1}^{p - 1} k! &\equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor, &\pmod{p} \\ \end{aligned} \]

as desired.

Problem B3: Let G be a finite simple graph and let k be the largest number of vertices of any clique in G. Suppose that we label each vertex of G with a non-negative real number, so that the sum of all such labels is 1. Define the value of an edge to be the product of the labels of the two vertices at its ends. Define the value of a labeling to be the sum of values of the edges.

Prove that the maximum possible value of a labeling of G is \dfrac{k - 1}{2k}.

Solution B3: We first solve it for complete graphs of size n = k. Clearly the claimed maximum value is achieved by letting each vertex have value \dfrac{1}{n}. Each edge has value \dfrac{1}{n^2} and there are \dbinom{n}{2} = \dfrac{n(n - 1)}{2} of them. Therefore the labeling of this graph has value \dfrac{n(n - 1)}{2n^2} = \dfrac{n - 1}{2n}. We now prove that this is a maximum. Let v_1, \dots, v_n be the values. The value V is computed as

    \[ V = \sum_{i < j} v_i v_j \]

Suppose v_i \neq v_j for some i, j. Assume WLOG that they are v_1, v_2. We replace v_1 and v_2 with v' = \dfrac{1}{2}(v_1 + v_2). Compute

    \[ \begin{aligned} \sum_{i < j} v_i v_j &= v_1 v_2 + \sum_{i > 3} (v_1 v_i + v_2 v_i) + \sum_{3 \leq i < j} v_i v_j \\ &= v_1 v_2 + \sum_{i > 3} (v' v_i + v' v_i) + \sum_{3 \leq i < j} v_i v_j \end{aligned} \]

Since v'^2 > v_1 v_2, this new labeling achieves a greater value. Since any labeling where two values differ is not maximal, our labeling v_1 = \cdots = v_n = \dfrac{1}{n} must be maximal.

To prove the more general case, we first note that \dfrac{k - 1}{2k} increases as k 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 v_1 and v_2. The value of the labeling is then linear in v_1 and v_2, as the value is computed as v_1 x + v_2 y + z, where x is the sum of the vertices connected to v_1, y is the sum of the vertices connected to v_2, and z is the value of the graph with v_1, v_2 removed. This is achieves its maximum at either v_1 = 0 or v_2 = 0 depending on the values of x, y. We repeat this process, until every pair of non-connected vertices has one labelled with value 0. 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 2019^8 + 1.

Bonus Solution: This odd factor must be prime. Notice 2019^8 \equiv -1 \pmod{p}, or 2019^{16} \equiv 1 \pmod{p}. Therefore 16 \mid p - 1 because we understand order. The smallest such primes are 17, 97, \dots. Checking 2019^8 + 1 \pmod{97}, we get 0, which is not the case for 17, so the answer is \boxed{097}.

This entry was posted in Math. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *