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

(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. Let \(S\) be a solid in 3D whose orthogonal projections on the \(xy\), \(xz\), \(yz\) planes are each unit squares (e.g., an axis-aligned unit cube is one such solid). How small can the volume of \(S\) be?

Source: See this excellent video by Ben Gobler.

  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 \(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).

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

(41-50) Puzzles 41 - 50
  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 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. 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.
  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)