Problems by archive

Let $\vee$ be a commutative and associative binary operation and $\neg$ a unary operation on a set, satisfying Robbins's equation $\neg (\neg (a\vee b)\vee \neg (a\vee \neg b))=a$ for all $a,b$. Prove that the structure is a Boolean algebra, or find a counterexample.

Prove that no packing of equal balls in three-dimensional space has average density greater than $\pi /\sqrt{18}\approx 0.7405$, the density of the familiar cannonball stacking (face-centered cubic packing).

Keller conjectured in 1930 that in every tiling of ${\mathbb{R}}^n$ by unit cubes, some two cubes share an entire $(n-1)$-dimensional face. For which dimensions $n$ is this true?

The numbers $8=2^3$ and $9=3^2$ are consecutive perfect powers. Prove that they are the only such pair, that is, the only solution of $x^a-y^b=1$ in integers $x,y,a,b>1$ is $3^2-2^3=1$.

A set of points in the plane is in general position if no three lie on a line. An empty hexagon in such a set is a convex hexagon whose vertices are points of the set and which contains no other point of the set. Find the smallest $N$ such that every $N$ points in general position contain an empty…

Prove that every closed (compact, without boundary) three-dimensional manifold in which every loop can be continuously shrunk to a point is homeomorphic to the three-dimensional sphere.

Two armies on opposite hills must attack a city at the same time to win, and an army attacking alone is destroyed. The generals can communicate only by messengers who cross a valley and may be captured. Is there a protocol with a finite number of messages that guarantees the generals always attack…

A Kakeya set (or Besicovitch set) in ${\mathbb{R}}^3$ is a set that contains a unit line segment in every direction. Such sets can have volume zero. Prove that every Kakeya set in ${\mathbb{R}}^3$ nevertheless has Hausdorff dimension 3.

$n$ generals must agree on whether to attack or retreat by exchanging oral (unsigned) messages, and up to $m$ of them are traitors who may send arbitrary messages. All loyal generals must reach the same decision, and if the commanding general is loyal they must follow the commander's order. For…

A rigid planar shape must be moved around a right-angled corner in a hallway of width 1. What is the largest possible area of such a shape? Gerver's sofa has area about 2.2195. Prove that no shape with larger area can make the turn.