Problems
Prove that the vertices of a planar graph can be coloured in (at most) six different colours such that every pair of vertices joined by an edge are of different colours.
Note: a graph is planar if it can be drawn in the plane with no edges
crossing. For example, three houses, each of which is connected to three
utilities, is not a planar graph.
You may find it useful to use the Euler characteristic: a planar graph
with \(v\) vertices, \(e\) edges and \(f\) faces satisfies \(v-e+f=2\).
Paloma wrote digits from \(0\) to \(9\) in each of the \(9\) dots below, using each digit at most once. Since there are \(9\) dots and \(10\) digits, she must have missed one digit.
In the triangles, Paloma started writing either the three digits at the corners added together (the sum), or the three digits at the corners multiplied together (the product). She gave up before finishing the final two triangles.
What numbers could Paloma have written in the interior of the red triangle? Demonstrate that you’ve found all of the possibilities.
How many subsets are there of \(\{1,2,...,10\}\) (the integers from \(1\) to \(10\) inclusive) containing no consecutive
digits? That is, we do count \(\{1,3,6,8\}\) but do not count \(\{1,3,6,7\}\).
For example, when \(n=3\), we have
\(8\) subsets overall but only \(5\) contain no consecutive integers. The
\(8\) subsets are \(\varnothing\) (the empty set), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1,3\}\), \(\{1,2\}\), \(\{2,3\}\) and \(\{1,2,3\}\), but we exclude the final three
of these.
On a sheet of paper a grid of \(n\) horizontal and \(n\) vertical straight lines is drawn. How many different closed \(2n\)-link broken lines can be drawn along the grid lines so that each broken line passes through all horizontal and all vertical straight lines? On the diagram below you can see an example of a closed broken line for \(n = 5\).
Find the largest number \(A\) such that for each permutation of the set \(\{1,2,3, \dots, 100\}\), the sum of some \(10\) consecutive terms of that permutation is at least equal to \(A\).
The set of symmetries of an object (e.g. a square) form an object called a group. We can formally define a group \(G\) as follows.
A is a non-empty set \(G\) with a binary operation \(*\) satisfying the following axioms (you can think of them as rules). A binary operation takes two elements of \(G\) and gives another element of \(G\).
Closure: For all \(g\) and \(h\) in \(G\), \(g*h\) is also in \(G\).
Identity: There is an element \(e\) of \(G\) such that \(e*g=g=g*e\) for all \(g\) in \(G\).
Associativity: For all \(g\), \(h\) and \(k\) in \(G\), \((g*h)*k=g*(h*k)\).
Inverses: For every \(g\) in \(G\), there exists a \(g^{-1}\) in \(G\) such that \(g*g^{-1}=e\).
Prove that the symmetries of the ‘reduce-reuse-recycle’ symbol form a group.
All of the rectangles in the figure below, which is drawn to scale, are similar to the big rectangle (that is, their sides are in the same ratio). Each number represents the area of the rectangle. What is the length \(AB\)?
For any positive integer \(k\), the factorial \(k!\) is defined as a product of all integers between 1 and \(k\) inclusive: \(k! = k \times (k-1) \times ... \times 1\). What’s the remainder when \(2025!+2024!+2023!+...+3!+2!+1!\) is divided by \(8\)?
Let \(u\) and \(v\) be two positive integers, with \(u>v\). Prove that a triangle with side lengths \(u^2-v^2\), \(2uv\) and \(u^2+v^2\) is right-angled.
We call a triple of natural numbers (also known as positive integers) \((a,b,c)\) satisfying \(a^2+b^2=c^2\) a Pythagorean triple. If, further, \(a\), \(b\) and \(c\) are relatively prime, then we say that \((a,b,c)\) is a primitive Pythagorean triple.
Show that every primitive Pythagorean triple can be written in the form \((u^2-v^2,2uv,u^2+v^2)\) for some coprime positive integers \(u>v\).