Polyominoes on Chessboards - Numberphile

Key Concepts

• Polyominoes: Shapes formed by joining n squares edge-to-edge.
• Monimino (1-omino): A single square.
• Domino (2-omino): Two squares joined.
• Tromino (3-omino): Three squares joined (straight or L-shaped).
• Tetromino (4-omino): Four squares joined (Tetris pieces).
• Pentomino (5-omino): Five squares joined.
• Chessboard Coloring Argument: A proof technique using alternating colors to demonstrate impossibility of tiling.
• Tiling: Covering a surface with shapes without overlap or gaps.
• Grid: A network of horizontal and vertical lines forming squares.
• Rotation: Turning a shape by 90, 180, or 270 degrees.

Polyomino Tiling Problems

This video explores the possibility of tiling specific grids with polyominoes, focusing on smaller polyominoes and using coloring arguments as a primary proof method.

Domino Tiling of a Modified Chessboard

Problem: Can an 8x8 chessboard with two opposite corners removed be tiled by dominoes?

Key Points:

• A standard 8x8 chessboard has 64 squares. Removing two corners leaves 62 squares.
• Each domino covers exactly two squares.
• Coloring Argument:
  • A standard chessboard coloring has 32 white and 32 black squares.
  • The two removed corners are of the same color (e.g., both white).
  • This leaves an unequal number of squares of each color (e.g., 30 white and 32 black).
  • Every domino, regardless of placement, covers one white and one black square.
  • Therefore, to tile the remaining 62 squares, you would need 31 dominoes, which would cover 31 white and 31 black squares.
  • Since the number of white and black squares is unequal, tiling is impossible.

Conclusion: It is impossible to tile an 8x8 chessboard with two opposite corners removed using dominoes.

Variations:

• If two corners of different colors are removed, the remaining board has an equal number of white and black squares (31 each). In this case, tiling is possible.
• The video demonstrates that if one white and one black square are removed (even randomly), tiling is still possible. The proof involves drawing a path through all squares, which dominoes can follow.

Tromino Tiling of a Modified Chessboard

Problem: Can an 8x8 chessboard with one square removed be tiled by straight trominoes (three squares in a line)?

Key Points:

• An 8x8 chessboard has 64 squares. Removing one square leaves 63 squares.
• Each tromino covers three squares.
• Divisibility Argument: 63 is divisible by 3 (63 / 3 = 21), so the number of squares is compatible with tiling by trominoes.
• Three-Coloring Argument:
  • The grid is colored with three colors (e.g., green, pink, brown) in a repeating pattern.
  • A straight tromino, regardless of its orientation, will always cover exactly one square of each color.
  • For tiling to be possible, the number of squares of each color on the board must be equal (21 of each).
  • Analysis of an 8x8 grid with one corner removed: The video calculates the number of squares of each color. For a specific coloring pattern, it shows an unequal distribution (e.g., 22 green, 21 pink, 20 brown).
  • Since the counts are unequal, tiling is impossible if the removed square results in this imbalance.

Conclusion: Tiling an 8x8 chessboard with one square removed by straight trominoes is not always possible. It depends on the color distribution of the remaining squares.

Specific Case:

• If a corner square is removed, the color distribution is unequal, making tiling impossible.
• The video discusses the possibility of removing a square such that the remaining counts are equal. However, it highlights a fallacy: equal counts do not guarantee possibility.
• A crucial condition for possibility is that if a square is removed, any 90-degree rotation of that square must also result in a square of the same color. This is because if a rotated square has a different color, it could lead to an impossible tiling scenario.
• The video identifies a specific "green" square whose 90-degree rotations land on other "green" squares. Removing this square might make tiling possible.
• The video then demonstrates, by drawing, that tiling is possible when this specific green square is removed.

Note on L-shaped Trominoes: The video mentions that L-shaped trominoes have different constraints and are easier to tile with, but leaves this as an exercise for the viewer.

Tetromino Tiling of a 4x5 Grid

Problem: Can one copy of each of the five distinct tetrominoes (Tetris pieces) tile a 4x5 grid exactly once?

Key Points:

• There are five distinct tetrominoes.
• The total area of the five tetrominoes is 5 * 4 = 20 squares.
• A 4x5 grid has 20 squares, so the area is compatible.
• The grid must have a dimension of at least 4 to accommodate the straight tetromino.
• Two-Coloring Argument:
  • The 4x5 grid is colored with two alternating colors (pink and brown).
  • Four of the five tetrominoes always cover exactly two pink and two brown squares, regardless of orientation.
  • The "T-shaped" tetromino is the exception: it will always cover either three pink and one brown, or three brown and one pink square.
  • The 4x5 grid has an equal number of pink and brown squares (10 each).
  • If we use one of each tetromino, the four "balanced" tetrominoes will cover 4 * 2 = 8 pink and 8 brown squares.
  • The T-shaped tetromino must then cover the remaining 2 pink and 2 brown squares. However, it can only cover 3 of one color and 1 of the other.
  • This creates an imbalance in the total number of pink and brown squares covered.

Conclusion: It is impossible to tile a 4x5 grid with one copy of each of the five distinct tetrominoes.

Pentomino Tiling

Problem: Can all 12 distinct pentominoes tile a rectangular grid exactly once?

Key Points:

• There are 12 distinct pentominoes.
• The total area of the 12 pentominoes is 12 * 5 = 60 squares.
• The video states that the answer is "yes," and it is possible to tile a rectangular grid with them.
• The specific dimensions of the rectangle are not explicitly stated in this segment, but it's implied to be a solvable problem.
• The video does not provide the solution but confirms its existence.

Conclusion: It is possible to tile a rectangular grid with one copy of each of the 12 pentominoes.

Sponsor Segment: Jane Street

• Sponsor: Jane Street, a global quantitative trading firm.
• Opportunity: Internships at their Hong Kong office.
• Benefits: All expenses paid (flights, accommodation), salary.
• Requirements: Curious mind, passion for learning (machine learning, distributed systems, hardware, statistics), English proficiency, graduating in 2027 or later. No finance experience needed.
• Call to Action: Visit the Jane Street website for details.

Final Thoughts on Tetris Skill

• The video touches on the common perception of being good at Tetris.
• It suggests that true mastery of Tetris involves a level of speed and accuracy that often surprises people.