Elegant Problems

This section is dedicated to discussing some of my favourite problems I have come across in university mathematics competitions. I am always keen to see alternative solutions

Problem 1: Let a, b and c be the side lengths of a triangle with fixed perimeter 2s. As a, b and c vary, what is $\sup{\{(b-c)^2+(c-a)^2+(a-b)^2\}}$ ?

Problem 2: A standard deck of 52 cards is arranged at random face up in 4 rows and 13 columns. Show that by finitely many swaps of two cards of the same value (e.g. $7\clubsuit$ and $7\heartsuit$ ) the cards can be re-arranged so that each column contains one club, one heart, one spade and one diamond.

Problem 3: What is the area of the largest square contained in the unit cube?

Problem 4: An $n \times n$ real matrix $P$ is called an idempotent if $P^2 = P$ . Show that if $A$ , $B$ and $C$ are idempotents with $A+B+C = 0_n$ then they are all $0_n$ .

Problem 5: Let $x(t)$ be a twice differentiable function on $0 < t < \pi/2$ such that $x(0) = 0$ and $\dot{x}(0) = 1$ . Suppose that $\ddot{x} + x \geq 0$ . Prove that $x \geq \sin(t)$ . Is the converse true?

Problem 6: Prove that for every finite graph, you can colour the vertices black or white so that at least half the neighbours of every white vertex are black and at least half the neighbours of every black vertex are white.

To appreciate the nature of the problems, the (mathematical) reader should attempt to solve them before reading on.

Problem 1 – Maximising the side differences in a triangle

Let a, b and c be the side lengths of a triangle with fixed perimeter 2s. As a, b and c vary, what is $\sup{\{(b-c)^2+(c-a)^2+(a-b)^2\}}$ ?

My Solution:

We can assume W.L.O.G. that $0 < a \leq b \leq c < s$ .

$c < a+b \Rightarrow (c-b)^2 < a^2$ and $(c-a)^2 < b^2$
$b < a+c \Rightarrow (b-a)^2 < c^2$
Adding these 3 inequalities, we have
$(b-c)^2+(c-a)^2+(a-b)^2 < a^2+b^2+c^2$ (*)

Clearly $2s^2=a^2+b^2+c^2+(s-a)a+(s-b)b+(s-c)c$ , so $a^2+b^2+c^2 < 2s^2$ .
It follows from (*) that $(b-c)^2+(c-a)^2+(a-b)^2 < 2s^2$ .

But letting $a \rightarrow 0$ we have $(b-c)^2+(c-a)^2+(a-b)^2 \rightarrow (s-s)^2+(s-0)^2+(0-s)^2 = 2s^2$ .

Hence $\sup{\{(b-c)^2+(c-a)^2+(a-b)^2\}}=2s^2$

Problem 2 – A game of patience

A standard deck of 52 cards is arranged at random face up in 4 rows and 13 columns. Show that by finitely many swaps of two cards of the same value (e.g. $7\clubsuit$ and $7\heartsuit$ ) the cards can be re-arranged so that each column contains one club, one heart, one spade and one diamond.

My Solution:

Given any column $C$ with the following conditions satisfied:
(i) All columns to the left of $C$ are full-suit (i.e. contains a card from each suit)
(ii) $C$ is not full-suit
we can employ an algorithm which only swaps cards of the same value to bring a missing suit into $C$ , and also keep (i) true.

To explain the algorithm, suppose $C$ was missing a $\spadesuit$ , and had more than one $\clubsuit$ . Then the algorithm to replace a $\clubsuit$ with a $\spadesuit$ in $C$ goes as follows:

set $A:=C$ ( $A$ being the ‘active column’.)
set $OutCard := \text{any } \clubsuit \text{ card in } C$
(*)
set $InCard := \spadesuit\text{ card with same value as }OutCard$
swap $InCard$ and $OutCard$
mark $A$ as visited
if $OutCard$ is in a column to the right of $C$
stop
else ( $OutCard$ must be in a column to the left of $C$ .)
set $A := \text{column containing }OutCard$
set $OutCard := \text{the other }\clubsuit\text{ card in } A$
repeat from (*)
endif

For example, if the cards were arranged as follows
$\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 7\heartsuit & 9\diamondsuit & 10\spadesuit & \text{Q}\heartsuit & \text{K}\clubsuit & 10\diamondsuit \\ 7\clubsuit & 8\clubsuit & 5\clubsuit & 7\diamondsuit & 8\diamondsuit & 10\clubsuit \\ \text{J}\spadesuit & \text{Q}\spadesuit & 6\diamondsuit & 5\spadesuit & \text{A}\heartsuit & 4\heartsuit \\ \text{Q}\diamondsuit & 10\heartsuit & 3\heartsuit & \text{J}\clubsuit & \text{A}\spadesuit & 3\clubsuit \end{array}$
then the algorithm above will generate the following moves to swap $10\clubsuit$ in column 6 for $10\spadesuit$ in column 3:
$10\clubsuit$ in column 6 is swapped with $10\spadesuit$ in column 3,
$5\clubsuit$ in column 3 is swapped with $5\spadesuit$ in column 4,
$\text{J}\clubsuit$ in column 4 is swapped with $\text{J}\spadesuit$ in column 1,
$7\clubsuit$ in column 1 is swapped with $7\spadesuit$ in a column to the right of column 6

The above algorithm will always terminate. In order to visit a column that was already visited before, the current active column must also have been visited before. For example, suppose a visited column contains $2\spadesuit$ . Then to visit this column again, the active column, $A$ , must contain $2\clubsuit$ , which implies $A$ must have been visited before because $2\clubsuit$ can only be in $A$ if it was swapped from $2\spadesuit$ . Thus if $A$ has not been visited, then the next column assigned to $A$ would not have been visited. i.e. The algorithm will never visit any column more than once.

Thus an upper bound for number of swaps required for a card in the $c^\text{th}$ column is $c$ . Any column will need at most 3 new suits. So the $c^\text{th}$ column will require at most $3c$ swaps to make it full-suit. We can make all columns full-suit by using the algorithm to make the leftmost non-full-suit column full-suit until all columns are full-suit.

Hence an upper bound for the total number of swaps required is $\sum_{c=1}^{12}3c=234$ .

Problem 3 – Square in a cube

What is the area of the largest square contained in the unit cube?

My Solution:

First we find (one of) the longest possible pair $\mathbf{a}$ , $\mathbf{b}$ of orthogonal vectors of the same length lying inside the unit cube. Then the length of the diagonals of any square in the unit cube cannot exceed the length of these vectors.

Let $\mathbf{a}\in A=\{(x,y,z):x,y,z\in [0,1]\}$ , and $\mathbf{b}\in B=\{(x,y,z):x,z\in [0,1],\,y\in [-1,0]\}$ be position vectors.

We require $|\mathbf{a}| = |\mathbf{b}|$ and $\mathbf{a}\perp \mathbf{b}$ .

Given any $r\in (\sqrt{2},\sqrt{3})$ , the locus of terminal points for $\mathbf{a}$ such that $|\mathbf{a}| = |\mathbf{b}| =r$ is the part of the sphere $x^{2}+y^{2}+z^{2}=r^{2}$ contained in $A$ . Similarly the locus of terminal points for $\mathbf{b}$ is the part of the sphere contained in $B$ . Let $\theta$ denote the angle between $\mathbf{a}$ and $\mathbf{b}$ . Clearly $\theta$ is maximised when $\mathbf{a}$ and $\mathbf{b}$ are positioned such that $\mathbf{a}=(a,1,1)$ and $\mathbf{b}=(1,-1,a)$ , $a\in (0,1)$ . $|\mathbf{a}|=|\mathbf{b}|$ is maximised when $a$ is.
$\mathbf{a}\cdot \mathbf{b}=2a-1$
$a>\frac{1}{2}\Rightarrow \mathbf{a}\cdot \mathbf{b}=|\mathbf{a}| |\mathbf{b}| \cos \theta >0\Rightarrow \theta <90^\circ$
Thus the maximum value of $a$ for which $\mathbf{a}\perp \mathbf{b}$ can be satisfied is $a=\frac{1}{2}$ .

By inspection, a square with vertices $(1,0,\frac{3}{4})$ , $(\frac{1}{4},0,0)$ , $(0,1,\frac{1}{4})$ , $(\frac{3}{4},1,1)$ has diagonals corresponding to $\mathbf{a}=(\frac{1}{2},1,1)$ , and $\mathbf{b}=(1,-1,\frac{1}{2})$ .

Hence the largest square has area $\left( \frac{3}{4}\right) ^{2}+\left(\frac{3}{4}\right) ^{2}=\frac{9}{8}$ units².

Problem 4 – Idempotent matrices

An $n \times n$ real matrix $P$ is called an idempotent if $P^2 = P$ . Show that if $A$ , $B$ and $C$ are idempotents with $A+B+C = 0_n$ then they are all $0_n$ .

My Solution:

We have $A^2 = A$ , $B^2 = B$ , $C^2 = C$ .

Let $\mathbf{y} \in \text{range}(A) \subseteq \mathbb{R}^n$ . Then $\exists \, \mathbf{x} \in \mathbb{R}^n$ s.t. $\mathbf{y}=A\mathbf{x} \Rightarrow A\mathbf{y}=A^2 \mathbf{x}=A \mathbf{x}=\mathbf{y}$ .

$C=-A-B$ and $C^2=C \Rightarrow (A+B)^2=-A-B \Rightarrow 2A+2B+AB+BA=0_n$
Post-multiplying both sides by $\mathbf{y}$ yields
$2A\mathbf{y}+3B\mathbf{y}+AB\mathbf{y}=\mathbf{0}$ (1)

Re-writing (1), $B\mathbf{y}=-\frac{1}{3}A(2I_n+B)\mathbf{y}$ , we clearly see
$BAB\mathbf{y}=BB\mathbf{y}=B\mathbf{y}$ (2)

Pre-multiplying (1) by $B$ , and using (2),
$2BA\mathbf{y}+3B^2\mathbf{y}+BAB\mathbf{y}=2B\mathbf{y}+3B\mathbf{y}+B\mathbf{y}=\mathbf{0} \Rightarrow B\mathbf{y}=\mathbf{0}$ . By symmetry, $C\mathbf{y}=\mathbf{0}$ also.

$A+B+C=0_n \Rightarrow A\mathbf{y}+B\mathbf{y}+C\mathbf{y}=A\mathbf{y}=\mathbf{y}=\mathbf{0} \Rightarrow \text{range}(A)=\{\mathbf{0}\}$ $\Rightarrow A=0_n$ , and by symmetry, $C=B=A=0_n$ .

Problem 5 – A differential inequality

Let $x(t)$ be a twice differentiable function on $0 < t < \pi/2$ such that $x(0) = 0$ and $\dot{x}(0) = 1$ . Suppose that $\ddot{x} + x \geq 0$ . Prove that $x \geq \sin(t)$ . Is the converse true?

My Solution:

Let $y(t)=\frac{x(t)}{\sin t}=x(t) \csc t$ for $t \in (0,\frac{\pi}{2})$ .

$\dot{y}=\dot{x} \csc t + x(- \csc t \cot t)=(\dot{x}-x \cot t)\csc t$
$\begin{array}{rcl} \ddot{y} & = & -\csc t \cot t (\dot{x}-x \cot t) + \csc t (\ddot{x}-\dot{x} \cot t -x(-\csc^2 t)) \\ & = & \ddot{x} \csc t - 2\dot{x}\csc t \cot t + x \csc t(\csc^2 t + \cot^2 t) \\ & \geq & - 2\dot{x}\csc t \cot t + x \csc t(\csc^2 t -1 + \cot^2 t) \text{ since } \ddot{x} \csc t \geq -x \csc t \\ & = & - 2(\dot{x}-x \cot t)\csc t \cot t \\ & = & -2 \dot{y}\cot t \end{array}$
So $y$ satisfies $\ddot{y}\geq-2 \dot{y} \cot t \Leftrightarrow -\ddot{y} \sin t \leq 2 \dot{y} \cos t$ for $t \in (0,\frac{\pi}{2})$ .

Now consider $z(t)=\dot{y}(t) \sin^2 t=\dot{x}(t) \sin t - x(t) \cos t$ .
$\dot{z}=\ddot{y} \sin^2 t + 2\dot{y} \sin t \cos t \geq \ddot{y} \sin^2 t - \ddot{y} \sin^2 t=0$ and $z(0)=\dot{x}(0)\cdot 0=0 \Rightarrow z\geq 0 \Rightarrow \dot{y}\geq 0$
$x(0)=0$ , so by L’Hopital’s rule, $\lim\limits_{t \to 0^+} y(t)=\frac{\dot{x}(0)}{\cos 0}=\dot{x}(0)$ .
Hence $y(t)\geq \dot{x}(0) \Rightarrow x(t)\geq \dot{x}(0)\sin t = \sin t$ for $t \in (0,\frac{\pi}{2})$ .

The converse is false. Consider $x(t)=\sin t - t^2 (t-\frac{\pi}{2})\geq\sin t$ on $(0,\frac{\pi}{2})$ . $x(0)=0$ .
$\dot{x}=\cos t - 3t^2 +\pi t \Rightarrow \dot{x}(0) = 1$
$\ddot{x}=-\sin t - 6t +\pi$
$\ddot{x}+x=-t^3+\frac{\pi}{2}t^2- 6t +\pi=-1+\frac{\pi}{2}-6+\pi<-7+\frac{4}{2}+4<0$ at $t=1 \in (0,\frac{\pi}{2})$ .

Problem 6 – Black and white graphs

Prove that for every finite graph, you can colour the vertices black or white so that at least half the neighbours of every white vertex are black and at least half the neighbours of every black vertex are white.

Note: There is an incredibly elegant one line solution to this problem (which I have not included here). Try to think of this solution before reading on. Hint: Pick a graph satisfying a particular property.

My Solution:

Note: Clearly no loops are allowed. Consider the graph consisting of only one node and one edge from the node to itself.

Given any graph not satisfying the above property, the following algorithm will re-colour the graph so that it does satisfy the property:

(1) Pick any node $N$ with strictly less than $\frac{1}{2}\deg(N)$ different coloured neighbours.
(2) Change the colour of $N$ (white to black / black to white)
(3) If the graph now satisfies the property, stop. Else repeat from (1).

Each time (2) occurs, the number of pairs of differently coloured nodes increases by at least 1. Thus the algorithm must terminate for any finite graph, for if it doesn’t then there will be infinitely many pairs of differently coloured nodes, which implies the graph is infinite, a contradiction.

Wilson Ong's Blog