IMO Series (2023)

by Erik Demaine and Martin Demaine

This piece was prepared for the International Mathematical Olympiad (IMO) 2023. It features multiple levels of mathematical puzzles (see the unfolded sheets and mathematical problems below). At one level, its surface describes 11 solved mathematical problems (P1–P11) and 3 unsolved problems (U1–U3), all around a central mathematical theme of dissections. At another level, these problems are written in two different mathematical fonts also about dissection: the solved problems are written in our Tetris font and the unsolved problems are written in our 2-piece disconnected dissection font. Thus each letter of each problem is itself a puzzle: for each letter of the Tetris font, the goal is dissect the shape into exactly the seven Tetris pieces (one-sided tetrominoes); while for each letter of the dissection font, the goal is to dissect the shape into two sets of pixels that can be re-arranged (translated/rotated/reflected) into a square. These 52 font puzzles are featured on the other side of the unfolded sheet (and the base underneath the sculpture). Each mathematical problem is also written within the shape of a tetromino (Tetris piece), and the problems themselves form an interesting tetromino packing (considered in Problem P3).

Video

Watch a 7-minute video about the making of this piece, thanks to Jane Street!

Sculpture

[0691] “Solve Me” (2023), Mi-Teintes paper, 11" × 14" × 15" high:

Unfolded Sheet

One side of the unfolded sheet features 52 font puzzles. For each of the 26 letters of the Tetris font at the top, dissect each letter into exactly the seven Tetris pieces. For each of the 26 letters of the 2-piece disconnected dissection font, dissect the shape into two sets of not necessarily connected pixels that form a square (by translation and/or rotation and/or reflection).

The other side of the unfolded sheet features 11 solved problems (P1–P11, written in the Tetris font) and 3 unsolved problems (U1–U3, written in the 2-piece disconnected dissection font). These mathematical problems are detailed below.

Mathematical Problems

Here is the text of the mathematical problems, along with related hints and/or references:

P = puzzle / problem
U = unsolved / unknown

P1 Give an efficient algorithm to tile a given polyomino by 2x2 squares if possible

Hint
Consider the topmost leftmost pixel of the polyomino.

P2 Pack 2 complete sets of the 7 Tetris pieces into a 7x8 rectangle

Solution

AAEEJJJ
AAEIIMJ
BBEFIMM
BBFFIMN
CDFGKNN
CDGGKKN
CDGHHKL
CDHHLLL

P3 Show 2 complete sets of the 7 Tetris pieces cannot pack into [O]

Hidden joke
The arrangement of problems as Tetris pieces would appear to be such a packing.
Explanation
The arrangement of problems as Tetris pieces uses 3 Ls and 1 J, instead of 2 Ls and 2 Js as required by P3.

P4 Prove that a tiling of a square by rectangles with no separating line has 1 piece strictly inside the square

Definition of tiling
“Tiling” means “exact packing”: both completely covering the square and not leaving any gaps between pieces.
Definition of separating line
The top figure defines “separating line”: a line all the way through the tiling that doesn't intersect the interior of any pieces.
Definition of strictly inside
The bottom figure defines “strictly inside”: the piece does not touch the boundary of the square.
Problem origin
This problem was a shortlisted problem from IMO 2007 (Problem C2).

P5 Which tilings by Tetris pieces can be ordered so each piece is supported by a prior pixel or the floor?

Hint
Use a partial order to characterize which pieces must be placed before which other pieces.

P6 Prove NP-hardness of tiling a given polyomino with any trominoes

Problem clarification
You can use arbitrarily many of each type of tromino.
Problem origin
2017 paper by Horiyama, Ito, Nakatsuka, Suzuki, and Uehara

U1 What is the complexity of tiling a given polyomino with any tetrominoes?

Motivation
This is a natural extension of P6.

P7 Cut the surface of a cube into 2 pieces that each fold into a unit cube? 4 pieces? 5 or 8 or 9 or 10 pieces?

Problem origin
See our initial rep-cube paper and the follow-up paper.

P8 Prove 2 equal-area rectangles have a common dissection into finitely many polygons

Solution
See this figure and description.
Problem origin
Originally proved by Montucla in 1778; see G. Frederickson, Dissections: Plane & Fancy, Cambridge University Press, 1997, p. 222.

P9 Assuming P8, prove 2 equal-area polygons have a common dissection into finitely many polygons

Proof sketch
Triangulate each polygon, cut each triangle into three pieces and re-arrange into a rectangle, apply P8 to make all rectangles have the same small height. Thus we can convert both polygons into a thin rectangle; overlay the two dissections.

P10 Prove some 2 equal-area polygons have no k-piece common dissection, for any k

Solution construction
1 × 1 square versus 2k × 1/2k rectangle.
Proof sketch
Pieces have diameter at most √2, but need to reach across 2k.

U2 Do a square and a regular triangle have a 2-piece or 3-piece common dissection?

Problem clarification
“Regular triangle” means “equilateral triangle”
Figure description
The figure shows the best known (4-piece) common dissection.

P11 Prove NP-hardness of finding a k-piece common dissection of 2 given polygons? In the strong sense?

Problem origin
Our paper about dissection with the fewest pieces.

U3 Does any algorithm decide whether 2 given polygons have a 2-piece common dissection? k-piece?

Other Curved Crease Sculpture by Demaine & Demaine