IOQM 2023 Apple Mock One

This is the first ever public IOQM mock test of MOMC. The problems are taken from CHMMC 2012 Spring, PUMaC 2020 and HMMT 2009 Feb Guts Round. All the credit and authorship of the problems belongs to their respective sources.

I had a fun time making the mock, as well as naming it. Last year's mocks' names were of the format <abbreviation of month>_number (Eg: SP3). To switch things up this year, I decided to name them after a fruit instead.

I wasn't able to fit in some nice problems in the test, so I added them as bonus problems at the end. Try them out as well! Now I wish to share with you, the key ideas of some of my favourite problems in the test. So if you are planning to attempt the mock, beware of the spoilers ahead.

Problem 15: $\textbf{(PUMaC 2020 Algebra A P4)}$ Let $P$ be a $10$-degree monic polynomial with roots $r_1, r_2, \ldots, r_{10} \neq 0$ and let $Q$ be a $45$-degree monic polynomial with roots $\frac{1}{r_i}+\frac{1}{r_j}-\frac{1}{r_i r_j}$ where $i<j$ and $i, j \in\{1, \ldots, 10\}$. If $P(0)=Q(1)=2$, then $\log _2(|P(1)|)$ can be written as $\frac{a}{b}$ for relatively prime integers $a, b$. Find $a+b$.

Solution: This problem is a very cool yet simple example of representing a polynomial as the product of $(x-\alpha_i)$ where $\alpha_i$ is one of its root. So we write $Q$ as:

Now we want to manipulate this expression in order to be able to use the value of $P(0)$,$Q(1)$ and compute $P(1)$. So we substitute in $x = 1$ to get: $Q(1)=\prod_{i<j}\left(1-\frac{1}{r_i}-\frac{1}{r_j}+\frac{1}{r_i r_j}\right)$ Thus we know that this expression is equal to $2$. Now note that the denominators resemble something like $(1-r_i)(1-r_j)$, which reminds us that we can write $P(x)$ as $\prod_{i=1}^9 (1-r_i)$ which is a good sign. Thus taking the common fraction we get:

Now we can use $P(0) = 2$ as it is the product of roots, thus the fraction evaluates to $\frac{P(1)^9}{2^9}$. So $P(1)^9 = 2^{10}$. From here, the answer is $\frac{10}{9}$.

Onto the next problem!

Problem 24: $\textbf{(CHMMC 2012 Individual P13)}$ Suppose that $a, b, c, d, e, f$ are real numbers such that

Find the sum of digits of $a+6 b+21 c+36 d+32 e+720 f$

Solution: Even after noticing the pattern in the coefficients, this problem seems very ugly and bashy. But it is actually very nice, believe it or not. This is a beautiful demonstration of finite differences. Firstly define $g(k) = a + kb + \frac{k(k-1)}{2}c + k^2 d + 2^ke + k!\cdot f$. The key observation is that the coefficients of $a,b,c,d$ are polynomials of degree atmost $2$. Thus we can feasibly use finite differences. Thus $g(k)-3 g(k-1)+3 g(k-2)-g(k-3)$ will have a coefficient of $0$ for all $a,b,c,d$. Thus we obtain the following three equations in the three variables $e,f$ and $g(6)$:

Solving the first two equations we get $f=1$ and $e = -11$. Plugging this into the third equation gives $g(6) = 508$.

Problem 30: $\textbf{(CHMMC 2012 Individual P11)}$ Let $F_0=0, F_1=1$, and $F_n=F_{n-1}+F_{n-2}$. How many subsets $S$ of $\{1,2, \ldots 99\}$ are there such that

Solution: This problem relies on some basic intuition about size regarding Fibonacci numbers. We claim that, in general for $F_{2n}-1$, the answer is $n$. We proceed by induction. The base case $n = 1$ is clear. Now suppose it is true for $n$. Notice that $F_{2n+2}-1$ is quite large compared to other fibonacci numbers (especially $F_i$ with $i \leq 2n$). Also remembering the identity $\sum_{k=1}^{2n} F_k = F_{2n+2}-1$, we are motivated to do casing on whether $F_{2n+1}$ is involved in the sum or not. If it is not involved, then the above identity implies that, to get the desired sum, we need to choose all the available fibonacci numbers. Thus there is only $1$ way in this case. Now if we do choose $F_{2n+1}$ then the rest of the sum is $F_{2n+2}-1 - F_{2n+1} = F_{2n} - 1$. Now by induction there are $n$ ways for this. Thus in total we have $n+1$ ways, completing the inductive step.

Proving the identity is not very difficult, for example, it can be shown by induction. If the result is true for $n$ then $\sum_{k=1}^{2n+2} F_k = \sum_{k=1}^{2n} F_k + F_{2n+1} + F_{2n+2} = F_{2n+2} + F_{2n+1} - 1 + F_{2n+2} = F_{2n+3} + F_{2n+2} - 1 = F_{2n+4} - 1$ completing the induction.

Now we would move on to a funny geometry problem

Problem 23: $\textbf{(CHMMC 2012 Team P10)}$ A convex polygon in the Cartesian plane has all of its vertices on integer coordinates. One of the sides of the polygon is $A B$ where $A=(0,0)$ and $B=(51,51)$, and the interior angles at $A$ and $B$ are both at most $45$ degrees. Assuming no $180$ degree angles, what is the maximum number of vertices this polygon can have?

Solution: As there is almost no condition on the sides of the polygon, we just consider the sides as vectors $v_1, v_2, \cdots v_k$, where $k$ is the number of sides minus one (Side $AB$ isn't considered in these vectors). Observe that the sum of entries of the vectors $v_1 + v_2 + \cdots v_k$ is $51$. Clearly all the entries are integers. Infact these integers must be non-negative. This is because the polygon must be convex and that the interior angles at $A$ and $B$ are both at most $45$ (Only proceed if you fully understand why). Now to maximize the number of vectors, we need the entries to be as small as possible. We write the "smallest" possible vectors until the sum of the entries is close to or equal to $51$. All the vectors with sum of $i$ and $j$ is less than or equal to $7$ is:

The sum of the entries is $46$. Now we show that $k \leq 20$. Suppose for the sake of contradiction that $k \geq 21$. Then we need to add atleast $2$ vectors with sum of both entries atleast $8$. Thus sum of all entries is atleast $46 \cdot 2 + 8 \cdot 2 = 108 > 102$.

The following construction is due to CHMMC Official Solutions: Take the list of $19$ vectors above along with $(3,5)$, and order them by the angle they make with the vector $(1,0)$ from smallest to largest (so the list starts with $(1,0)$ and ends with $(0,1)$ ). Make the sides of the polygon correspond to the vectors in this order and then replace $(1,0)$ with $(3,0)$. The increasing angle condition makes the polygon convex, the interior angles at $A$ and $B$ are exactly 45 degrees, and the sum of all the vectors is $(51,51)$.