Puzzles

Through the years, I’ve encountered many fun math puzzles. I wish I had kept track of them, so I could share them with others!

That’s why I’ve decided to start listing some of my them here. While I may not be the best at solving these kinds of puzzles (far from it), I always enjoy giving them a try, and hope you do too! Many of these puzzles I heard from friends and colleagues.

None of these problems are easy; the ones I think are particularly difficult I mark with a (*).

Six people are at a party. Show that there is a group of three people who are either all friends, or none of the three are friends.

Source: Chapter 8.3 of Introduction to Graph Theory, 2nd Edition, by Douglas B. West

(*) Consider a list \((a_1, a_2, \ldots, a_n)\) of \(n\) distinct real numbers. Show that there is a sublist \((a_{i_1}, a_{i_2}, \ldots, a_{i_m})\), \(i_1 < i_2 < \ldots < i_m\), of length at least \(m \geq \sqrt{n}\) which is either increasing or decreasing.

Source: Chapter 8.3 of Introduction to Graph Theory, 2nd Edition, by Douglas B. West

Fix \(p \in (0, 1]\). Let \(G\) be an Erdős–Rényi random graph on \(n\) vertices with edge probability \(p\). Let \(q(n,p)\) be the probability that \(G\) has diameter \(2\). Show that \(q(n,p) \to 1\) as \(n \to \infty\) (here, \(p\) is constant, independent of \(n\)).

Source: Chapter 8.5 of Introduction to Graph Theory, 2nd Edition, by Douglas B. West

Let \(A\) be a real \(n \times n\) matrix which is tridiagonal (not necessarily symmetric). How many matrix-vector products \(A x\) do you need to recover all of \(A\), exactly and certainly? What about if the nonzero entries of \(A\) are in \([0,1]\) with say \(\leq 8\) digits after \(0. \ldots\)?

Source: I heard this from Nicolas Boumal, who heard it from Yuji Nakatsukasa.

This questions concerns a simple efficient algorithm for finding a min cut of a graph (or multigraph).
1. Let \((S, T)\) be a min cut of a graph \(G\) on \(n\) vertices of size \(k\) (i.e., \(k\) edges cross the partition \((S, T)\)). Show that \(G\) contains at least \(\frac{k n}{2}\) edges.
2. Consider the (randomized) algorithm presented below. When the algorithm terminates, it determines a cut (all vertices packed into the first vertex, and the others packed into the second remaining vertex). Show that this cut is a min-cut with probability at least \(\frac{2}{n(n-1)}\).
```
Input: a multigraph G

while G has more than 2 vertices:
    Choose an edge {u, v} from G uniformly at random (over the edges)

    Contract {u, v}: i.e., u and v are replaced by a single vertex, and any edge going 
    to u or v now goes to the combined vertex.

    Update G to be the new multigraph after the contraction
```
3. Show that any graph \(G\) has at most \(n(n-1)/2\) distinct min cuts.

Source: Section 2.3.3.2 of Notes on Randomized Algorithms by James Aspnes. Aspnes attributes this simple efficient algorithm for finding a min-cut to David Karger.

There is some positive integer \(N\) unknown to you. You sample \(k\) positive integers uniformly from \(\{1, 2, \ldots, N\}\), without replacement. After observing these \(k\) positive integers, what is a good estimate of \(N\)? Specifically, what is the maximum-likelihood estimator for \(N\)? What is the minimum-variance unbiased estimated for \(N\)? Which (the MLE or MVUE) gives a more sensible answer?

Source: This is a famous problem known as the German tank problem. It is a good example that sometimes it is not always best to simply use the MLE (even though the MLE is consistent and efficient).

(*) You are presented with two envelopes, each containing a real number (the numbers are distinct). One of the envelopes is randomly opened (probability \(1/2\) each envelope) and its number is revealed to you. You are asked to predict which of the two numbers in the envelopes is bigger. Is there a strategy that allows you to predict correctly with probability greater than \(1/2\)?

Source: This is a famous problem originally due to Thomas Cover.

Let \(p(z) = a_0 + a_1 z + \ldots + a_n z^n\) be a complex-valued polynomial, and let \(p'\) be its derivative. Show that the roots of \(p'\) lie in the convex hull of the roots of \(p\). Does this statement also hold if \(p\) is not polynomial but holomorphic on the entire complex plane with a finite number of zeros?

Source: This is known as the Gauss-Lucas theorem. It is in some sense a 2D generalization of Rolle’s theorem. See also John Baez’s proof based on electrostatics.

(*) Let \(A \in \mathbb{C}^{n \times n}\) be a complex \(n \times n\) matrix. Show that \(\{x^* A x : x \in \mathbb{C}^n, x^* x = 1\} \subseteq \mathbb{C}\) is convex. [Hint: first show that it is enough to just consider the case \(n=2\).]

Source: This is known as the Toeplitz-Hausdorff theorem – Chandler Davis gives a remarkably simple proof. There are many other results of the same flavor as Toeplitz-Hausdorff – see for example Kostant’s convexity theorem, and its generalizations.

Choose \(n\) points uniformly at random on a circle. What is the probability that the convex hull of the points contains the center of the circle?

Source: This one is a classic, and there are many very clever solutions.

(*) You are given an infinite sequence of boxes \(b_1, b_2, \ldots\), each containing a real number. Moreover, that sequence of real numbers eventually ends in all zeros (but you don’t know when). You are allowed to open an infinite number of boxes (in finite time – you are very powerful!), but you can’t open all boxes. You then have to choose a single box and can make one (and only one) guess what number is in the box. Devise a strategy that guarantees you are correct with probability 99/100.

Source: Pierre Marion came up with this problem, based on a variant of this problem we heard from Quentin Rebjock.

(*) What is the largest dimension of a linear subspace of matrices of size \(n \times n\) such that all matrices in that subspace (except the zero matrix) are invertible? It matters whether you consider complex or real matrices.

Source: I heard about this problem from Daniel Kressner. Some cases of this problem are fairly easy; others are difficult.

Fix \(n \geq 2\). Find a sequence (if it exists) \(a_0, a_1, ..., a_{n-1}\) such that \(a_i\) equals the number of times digit \(i\) appears in the sequence (\(a_i\) is an integer between \(0\) and \(n-1\)). For which \(n\) does such a sequence exist? For which \(n\) is the solution unique?

Source: I heard about this problem from Daniel Kressner.

Which is bigger: \(2^{100!}\) or \((2^{100})!\)?

Source: This video.

Let \(C \subseteq \mathbb{R}^n\) be a closed convex cone, and \(A \colon \mathbb{R}^n \to \mathbb{R}^m\) be a linear map. Is \(A(C) = \{A(x) : x \in C\}\) necessarily closed? convex? What if \(C\) is the intersection of a finite number of closed halfspaces?

Source: Chapter 4 of Approximation Algorithms and Semidefinite Programming by Gärtner and Matousek.

Let \(M\) be a \(n \times n\) real symmetric matrix. For \(k \in [1,n]\), let \(M_k\) denote the top-left \(k \times k\) submatrix of \(M\). Show that \(M\) is positive definite if and only if \(\text{det}(M_k) > 0\) for all \(k \in [1,n]\).

Source: This is known as Sylvester’s criterion.

(*) Take \(n \geq 4\) non-parallel lines in the plane. Suppose the number of unique intersection points of the lines is \(k\). Assume at most \(n/2\) lines pass through each distinct intersection point. Show that \(k \geq n/2\) (i.e., there are at least \(n/2\) unique intersection points).

Source: I heard this problem from Guifré Sánchez.

(*) Let \(S\) be a unit square (with interior), i.e., sidelength equals one. We want to cover \(S\) with a triangle \(T\) in the “best” way possible. Therefore we ask: what is the minimal value of \[\textrm{Area}(T \setminus S) + \textrm{Area}(S \setminus T),\] where \(T\) ranges over all triangles (with interior)?

Source: Reddit.

(*) How many ways are there to create change for 10000 CHF using Swiss coins? (Swiss coins have denominations worth \(.05, .1, .2, .5, 1, 2, 5\) CHF.)

Source: See these notes of Andrew Neitsch. Also see this set of notes from MIT.

You are in a train which has \(n\) wagons, all indistinguishable. They each contain a light bulb and a switch. The light in each wagon can be on or off: the initial state of the \(n\) lights is unknown. The wagons are attached to form a cycle. You are allowed to travel back and forth between neighboring wagons (each hop costs you 10 seconds). You are allowed to flip the switches (for free). Determine \(n\) in time \(O(n \log n)\).

Source: I head this from a friend. See this blog post by Tim Black.

Show that the number of partitions of an integer \(n \geq 2\) is between \(2^{\left\lfloor \sqrt{n} \right\rfloor}\) and \(2^n\).

Source: See MSE.

Let \(G\) be an Erdős–Rényi random graph on \(n\) vertices with edge probability \(p\). What is the expectation and variance of the number of triangles appearing in \(G\)? What is the threhsold for the appearance of a triangle in an Erdős–Rényi random graph?

Source: CV and MSE.

Does there exist a triangle-free graph on \(n\) vertices with at least \((n^2-1)/4\) edges?

Consider \(5\) points on a sphere (in \(\mathbb{R}^3\)). Is there an open hemisphere containing at least 3 of the points? At least 4 of the points? What if the hemisphere is closed?

Source: MSE.

An even number of coins are lined up on a table. Each coin has a real value. Alice and Bob play in turns, picking up one of the coins at the extremes (first or last coin of the line). Alice goes first. When no coins are left, the player whose sum of coin values is largest wins. Who wins, and with what strategy? What strategy should Alice use to obtain the maximal amount of money possible?

Source: I heard this from a friend. See Quora, and these slides.

Alice and Bob find a barrel of wine, without a cover. Alice thinks the wine is slightly more than half the barrel, and Bob thinks the wine is slightly less than half the barrel. How can they tell who is correct, without using any tools or any other container? Assume the barrel is rotationally symmetric, and has a reflection symmetry across a halfway plane orthogonal to the axis of rotation.

Source: I heard this from a friend. See this.

Consider a circular necklace with \(p\) beads, where each bead is one of \(k\) possible colors. Assume \(p\) is prime. How many different necklaces can you make? Prove Fermat’s little theorem.

Source: MSE.

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

Source: 1972 IMO.

Prove that every fraction \(a/b\) has a repeating decimal expansion of period at most \(b\).

Source: See for example MSE.

Are there 1000 distinct points in the plane, not all on a single line, whose pairwise distances are all integer? (*) What if no 3 points are allowed to be collinear?

Source: This video by Ravi Boppana.

(*) What is number of spanning trees in the complete graph on \(n\) vertices?

Source: See Kirchhoff’s matrix tree theorem.

(*) Let \(T\) be a tree with \(n\) nodes. Give an algorithm to find the diameter of \(T\) in linear time (i.e., \(O(n)\)).

Source: See this blog post. See also this video by Polylog.

How many ways are there to paint the faces of a 3D cube using at most \(n\) colors? Two painted cubes are the same if one can be obtained from the other via rotation. What about a regular octahedron? (*) A regular dodecahedron?

Source: See Burnside’s lemma. For the symmetries of the cube, see Gower’s blog post on the orbit-stabilizer theorem.