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, while a few are my own creations.

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

(1-10) Puzzles 1 - 10
  1. 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

  1. (*) 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

  1. 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

  1. 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.

  1. 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.

  1. 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).

  1. (*) 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.

  1. 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.

  1. (*) 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.

  1. 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.

(11-20) Puzzles 11 - 20
  1. (*) 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.

  1. (*) 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.

  1. 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.

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

Source: This video.

  1. 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.

  1. 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.

  1. (*) 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.

  1. (*) 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.

  1. (*) 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.

  1. 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.

(21-30) Puzzles 21 - 30
  1. 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.

  1. 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.

  1. Does there exist a triangle-free graph on \(n\) vertices with at least \((n^2-1)/4\) edges?
  1. 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.

  1. 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.

  1. 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.

  1. 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.

  1. 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.

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

Source: See for example MSE.

  1. 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.

(31-40) Puzzles 31 - 40
  1. (*) What is number of spanning trees in the complete graph on \(n\) vertices?

Source: See Kirchhoff’s matrix tree theorem.

  1. (*) 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.

  1. 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.

  1. Give an example of a solid body in 3D which has uniform density, and has only two equilibrium points when resting on a table — one stable and one unstable. (Example: A generic ellipsoid has six equilibrium points, two of which are stable. So an ellipsoid doesn’t count.)

Source: See wikipedia. Note that in this problem the shape may be nonconvex.

  1. Show that the squareroot of a positive integer is either an integer or irrational.
  1. Let \(G\) be a simple graph on \(n\) vertices, and let \(E\) be its number of edges. Prove the following:

  1. If \(G\) has no triangles, then \(E \leq \frac{n^2}{4}\). Is this bound tight?

  2. If \(G\) has no \(p+1\)-clique, then \(E \leq (1 - \frac{1}{p})\frac{n^2}{2}\). Is this bound tight?

  3. (*) If \(G\) has no 4-cycle, then \(E \leq n^{3/2}\).

  4. (*) If \(G\) has no even cycles, then \(E \leq \frac{3(n-1)}{2}\). Is this tight?

Source: Chapters 20, 28, 41 of Proofs from THE BOOK by Aigner and Ziegler, and this MSE post.

  1. Let \(G\) be a simple graph on \(n\) vertices, for which any two vertices have exactly one neighbor in common, aka, every two vertices are connected by exactly one path of length \(2\). Prove the following:

  1. (*) If no vertex of \(G\) is adjacent to all other vertices, then \(G\) is regular (i.e., all degrees are equal).

  2. (*) There is some vertex of \(G\) which is adjacent to all other vertices.

  3. (*) What are all possible graphs \(G\) can be?

Source: Chapter 44 of Proofs from THE BOOK by Aigner and Ziegler.

  1. Let \(G\) be a simple planar graph on \(n\) vertices. Prove the following:

  1. (*) \(G\) has at most \(3n-6\) edges.

  2. \(G\) has a vertex of degree at most \(5\).

  3. \(G\) is \(6\)-colorable.

Source: Chapter 13 of Proofs from THE BOOK by Aigner and Ziegler.

  1. Let \(m > 1\) be an integer.

  1. Let \(n = 2^m, m > 1\). Show that there exists an \(n \times n\) matrix \(A\) whose entries are \(1\) or \(-1\), and such that \(A^T A = A A^T = n I\) (i.e., \(A\) is orthogonal up to scaling).

  2. Let \(n = 2^m - 1\). Determine the maximum possible volume of a \(n\)-simplex that can be inscribed in the cube \([-1, 1]^n\). Does a maximal \(n\)-simplex have to be regular?

(An \(n\)-simplex is the convex hull of \(n+1\) vectors in \(\mathbb{R}^n\). It is called regular if all pairwise distances between its vertices are equal.)

Source: Part (a) comes from Chapter 7 of Proofs from THE BOOK by Aigner and Ziegler.

  1. Let \(n \geq 1\). A triangulation of the cube \([-1,1]^n\) is a subdivision of the cube into \(n\)-simplices whose interiors are pairwise disjoint.

  1. Show that there is a triangulation of the cube \([-1,1]^n\) requiring at most \(2^n n!\) simplices.

  2. Show that any triangulation of the cube \([-1,1]^n\) requires at least \(2^n n! / \sqrt{(n+1)^{n+1}} \gtrsim (\frac{\sqrt{n}}{e})^n\) simplices.

  1. Find a triangulation of the cube \([-1,1]^3\) such that (a) the triangulation uses only the vertices of the cube (no interior vertices are allowed), and (b) it consists of at most \(5\) tetrahedra (aka, \(3\)-simplices).

Source: See Exercise 3.3.2 of Nemirovski’s excellent set of lectures. For part (c), see this nice website. I suspect \(5\) is the best one can do, but have no proof.

(41-50) Puzzles 41 - 50
  1. Given a set \(K \subset \mathbb{R}^3\), we call the orthogonal projections of \(K\) onto the \(xy, yz, xz\)-planes the three shadows of \(K\). Similarly, if \(K \subset \mathbb{R}^2\), it has two shadows defined as orthogonal projections to the \(x, y\)-axes.
  1. What is the minimal possible area of a convex set \(K \subset \mathbb{R}^2\) whose two shadows are (closed) unit intervals?
  1. Find a convex set \(K \subset \mathbb{R}^3\) whose three shadows are unit squares, and whose volume is at most \(1/3\).
  1. Let \(K \subset \mathbb{R}^3\) be a convex set whose three shadows are unit squares (not necessarily aligned with the axes). Show that \(\text{vol}(K) > 0\) and \(\text{vol}(K) \leq 1\).

Comments: For (b), I suspect any such convex solid has volume at least \(1/3\), but have no proof. What happens if we allow \(K\) to be the union of two convex sets?

  1. The width of a convex compact set is the smallest distance between two parallel supporting hyperplanes of the set. For example, the width of a line segment is zero, and the width of the unit ball is \(2\).

Find an explicit constant \(C > 0\) such that: for all compact convex sets \(K \subset \mathbb{R}^3\), the width of \(K\) is at most \(C \cdot \text{volume}(K)^{1/3}\).

Comments: See wikipedia about Reuleaux triangles. If you can prove that \(C \sim 1.33638\) works, then you will resolve a famous conjecture about Meissner bodies — see this nice article by Kawohl and Weber, and wikipedia.

  1. Let \(\text{Herm}(n), n \geq 2,\) be the real vector space of \(n \times n\) complex Hermitian matrices. Endow \(\text{Herm}(n)\) with the standard inner product \(\langle A, B \rangle = \text{tr}(A B)\). We say that a basis \(\{A_1, A_2, ..., A_m\}, m = n^2,\) of \(\text{Herm}(n)\) is PSD if each \(A_i\) is nonzero and positive semidefinite. The condition number \(\kappa\) of the basis \(\{A_1, A_2, ..., A_m\}, m = n^2,\) is the ratio of the maximum and minimum eigenvalues of the \(m \times m\) Gram matrix with entries \(G_{ij} = \langle A_i, A_j \rangle = \text{tr}(A_i A_j)\): \(\kappa = \lambda_{\text{max}}(G) / \lambda_{\text{min}}(G)\).
  1. Show that a PSD basis of \(\text{Herm}(n)\) cannot be orthonormal (i.e., satisfies \(\langle A_i, A_j\rangle = 0\) for all \(i \neq j\)).
  1. Show that the condition number of any PSD basis of \(\text{Herm}(n)\) is at least \(n+1\).
  1. Show that there exists a PSD basis of \(\text{Herm}(n)\) with condition number at most \(2(n+1)\), for all \(n\) large enough.
  1. Assume that there exists a collection of “equiangular” complex unit vectors \(a_1, ..., a_m, m = n^2,\) which satisfy \(|\langle a_i, a_j \rangle|^2 = (n+1)^{-1}\). Show that there exists a PSD basis of \(\text{Herm}(n)\) with condition number exactly \(n+1\). (It is conjectured (but unproven) that such a collection \(a_1, ..., a_m\) always exists: see wikipedia)
  1. (*) Consider a rectangle in the plane which is tiled by smaller rectangles, all of whose axes are parallel to those of the big rectangle. Show that if all the rectangular tiles have one side of integer length, then so does the big rectangle.

Source: Chapter 29 of Proofs from THE BOOK by Aigner and Ziegler.

  1. (*) A cube is called integral if its sidelength is an integer. Prove that an integral cube cannot be partitioned into \(n > 1\) integral cubes, such that each of them has different side length.

Source: This is a classic, usually referred to as “cubing the cube.” For a solution see wikipedia.

  1. Let \(A\) be a matrix with integer entries. Show that if \(A x = 0\) has a positive real solution (i.e., \(x > 0\) entrywise), then \(A x = 0\) has a positive integer solution.

Source: Chapter 10 of Proofs from THE BOOK by Aigner and Ziegler.

  1. Assume all the roots of the real polynomial \(p(x) = x^n + a_{n-1} x^{n-1} +...+ a_0\) are real, and \(n \geq 2\). Show that all the roots of \(p\) are contained in the interval \([-2C, 2C]\) where \(C = \max\{|a_{n-1}|, |a_{n-2}|\}\).

Source: Chapter 20 of Proofs from THE BOOK by Aigner and Ziegler.

  1. Consider a museum whose floor plan is a connected polygon in the plane with \(n\) walls (for example, a rectangular museum has \(n = 4\)). The polygon does not intersect itself, and has no holes. You may place \(m\) guards inside the museum; each guard is stationary but has a \(360^\circ\) field of view. How many guards are needed to surveil the entire museum, i.e., so that every point of the museum is in the field of view of at least one guard? (For a rectangular museum, only one guard is needed.)

  1. Show that there exist polygonal museums with \(n\) walls that require at least \(\left\lfloor \frac{n}{3} \right\rfloor\) guards.

  2. (*) Show that \(\left\lfloor \frac{n}{3} \right\rfloor\) guards always suffice for any polygonal museum with \(n\) walls.

Source: Chapter 40 of Proofs from THE BOOK by Aigner and Ziegler.

  1. You are given a list of \(n\) natural numbers which are each at most \(m\). You know that each element in the list appears an even number of times, except one element appears an odd number of times. Find the element which appears the odd number of times, in time \(O(n)\) and space \(O(\log(m))\).

Source: I heard this from a friend.

  1. (*) Let \(A\) be a \(n \times n\) real matrix with positive entries. Show that \(A\) has a positive eigenvalue, with a corresponding positive eigenvector.
Source: See the Perron-Frobenius theorem.
[hint/spoiler] There are slick proofs based on the Brouwer fixed-point theorem.
(51-60) Puzzles 51 - 60
  1. (*) Is there a continuous open surjective map from the 2-sphere \(S^2\) to the 2-torus \(S^1 \times S^1\)? (An open map is a map which sends open sets to open sets.)

Source: See this question I asked on MSE.

  1. Is there a surjective real-analytic map from the 2-sphere \(S^2\) to the 2-torus \(S^1 \times S^1\)?

Source: See this question I asked on MSE.

  1. For every \(n \geq 1\), does there exist a surjective rational map from \(\mathbb{R}^n\) to the \(n\)-sphere \(S^n\)? (By rational, I mean its entries are quotients of polynomials.)

Source: See this question I asked on MSE.

  1. Write \(24\) in terms of \(1, 3, 4, 6\) using only multiplication, division, addition, subtraction (no powers or concatenation). You must use each \(1, 3, 4, 6\) exactly once. How many such expressions for \(24\) are possible?

Source: I heard this from a friend, see for example Reddit.

  1. (*) A king will call prisoners into a room one at a time, each call he chooses uniformly at random with replacement from the same set of 100 prisoners. In the room there is a single switch that can be flipped between ON and OFF. Before the process begins, the prisoners may agree on any strategy; after it begins, they cannot communicate except by flipping the switch. On any visit, the prisoner may flip (or not flip) the switch, and may also declare that every prisoner has visited the room at least once. If a declaration is correct, all prisoners are freed. If a declaration is incorrect, they are all executed. (Multiple visits by the same prisoner are possible; visits continue until someone declares.)
  1. Suppose the switch is initially ON and everyone knows this. Is there a strategy that succeeds with probability \(1\)? If so, estimate the expected time (number of calls) until the correct declaration occurs (under your strategy).
  1. Now suppose the initial position of the switch is unknown to the prisoners. Is there a strategy which allows the prisoners to succeed with probability \(1\)?

Source: I heard this from a friend. This page and this page have some solutions. Quanquan Liu provides a nice write-up with variations on the problem.

  1. Let \(a\) and \(b\) be positive integers. You are given two empty buckets with volumes \(a\) and \(b\), and access to a tap supplying an unlimited amount of water. Which integer volumes \(c\) can you measure?

Source: I heard this from a friend.