# Are there any open mathematical puzzles?

Are there any (mathematical) puzzles that are still unresolved? I only mean questions that are accessible to and understandable by the complete layman and which have not been solved, despite serious efforts, by mathematicians (or laymen for that matter)?

My question does not ask for puzzles that have been shown to have either no solution or multiple solutions (or have been shown to be ambiguously formulated).

-
Game theory puzzle: Can white force a win in chess? –  vadim123 Oct 19 '13 at 21:37
–  Mitch Oct 19 '13 at 21:48
I think this might be of interest to you: youtu.be/JPhqhZvXlhQ –  Vincent Pfenninger Oct 19 '13 at 23:23
@VincentPfenninger Which also leads to the "incomplete layman". –  Felix Marin Oct 20 '13 at 17:43
See also mathoverflow.net/q/100265/12357 –  Joel Reyes Noche Oct 20 '13 at 23:49

The sofa problem.

From Wikipedia:

It asks for the rigid two-dimensional shape of largest area $A$ that can be maneuvered through an L-shaped planar region with legs of unit width. The area $A$ thus obtained is referred to as the sofa constant. The exact value of the sofa constant is an open problem.

Author of the picture: Claudio Rocchini, see this link

-
Very cute graphic there! –  user43208 Oct 19 '13 at 21:39
This seems extremely solvable. Is it a joke or a very fitting answer to an odd question? –  Captain Giraffe Oct 19 '13 at 22:01
@O.L. This is a link to the Gerver paper. Quickly scanning it, I think it conjectures that the solution proposed (Fig. 2 on p. 268) is uniquely maximal. –  Glen The Udderboat Oct 20 '13 at 11:07
"It would be really useful to know before you buy a piece of furniture whether it's actually going to fit up the stairs or around the corner." – From Dirk Gently's Holistic Detective Agency, Douglas Adams –  Pål GD Oct 20 '13 at 13:16
Ironically, the solution which "cuts corners" turns out to be optimal. –  Kaz Oct 20 '13 at 20:46

The Collatz conjecture seems to fit the bill.

Consider the function $f : \mathbb{N} \to \mathbb{N}$ (here $0 \not\in \mathbb{N}$) given by

$$f(n) = \begin{cases} \frac{n}{2} &\ \text{if}\ n\ \text{is even,}\\ &\\ 3n+1 &\ \text{if}\ n\ \text{is odd.} \end{cases}$$

The Collatz conjecture states that, for every $n \in \mathbb{N}$, there is $k \in \mathbb{N}$ such that $f^k(n) = 1$ where $f^k = \underbrace{f\circ f\circ \dots \circ f \circ f}_{k\ \text{times}}$. That is, for any positive integer, repeated application of the function $f$ will eventually lead to $1$.

Of course, this conjecture can be stated without the need to refer to the function $f$, but rather the rules of a game as follows.

1. Pick a positive integer.
2. If the number is even, divide it by two. If the number is odd, multiply by three and add one.
3. If the number from step 2 is $1$, stop. Otherwise, repeat step 2.

Does the game always finish, no matter what number we begin with?

-
What is the importance of this conjecture? –  Tyler Hilton Oct 20 '13 at 7:12
@TylerHilton: Its ultimate importance is probably unknown, much as the importance of Fermat's Last Theorem was unknown at the time of its writing (but later led to significant advances in number theory). To quote Erdos: "Mathematics is not yet ready for such problems." –  Blue Oct 20 '13 at 10:59
@tylerhilton: Ideally we'd like to understand the dynamics of functions $f : \mathbb{Z} \to \mathbb{Z}$ in general. This is the simplest example where we very much don't -- it's piecewise linear, for goodness's sake! –  Daniel McLaury Oct 20 '13 at 13:57
@TylerHilton Like a lot of mathematical stuff, it is important because it helps to fight mental obesity. –  Matemáticos Chibchas Oct 21 '13 at 0:14
@DanielMcLaury: I'm not sure which properties of functions $\Bbb Z\to\Bbb Z$ should cause them to be called piecewise-linear, but I'm pretty sure the function considered here (which depends on parity of the argument) does not qualify for that adjective. –  Marc van Leeuwen Oct 21 '13 at 9:00

Frankl's union-closed sets conjecture: if $\mathcal F$ is a nonempty finite collection of nonempty finite sets, and if $X\cup Y\in\mathcal F$ whenever $X,Y\in\mathcal F$, must there be an element which is in more than half the members of $\mathcal F$?

P.S. There is an equivalent form of the conjecture, where the family $\mathcal F$ is permitted to have $\emptyset$ as an element; in this case the condition $\mathcal F\ne\emptyset$ has to be strengthened to $\bigcup\mathcal F\ne\emptyset$, and the conclusion has to be weakened to an element which is in at least half the members of $\mathcal F$.

-
Thats crazy that this is open. –  Abdulh Khazzak Gustav ElFakiri Oct 20 '13 at 17:26
@AJMansfield You don't think the fact that it's been open for 30 years rules out a "fairly obvious solution"? –  Pål GD Oct 20 '13 at 21:56
@PålGD Even if not, I will at least learn some stuff as I attempt to solidify my solution! –  AJMansfield Oct 20 '13 at 21:58
@AJMansfield I have a wonderful proof of this conjecture, but the StackExchange comment length is too small for me to post it here ;-) –  F'x Oct 21 '13 at 19:02
@MichaelAlbanese I'm sure something along the lines of the following would be clear enough with a little dialogue (but someone else can word it more elegantly): "An online store has a variety of combo-deals. And for any two combos they have, they also offer a combo with all of those items together. Must it be the case that some item is in at least half of the combos? Mathematicians don't know." –  Mark S. Nov 1 '13 at 0:03

In the spirit of O.L.'s example, I believe that the moving needle problem is still open:

Given a smoothly embedded copy of $\mathbb{R}$ in $\mathbb{R}^3$ containing $\{ (x,0,0) \ | \ x \in (-\infty,-C] \cup [C, \infty) \}$, is it always possible to continuously slide a unit length needle lying on the ray $(-\infty, -C]$ to the ray $[C, \infty)$, while keeping the head and tail of the needle on the curve throughout the process?

-
Is there a specific reason why we're embedding $\mathbb R$ is three dimensional space, rather than n-dimensional space for $n>1$? –  Karl Kronenfeld Oct 19 '13 at 23:05
@KarlKronenfeld I guess not. It just makes the problem easier to visualize. When I heard it stated the first time, it was stated for $\mathbf R^2$. –  Bruno Joyal Oct 19 '13 at 23:08
Ok, thank you. I thought maybe it was easier in some dimensions than others. –  Karl Kronenfeld Oct 19 '13 at 23:09
@KarlKronenfeld You're welcome. Maybe it is. Well, for $n=1$ it is certainly quite obvious. :) –  Bruno Joyal Oct 19 '13 at 23:12
Anybody volunteering to make an animated picture of this? It seems that Claudio Rocchini, the maker of the picture in O.L.'s answer, doesn't do requests: "You need a mathematical image? Dont' ask to me! I'm Too Busy." –  Glen The Udderboat Oct 20 '13 at 10:31

In his comment, user Vincent Pfenninger referred to a YouTube video that, amongst other fascinating, layman accessible puzzles, discusses packing squares problems proposed by Paul Erdős. I thought I'd include it among the answers (as a community wiki).

How big a square do you need to hold eleven little squares?

We don't even know if this is the best possible [solution.]

Which, to me, comes as a complete surprise. :)

Here is the link to Erich's Packing Center provided in grey below the picture. It contains lots of proposed solutions to packing problems like this one.

-
I'm never surprised anymore when a packing problem is open and hard. –  user7530 Oct 22 '13 at 1:11
This might be a naive question, but... how do we know there is a best possible solution? –  Bruno Joyal Nov 26 '13 at 17:00
@BrunoJoyal I turned your question into a question: math.stackexchange.com/q/582263/56801 :) –  Glen The Udderboat Nov 26 '13 at 18:37

The lonely runner conjecture is particularly simple; If $k$ runners race around a circular track of length $1$ - all beginning from the same point - at pairwise distinct and constant speeds, then for every runner there will be a time when that runner is a distance of at least $1/k$ from every other runner a.k.a lonely.

The result is known for $k \leq 7$, but a general solution has yet to be discovered.

Image by Claudio Rocchini.

-

Existence of odd perfect numbers. (Numbers which are the sum of their own proper divisors). This one has withstood over 2000 years of effort.

-

The twin prime conjecture: there are infinitely many pairs of primes which are a distance $2$ from each other (like 11 and 13).

-
The possibility that $p_{n+1}-p_n \to \infty$ for $n\to\infty$ where $p_n$ is the $n$th prime was not ruled out until Yitang Zhang's result this year (2013). –  Jeppe Stig Nielsen Oct 20 '13 at 17:46
@JeppeStigNielsen Indeed! This week, Zhang was awarded the Cole prize for this work. –  Bruno Joyal Oct 20 '13 at 17:52

The Inscribed Square Problem seems to fit the bill.

Draw a non-intersecting loop. Is it possible to find four points on the loop which are the corners of a square?

More precisely, by a non-intersecting loop I mean a Jordan curve.

-
The distinction between the cases that have been resolved and the general case is probably not very accessible to a layman. –  Mike Hall Oct 20 '13 at 22:49
@MikeHall: Could you elaborate? –  Michael Albanese Oct 20 '13 at 22:51
Does the square have to be contained within the loop in order to satisfy the problem? –  KeithS Oct 21 '13 at 19:34
I think that Michael refers to the fact that problem is solved for curves which can be drawn by hand.. How would you explain to a layman what a non-piecewise smooth curve is? –  N. S. Oct 23 '13 at 4:57
A curve with cusps is piecewise smooth. –  N. S. Oct 23 '13 at 13:46

What is a winning first move in the game of Chomp? (The game is known to be a win for the first player, but only by a nonconstructive "strategy-stealing" argument.)

-
My guess is there are lots of solved puzzles solved by nonconstructive arguments only. Am I right? (I'm a layman myself, so be gentle.) –  Glen The Udderboat Oct 19 '13 at 22:12
Let's see. (1) Strategy-stealing arguments in combinatorial game theory; Chomp is one example, there are a bunch of others. (2) The probabilistic method famously used by Paul Erdős to prove the lower bound $R(n,n)\gt2^{n/2}$ for the Ramsey number $R(n,n)$. (3) Paradoxical decompositions using the axiom of choice, like the Banach-Tarski theorem: a unit ball can be cut into 5 pieces which can be reassembled into 2 unit balls. –  bof Oct 19 '13 at 22:39
Worth noting that for (1) and (2), these aren’t non-constructive in the formal sense of intuitionistic logic. For (1), for instance, since it’s a finite game on a finite set, the strategy-stealing argument translates into an explicit, constructively definable strategy: simply enumerate the game tree, enumerate all possible strategies, … –  Peter LeFanu Lumsdaine Oct 21 '13 at 14:28

Can we cover a unit square with $\dfrac1k \times \dfrac1{k+1}$ rectangles, where $k \in \mathbb{N}$?

Note that the areas sum to $1$ since $\displaystyle \sum_{k \in \mathbb{N}}\dfrac1{k(k+1)} = 1$.

Here is an MO thread discussing some of the progress on this problem.

-

Does there exist a rectangular cuboid such that the width, height, breadth, length of all the diagonals, i.e., the diagonals on each face, and the body diagonal, are all integers?

-
What is a cuboid here? The Wikipedia article says there are non-equivalent definitions in use. –  Daniel McLaury Oct 20 '13 at 14:10
@DanielMcLaury I do not understand your question. Essentially, the question is whether there exists $a,b,c \in \mathbb{Z}$ such that $\sqrt{a^2 + b^2} \in \mathbb{Z}$, $\sqrt{b^2 + c^2} \in \mathbb{Z}$, $\sqrt{c^2 + a^2} \in \mathbb{Z}$ and $\sqrt{a^2 + b^2 + c^2} \in \mathbb{Z}$. en.wikipedia.org/wiki/Euler_brick#Perfect_cuboid –  user17762 Oct 20 '13 at 14:18
Okay, so by "cuboid" you mean "rectangular parallelepiped." –  Daniel McLaury Oct 20 '13 at 16:17
@DanielMcLaury I am curious to know what you interpreted by "rectangular cuboid". –  user17762 Oct 20 '13 at 16:21
A related open problem is whether 4D Euler bricks exist. That is, if we drop the requirement that the space diagonal is integral, then can we find $4$ integers such that the square root of the sum of the squares of any two of them is always an integer? –  Jaycob Coleman Oct 22 '13 at 0:28

The einstein problem (in german meaning one stone). Also known as the monotile problem.

Is there a single tile in the plane which can tile the entire plane but can not tile the plane periodically?

Such a tiling with no requirement on the number of tiles is known as an aperiodic tiling and is associated with such famous images as the penrose tiling

and is closely related to the exciting new field of quasicrystals - crystalline structures which give rise to pure point Bragg diffraction patterns with rotational symmetries which are not possible in classical crystals (so not two, three, four, or six-fold symmetry).

The full statement of the monotile problem actually needs a few assumptions on what a tile is, and what it means for it to tile the plane, as certain versions of the problem have been solved. This is discussed in this paper by Socolar and Taylor. But some standard assumptions are that the tile is a connected subspace of the plane homeomorphic to the closed disk and with piecewise linear boundary, and that it can tile the plane if you can rotate and translate the tile in such a way that the union of a set of these transformations covers the plane, and the interior of any two transformed tiles have empty intersection.

For instance, if we allow for disconnected tiles, then the Socolar-Taylor tile is a monotile.

-
This link may provide some information: tilings.math.uni-bielefeld.de –  Eric Nov 26 '13 at 0:25

There are numerous unsolved problems in number theory.

-
+1 Thank you for turning what was initially a +10 comment into an answer. Much appreciated. –  Glen The Udderboat Oct 21 '13 at 20:16

Here are two more problems I'd like to mention.

• Does there exist an odd positive integer $n$ (in base 10) satisfying: $$\begin{array} & \text{i})\space n \gt 1 \\ \text{ii})\space n \space \text{is a square} \\ \text{iii})\space \text{The only digits of}\space n \space \text{are} \space 0 \space \text{and} \space 1. \\ \end{array}$$

I've been playing with this on and off for 10 years with no success! $\mathbf {Note}$: There are no such integers less than $10^{50}$.

• Find 3 integers $x$,$y$ and $z$ such that $x^3 + y^3 + z^3 = 33$.
-
Wrote a program to rip through the second one (though I'm sure I'm not the first). at least one of z, y, z is not in the range [-650, 650] but the range is still growing –  Cruncher Oct 24 '13 at 18:39
$x,y,z$ are positive? (you wrote integers) –  Elimination Jul 16 '14 at 16:31
@Elimination No, otherwise it would be a very easy problem. –  Yongyi Chen Feb 11 at 4:22

While this is not a puzzle per se, the (traditional) game of Reversi is still mathematically unsolved, as are other games that are partially solved. You can see a small list here.

-
The game has been solved for the first player, for all board sizes smaller than the 8x8 grid on which the game is traditionally played. You are right that 8x8 does remain unsolved. –  KeithS Oct 21 '13 at 19:37

Gilbreath's conjecture is an unsolved problem related to primes which is as accessible to the layman as the Goldbach conjecture and twin prime conjecture, if not more so. It says that if we write out the prime numbers in order

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...$

then take the absolute values of the differences (often called the absolute difference) between consecutive terms,

$1, 2, 2, 4, 2, 4, 2, 4, 6, 2, ...$

and now do the same to the resulting values, then to those values, and so on to infinity i.e.

$1, 0, 2, 2, 2, 2, 2, 2, 4, ...$

$1, 2, 0, 0, 0, 0, 0, 2, ...$

$1, 2, 0, 0, 0, 0, 2, ...$

$1, 2, 0, 0, 0, 2, ...$

$1, 2, 0, 0, 2, ...$

the first term is always $1$. A simple observation utilized by Andrew Odlyzko to verify the conjecture for the first $3.4 \times 10^{11}$ differences is that if a sequence begins with $1$ and continues with only $0$ and $2$ for the next $n$ terms, then the next $n$ iterated differences must also begin with $1$, since the absolute difference between any combination of $0$ and $2$ is also $0$ or $2$, and the absolute difference between $1$ and either $0$ or $2$ is necessarily equal to $1$. Kyle Sturgill-Simon gives a nice exposition of the problem written specifically for the layman here.

Precisely the same conjecture has been made for the practical numbers, which have other significant analogies with prime numbers as well (see link). For intuition's sake the practical numbers can be seen as complementary to the primes in the sense that, whereas a prime number has no prime factors less than itself, a practical number typically has many prime factors which are small in comparison with the number itself. As a consequence, small multiples of practical numbers are also practical. In particular, if $n$ is practical and $1\leq m\leq 2n$, then $nm$ is practical. They begin:

$1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, ...$

-

Wolfram's "New Kind of Science" book on cellular automata had a large accompanying list of open problems which must surely contain many suitable candidates (although note some of the questions are more in History of Mathematics territory). I'd be surprised if they've been all ticked off in the last decade.

Wolfram's opus also serves as some inspiration as to how simple systems with complex emergent behaviour can create an enormous - and accessible - fresh new landscape of problems ripe for exploration.

-
Your link the open problems appears to be broken. –  Jaycob Coleman Oct 22 '13 at 0:40
Ooops! Thanks, fixed. –  timday Oct 22 '13 at 7:25

A somewhat forgotten problem from Paul Erdős is proving his following conjecture:

Let $f(r)$ equal the maximum of the sum of the side lengths of $r$ squares inscribed in a unit square such that they have no interior points in common. Erdős conjectured: For any positive integer $k$, $$f(k^2+1)=k.$$

As far as I know, this is not proven.

-

Two envelopes problem

From wikpedia: The two envelopes problem, also known as the exchange paradox, is a brain teaser, puzzle, or paradox in logic, philosophy, probability, and recreational mathematics. It is of special interest in decision theory, and for the Bayesian interpretation of probability theory. Historically, it arose as a variant of the necktie paradox.

The problem:

You have two indistinguishable envelopes that each contain money. One contains twice as much as the other. You may pick one envelope and keep the money it contains. You pick at random, but before you open the envelope, you are offered the chance to take the other envelope instead.

It can be argued that it is to your advantage to swap envelopes by showing that your expected return on swapping exceeds the sum in your envelope. This leads to the paradoxical conclusion that it is beneficial to continue to swap envelopes indefinitely.

Example - Assume the amount in my selected envelope is \$20. If I happened to have selected the larger of the two envelopes, that would mean that the amount in my envelope is twice the amount in the other envelope. So in this case the amount in the other envelope would be \$10. However if I happened to have selected the smaller of the two envelopes, that would mean that the amount in the other envelope is twice the amount in my envelope. So in this second scenario the amount in the other envelope would be \$40. The probability of either of these scenarios is one half, since there is a 50% chance that I initially happened to select the larger envelope and a 50% chance that I initially happened to select the smaller envelope. The expected value calculation for how much money is in the other envelope would be the amount in the first scenario times the probability of the first scenario plus the amount in the second scenario times the probability of the second scenario, which is \$10 * 1/2 + \$40 * 1/2. The result of this calculation is that the expected value of money in the other envelope is \$25. Since this is greater than my selected envelope, it would appear to my advantage to always switch envelopes.

A large number of solutions have been proposed. The usual scenario is that one writer proposes a solution that solves the problem as stated, but then another writer discovers that altering the problem slightly revives the paradox. In this way, a family of closely related formulations of the problem have been created, which are discussed in the literature. No proposed solution is widely accepted as correct. Despite this it is common for authors to claim that the solution to the problem is easy, even elementary. However, when investigating these elementary solutions they often differ from one author to the next. In the last two decades, several new papers have been published every year.

-
I wouldn't consider this an open problem myself, it's more like a problem which is open to multiple resolutions, some of which have already been discovered. –  Manishearth Oct 20 '13 at 10:14
There is no probability distribution on a subset $A$ of the positive integers such a random variable $X$ can satisfy $\mathrm P(X=2n)=\mathrm P(X=n)$ for all $n\in A$. –  John Bentin Oct 20 '13 at 11:30