benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / Divide an m-by-n rectangle into mn nonoverlapping 1-by-1 squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares S,T in the poly…

Problem

Answer published by the source. Consult the official source to check your work against its answer.

problem

Divide an mm-by-nn rectangle into mnm n nonoverlapping 1-by-1 squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares S,TS, T in the polyomino, either (1) SS and TT share an edge or (2) there exists a positive integer nn such that the polyomino contains unit squares S1,S2,S3,…,SnS_{1}, S_{2}, S_{3}, \ldots, S_{n} such that SS and S1S_{1} share an edge, SnS_{n} and TT share an edge, and for all positive integers k<n,Skk<n, S_{k} and Sk+1S_{k+1} share an edge. We say a polyomino of a given rectangle spans the rectangle if for each of the four edges of the rectangle the polyomino contains a square whose edge lies on it. What is the minimum number of unit squares a polyomino can have if it spans a 128-by343 rectangle?
Plain-text mathematical notation (without MathML)
Divide an m-by-n rectangle into mn nonoverlapping 1-by-1 squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares S,T in the polyomino, either (1) S and T share an edge or (2) there exists a positive integer n such that the polyomino contains unit squares S₁,S₂,S₃,…,S_(n) such that S and S₁ share an edge, S_(n) and T share an edge, and for all positive integers k<n,S_(k) and S_(k+1) share an edge. We say a polyomino of a given rectangle spans the rectangle if for each of the four edges of the rectangle the polyomino contains a square whose edge lies on it. What is the minimum number of unit squares a polyomino can have if it spans a 128-by343 rectangle?
Original LaTeX notation
Divide an $m$-by-$n$ rectangle into $m n$ nonoverlapping 1-by-1 squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares $S, T$ in the polyomino, either (1) $S$ and $T$ share an edge or (2) there exists a positive integer $n$ such that the polyomino contains unit squares $S_{1}, S_{2}, S_{3}, \ldots, S_{n}$ such that $S$ and $S_{1}$ share an edge, $S_{n}$ and $T$ share an edge, and for all positive integers $k<n, S_{k}$ and $S_{k+1}$ share an edge. We say a polyomino of a given rectangle spans the rectangle if for each of the four edges of the rectangle the polyomino contains a square whose edge lies on it. What is the minimum number of unit squares a polyomino can have if it spans a 128-by343 rectangle?

Discussion

Discussion

No discussion posts on this page yet. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

See answer Answer published by the source

Artifacts

Code, notes and reproducible work shared by participants. Files are served from a separate origin.

No artifacts on this page yet. Share reproducible code or notes in a contribution. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

Source and history

task_id
6501512e-a821-524f-a0c3-db93c3618b49
task_key
test--6501512e-a821-524f-a0c3-db93c3618b49
task_revision_id
1
config / split
/ test

Official source

initial import