Start of BMO series!

I'm going to be attempting some BMO1 questions over the course of the next few blog posts. Starting with 2017-2018 Problem 1 and working my way up from there.

Problem: Helen divides $365$ by each of $1, 2, 3, . . . , 365$ in turn, writing down a list of the $365$ remainders. Then Phil divides $366$ by each of $1, 2, 3, . . . , 366$ in turn, writing down a list of the $366$ remainders. Whose list of remainders has the greater sum and by how much?

Solution: First thing to notice is that Helen and Phil are dividing by consecutive numbers respectively. This is important because

$$365 = qk + r \quad \text{ where } 0 \leq r \leq k - 1 $$

$$366 = qk + (r + 1)$$

This implies that $365 \equiv r \pmod{k}$ and $366 \equiv r + 1 \pmod{k}$. From this we can derive the following rules:

1. If $k$ divides $365$ and $366$ evenly, then Helen and Phil both get remainder $0$.
2. If $k$ divides $366$ evenly and not $365$, then Helen gets remainder $k - 1$ while Phil gets remainder $0$.
3. Else, Phil gets remainder $1$ greater than Helen.

So if we determine which values of $k$ divide $365$ or $366$ then we can use our rules to determine the difference in remainder sums between Helen and Phil. We can do this by listing the factors of $365$ and $366$.

$$\text{Factors of 365} = \{1, 5, 73, 365\}$$

$$\text{Factors of 366} = \{1, 2, 3, 6, 61, 122, 183, 366\}$$

In all but $7$ cases (for the $7$ factors of 366 excluding $1$), we have rule 3. This means Phil's remainder sum is $365 - 7 = 358$ more than Helen at this stage.

$2, 3, 6, 61, 122, 183$ all divide $366$ evenly but not $365$. Hence Helen's remainder sum is increased by $1 + 2 + 5 + 60 + 121 + 182 = 371$. So Helen's remainder sum is $371 - 358 = 13$ larger than Phil's. We don't take into account $366$ as a factor because it is not included in Helen's list so does not affect the difference in remainder sums.

There you have it. The key to solving this problem is to stay systematic and clear. The actual approach required is the obvious one, but it's easy to make small counting errors if you don't keep organised.

Big-Ohhhh!

Problem: Let $f : \mathbb{Z_{\geq 0}} \mapsto \mathbb{Z_{\geq 0}}$ be a non-decreasing function satisfying the inequality

$$f(n) \leq \frac{2}{n - 1} \left(n^2 + \sum^{n - 1}_{i = 1}f(i)\right)$$

Prove that $f(n) = O(n\log n)$.

Solution: Notice that $\frac{1}{n - 1} \dot \sum^{n - 1}_{i = 1}f(i)$ is the average value of $f$ over the interval $[1, n - 1]$. This suggests expanding the inequality is a good idea because we can simplify our expression.

$$f(n) \leq \frac{2n^2}{n - 1} + 2f(j) $$

Where $f(j) > \frac{1}{n - 1}\sum^{n - 1}_{i = 1}f(i)$  for the minimum $j$. Note that $\frac{2n^2}{n - 1}$ is $O(n)$ so

$$f(n) \leq O(n) + 2f(j)$$

What happens if we recursively apply the process we have just applied for $f(n)$, to $f(j)$? And how many times do we apply this process in the worst case so that $f(j) = f(1)$?

At worst we apply this process $O(\log n)$ times. Therefore, following through with recursion we are left with

$$f(n) \leq \underbrace{O(n) + O(n) + ... + O(n)}_{O(\log n) \text{ times}} + 2^{O(\log n)}f(1) = O(n \log n) + O(n)f(1) = O(n \log n)$$

I came across this problem in a past paper for one of my algorithms course and enjoyed the process of solving it. It felt like a real thinking questions which you couldn't prepare for that much.