Puzzles, Problems, etc.

Through the years, I’ve encountered many intriguing math puzzles and interesting math problems (some not closely related to the research fields I work in). 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 favorites 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!

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.

Date: September 29, 2024

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.

Date: September 29, 2024

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

Date: September 29, 2024

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\)?

Date: September 29, 2024

Source: I heard this from Nicolas Boumal, who I believe heard it from Alex Townsend.

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.

Date: September 29, 2024

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?

Date: September 29, 2024

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\)?

Date: September 29, 2024

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?

Date: September 29, 2024

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 enonugh to just consider the case \(n=2\).]

Date: October 1, 2024

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?

Date: October 27, 2024

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.

Date: October 27, 2024

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.

Date: October 27, 2024

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?

Date: October 27, 2024

Source: I heard about this problem from Daniel Kressner.

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

Date: October 27, 2024

Source: This video.