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.

Intuitive intro to polynomial time reductions.

The concept of a reduction is fundamental to organising computational problems by relative difficulty. Intuitively, this is useful because if we know problem $A$ to be "hard", and we can establish that problem $B$ is "at least as hard" as $A$, then we know $B$ must also be "hard". This can save a lot of time that could have been spent searching for some fast algorithm for $B$ which may not exist. 

So what is a polynomial time reduction?

Suppose we have two problems $X$ and $Y$. Now suppose that we already know how to solve $Y$ in polynomial time using procedure $P_Y$. If we could construct some procedure, $P_R$, which transforms any instance, $I_X$, of $X$ to an instance, $I_Y$, of $Y$, then we could use our solution to $Y$ to solve $X$ in polynomial time given that:

• $P_R$ runs in polynomial time.
• $I_Y$ as input to $P_Y$ outputs the correct answer for $I_X$.

This is an example of a polynomial reduction from $X$ to $Y$ (written $X \le_P Y$). Intuitively, it helps me to think of this as saying: $X$ is no harder than $Y$, or $Y$ is at least as hard as $X$. Just as relative easiness of a problem can be shown using polynomial reductions, so can relative hardness.

Suppose that there is no polynomial time solution for $Y$. If $Y \le_P X$, then it must be that $X$ is at least as hard as $Y$ and so there is no polynomial time solution for $X$.

Proof. Suppose for contradiction that there exists a polynomial time solution for $X$. Then by the definition of a polynomial time reduction, there would exist a polynomial time solution to $Y$. A contradiction.

Notice that this logic only works if $P_R$ runs in polynomial time.

Snazzy application of pigeonhole principle.

Problem: Prove that a simple graph $G$ with $n > 2$ vertices has at least two vertices with the same degree.

Solution: Notice that there is no guarantee that $G$ is connected. However let us suppose that it is. Then each vertex has degree $d$ where $d \in \{1, 2, ..., n - 1\}$. Since we have $n$ vertices and $n - 1$ degree choices, it must be that at least two vertices in $G$ have the same degree.

This proves the case when $G$ is connected, but what about when it is unconnected?

In this case, each vertex can connect to at most $n - 2$ vertices because for $G$ to be unconnected, there must exist a vertex which is connected to no other vertex. Therefore, each vertex has degree $d$ where $d \in \{0, 1, ..., n - 2\}$. By the same argument used in the connected case, $G$ must have at least two vertices of the same degree.

I thought this was a pretty snazzy approach. There is something so elegant about the pigeonhole principle.