Solutions of Dedekind's Mathematical Olympiad 2017
1. Compute the following limit, where $\newcommand{\floor}[1]{\lfloor#1\rfloor}\floor x$ denotes the greatest integer less than or equal to $x$
\[\lim_{n\to\infty}\frac1{n^2}(\floor{2\pi}+\floor{4\pi}+\floor{6\pi}+ \dots+\floor{2n\pi})\\]
We can sandwich the succession between two limits:
\[\begin{equation} \begin{split} \pi &= \lim_{n\to\infty}\frac1{n^2}(2\pi-1+4\pi-1+6\pi-1+ \dots+2n\pi -1)\le L\\ L& \le \lim_{n\to\infty}\frac1{n^2}(2\pi+1+4\pi-1+6\pi+1+ \dots+2n\pi +1) =\pi \end{split} \end{equation}\]2. Let $(x_n) _ {n=1} ^ \infty$ be a succesion of real numbers. Study the convergence of the succession $(\sin^n x_n)_{n=1}^\infty$
Clearly every term is within the interval $[-1, 1]$. We note that $\sin$ is monotone map in this interval, and therefore the succession is sandwiched between the successions $(\sin^{n-1} -1) _ {n=1} ^ \infty$ and $(\sin^{n-1}1) _ {n=1}^\infty$.
Furthermore, $\sin$ is contractive in the interval, and thus has a single fixed point (which is obviously zero) to which both series converge.
Thus we conclude that the series converges for every starting succession to zero.
3. The diagonalization lemma implies that for every sentence A, there is a sentence S such that it can be proven that S is equivalent to “If there exists a proof of S, then A”.
Another indication: one well known property of proofs is that when you can prove a proposition, you can also prove that there exists a proof.
a) “Prove” that $1=2$ (indication: use the diagonalization lemma) Let’s consider S such that it can be proven equivalent to “if there is a proof of S, then $1=2$”.
We will try to prove $S$.
Suppose that there is a proof that concludes $S$. Then we could also prove that there is a proof of $S$ (1).
On the other hand, since we can prove $S$ we can also prove that “if there is a proof of S, then $1=2$”, since that can be proven equivalent to $S$ by construction. From this fact and (1) above, we could conclude that there exists a proof of $1=2$ (it follows from modus ponens applied as a last step to this hypothetical proof of S).
And if there a proof of $1=2$, it better be true, right?
b) (Löb’s theorem) Prove that if from the existence of the proof of a proposition we could deduce its truth, then the sentence must be neccesarily true.
Notice that we could substitute in the solution to a the proposition $1=2$ for any other proposition. But the last step is flawed, since we cannot deduce from the existence of a proof of $1=2$ that $1=2$ is true. If that was possible we would be able to prove any nonsense!
Therefore a neccessary condition to be able to prove that we can deduce from the existence of a proof of a proposition the truth value of the proposition it must happen all along that the proposition was true, which is what Löb’s states.
4. (Banach-Tarski paradox in the plane) We say that two sets $A$ and $B$ are equidecomposables and we will write such thing as $A\sim B$ if there exists $A_1 , …,A_n$ and $B_1,…,B_n$ pairwise disjoint and $g_1,…,g_n$ rotations or translations such that:
- $g_i A_i =B_i\, \forall i$
- $A_1 \uplus … \uplus A_n = A$
- $B_1 \uplus … \uplus B_n = B$
Show that $\mathbb{S}^1\sim \mathbb{S}^1\setminus{p}$, where $p$ is any point on the circle
\[\mathbb{S}^1 = \lbrace(x, y) : x^2 + y^2 = 1\rbrace.\]
Pick a rational rotation $\theta$ and consider the set formed by the succesive application of the rotation to the missing point in the circumference. Since the rotation is rational, you never fall twice in the same point, and therefore if you apply the inverse of the rotation to the set while leaving the rest of the circumference unchanged you end up with the whole circumference.
Thus both figures are equidescomposable.
5. (The white / yolk theorem) Let $C_1, C_2$ be two simple, closed curves in the plane, one inside the other. Prove that there can be found a straight line that divides each of the regions delimited by both curves in half.
Choose any direction of the plane and orientation, and first focus in either of the curves, the outer for example.
Trace two lines along the direction such that the curve falls within the region in between, and now consider the function that maps each of this lines to the difference between the area of the curve in its left and the region in its right. Clearly this function is continuous for all lines in this direction and orientation, and the two lines we drew are mapped to different signs. We can therefore conclude that there exists an unique middle line which splits the curve in half.
If we consider the map from directions and orientations to the unique lines that split the outer curve along that direction, and from there to the difference of areas in the left and right of the line, but of the inner curve, then we have another continuous map. Taking any direction, it so happens that its orientations are mapped to different signs, and therefore again due to the middle point therem, there is a direction in between that splits both areas in half.
6. Compute the limit
\[\lim_{n\to\infty}\frac1n\sum_{i,j=1}^n\frac1{i+j}\]
It we let
\[x_n:=\sum_{i=1}^n\sum_{j=1}^n\frac1{i+j}\]then it suffices to compute the limit
\[\lim_{n\to\infty}(x_{n+1}-x_n) =2\lim_{n\to\infty}\sum_{i=1}^n\frac1{i+n},\]but the computation is easy noting that the right hand side is a Riemann sum,
\[\sum_{i=1}^n\frac1{i+n} =\frac1n\sum_{i=1}^n\frac1{i/n+1}\to\int_0^1\frac1{1+x}\,dx =\log 2.\]Hence, the limit is $2\log2$.
7. Let $P_1,\dots,P_{2017}$ be the vertices of a regular $2017$-gon inscribed on the unit circle. Let $Q_j$ the distance between $P_1$ and $P_j$ ($j=2,\dots,2017$.) Compute \(\prod_{j=2}^{2017}Q_j.\)
Let $n=2017$. Then the vertices are the numbers $\zeta_j:=\exp(2\pi ij/n)$, so we have to compute
\[\begin{align*} \prod_{j=2}^n|\zeta_0-\zeta_j|&=\prod_{j=2}^n|1-\zeta_j|\\ &=\sqrt{\prod_{j=2}^n(1-\zeta_j)(1-\zeta_{n-j})}\\ &=\prod_{j=2}^n(1-\zeta_j)\\ &=\lim_{X\to1}\frac{1-X^n}{1-X}=n. \end{align*}\]8. Compute
\[\int_0^\infty\frac{\arctan(\sqrt[4]{x})}{\sqrt x(1+x)}\,dx.\]
The integral is $\pi^2/4$. Indeed, the change $x\mapsto 1/x$ and the identity $\arctan x+\arctan x^{-1}=\pi/2$ yield plainly the result.
Additional exercise: what happens if you replace $\arctan(\sqrt[4]{x})$ with $\arctan(x^a)$ for some real $a$?
9. (Finite sandpile abelian model) Let $D=\{x\in M_{2\times 3}:x_{ij}=0,1,2,3\}$. We define an operation $\oplus : D \times D \rightarrow D$ in the following way: To calculate $A\oplus B$ we first do the usual sum $C=A+B$, and then, if there is an entry $c_{ij}$ greater or equal to $4$ in the sum matrix $C$, we substract 4 from that entry and add 1 to the four nearby ones $c_{i-1,j}$, $c_{i+1,j}$, $c_{i,j+1}$ and $c_{i,j-1}$ if they exist at all. We repeat this last step until $c_{ij}\leq 3$ for all $i, j$. Let
\[T = \left[ \begin{array}{ccc} 3 & 3 & 3 \\ 3 & 3 & 3 \end{array} \right].\]a) Compute $2017\times T = \underbrace{T \oplus T \oplus \dots \oplus T}_{2017\text{ times}}$
As we do not know much about operating matrices with the operation $\oplus$, we should try to compute it with brute strength, decomposing 2017 into powers of 2 and computing $T, 2\times T, 4\times T \dots$ and so on: \(2\times T = \left[ \begin{array}{ccc} 3 & 3 & 3 \\ 3 & 3 & 3 \end{array} \right] \oplus \left[ \begin{array}{ccc} 3 & 3 & 3 \\ 3 & 3 & 3 \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 6 & 6 & 6 \\ 6 & 6 & 6 \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 4 & 5 & 4 \\ 4 & 5 & 4 \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 2 & 4 & 2 \\ 2 & 4 & 2 \end{array} \right] = \left[ \begin{array}{ccc} 3 & 1 & 3 \\ 3 & 1 & 3 \end{array} \right]\) \(4\times T = 2\times T \oplus 2\times T = \left[ \begin{array}{ccc} 6 & 2 & 6 \\ 6 & 2 & 6 \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 3 & 4 & 3 \\ 3 & 4 & 3 \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 4 & 1 & 4 \\ 4 & 1 & 4 \end{array} \right] = \left[ \begin{array}{ccc} 1 & 3 & 1 \\ 1 & 3 & 1 \end{array} \right]\) \(8\times T = 4\times T \oplus 4\times T = \left[ \begin{array}{ccc} 2 & 6 & 2 \\ 2 & 6 & 2 \end{array} \right] = \left[ \begin{array}{ccc} 3 & 3 & 3 \\ 3 & 3 & 3 \end{array} \right]\)
Thus we see that $8\times T = T$ and so $T \oplus 7\times T = T$. Dividing by 7 we discover that $2017 = 7\cdot 288 + 1$ and therefore: \(2017\times T = T \oplus \underbrace{7\times T \oplus 7\times T \oplus \dots}_{288\text{ times}} = T\)
b) Prove that $D \oplus T$ is a group under operation $\oplus$, which may be assumed to be asociative.
It is obvious that $\oplus$ is conmutative, because it is based in the usual matrix sum. We first must find the identity of such a group, and we know from a) that it is $7\times T$, but we can find it without that information. It suffices to show that $Id \oplus T$, because then for every $T \oplus G \in D$ we have that $(T \oplus G) \oplus Id = Id \oplus (T \oplus G) = (Id \oplus T) \oplus G = T \oplus G.$
Let $Id = T\oplus X$. Then $T \oplus T \oplus X = T$, and $X = T - (T \oplus T)$ and we can easily check that $T\oplus T \oplus X = (T\oplus T) \oplus (T - (T\oplus T)) = T.$
We must now find an inverse for any element $A \in D$. This can be acomplished by taking as inverse $Id \oplus (T - A) \oplus X$, which is indeed an inverse of $A$ and belongs to $D$ because it can be written as $T \oplus X \oplus X \oplus (T - A)$. Finally the operation is closed in $D,$ as $(T \oplus A) \oplus (T \oplus B) = T \oplus (T \oplus A \oplus B)$.
11. We know that the product modulo a prime has the structure of a cyclic group.
a) Prove that if a prime $p$ divides $x^2 + x + 1$ for some integer $x$, then either $p = 3$ or $p-1$ is a multiple of 6.
We note that if $x^2 + x + 1 \equiv 0$ (mod $p$) then $0\equiv (x^2 + x + 1)(x - 1) \equiv x^3 - 1$ and $x^3 \equiv 1$ (mod $p$) This means one of two things: either $x \equiv 1$, $x^2 + x + 1 \equiv 3 \equiv 0$ and $p=3$, or the order of $x$ in the group of product modulo $p$ is a multiple of 3, and so the order of the group is also a multiple of 3. As the order of the group is $p-1$, we have that $3|p-1$, and if $p= 2$, then $3\nmid p-1$. Therefore $p$ is odd, $p-1$ is even, and if it’s even and a multiple of 3 it is a mutiple of 6.
Remark: $x^2+x+1$ is the 3rd cyclotomic polynomial, whose roots are the primitive third roots of unity.
b) Prove the same thing than in a) for $x^2 + x + 7$.
We will use the Legendre symbol, where $(a/b)$ is 0 if $b\mid a$, 1 if $a$ is a quadratic residue modulo $b$, and -1 otherwise.
Also, we can assume that $p \neq 3$; otherwise we would be done.
We notice that, as $x^2 + x + 7$ is always odd, then $p\mid x^2 + x + 7 \Longleftrightarrow p\mid 4x^2 + 4x + 28 = (2x + 1)^2 + 27$
So if $p$ divides $x^2 + x + 7$ then $-27$ is a quadratic residue modulo $p$, and \[1 = (-27/p) = (-1/p)\cdot (3/p)^3=(-1/p)\cdot (p/3)\cdot (-1/p) = (p/3).\]
The next-to-last step deserves some explanation: We know by quadratic reciprocity that if $p$ and $q$ are odd primes, $(p/q) = -(q/p)$ if $q\equiv p \equiv 3 \text{ (mod 4)}$ and $(q/p) = (p/q)$ otherwise. Also, $(-1/p) = (-1)^{(p-1)/2}$. Therefore we can pass $(3/p)$ as $(p/3)$ with a factor $(-1/p)$.
So finally we know that $p$ is a quadratic residue modulo 3, and the only quadratic residue mod 3 other than 0 is 1, so $p\equiv 1$ (mod 3), $3\mid p-1$ and recalling that $p$ is odd we get that $6\mid p-1$.
Additional exercise: prove the converse!