P100 · Extremal configurations · Classic

Rectangle-free binary matrices

VERIFIED CONSTRUCTION21 ones
n = 7Current record · open

Place as many ones as possible in an n × n grid. No two rows and two columns may meet at four ones.

Formal definition

  • GridFill each cell of an n-row, n-column grid with zero or one.
  • RectangleChoose any two distinct rows and any two distinct columns. At most three of the four corners may contain ones, regardless of the entries inside.
  • ConstructionSupply the entire matrix, including any all-zero rows or columns.
  • ObjectiveScore one point for each one. Maximize the total.

Getting a feel for it

How often can a column pair occur?

Three ones in one row use three pairs of columns. If another row uses even one of those pairs, the four ones form a rectangle.

ONE LEADERBOARD PER n

Current best solutions by n

Each parameter n is an independently scored sub-problem. Select any card to inspect the current record construction or submit a stronger solution.

Discussion (0) ↓
n2
CURRENT RECORD3
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n3
CURRENT RECORD6
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n4
CURRENT RECORD9
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n5
CURRENT RECORD12
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n6
CURRENT RECORD16
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n7
CURRENT RECORD21
Optimal
Answer sourcePG(2, 2)
Solution methodPublished reference construction
n8
CURRENT RECORD24
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n9
CURRENT RECORD29
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n10
CURRENT RECORD34
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n11
CURRENT RECORD39
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n12
CURRENT RECORD45
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n13
CURRENT RECORD52
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n14
CURRENT RECORD56
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n15
CURRENT RECORD61
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n16
CURRENT RECORD67
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n17
CURRENT RECORD74
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n18
CURRENT RECORD81
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n19
CURRENT RECORD88
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n20
CURRENT RECORD96
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n21
CURRENT RECORD105
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n22
CURRENT RECORD108
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n23
CURRENT RECORD115
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n24
CURRENT RECORD122
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n25
CURRENT RECORD130
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n26
CURRENT RECORD138
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n27
CURRENT RECORD147
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n28
CURRENT RECORD156
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n29
CURRENT RECORD165
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n30
CURRENT RECORD175
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n31
CURRENT RECORD186
Optimal
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n32
CURRENT RECORD189best known 189
Matches the best known
Answer sourceNarjess Afzaly & Brendan McKay
Solution methodPublished reference construction
n43
CURRENT RECORD290best known 290
Matches the best known
Answer sourceuser48028 (MathOverflow)
Solution methodPublished reference construction

Data and citation

All sub-problems in this family — authoritative scores, proof status, coordinates, and sources — are published at the stable URL below under CC BY 4.0. Because scores update as records fall, please cite the file's generatedAt timestamp.

GET https://minmaxarena.com/data/rectangle-free-matrices.json

Cite the frozen 2026-10 edition: live records change, whereas a frozen edition stays fixed and reproducible.

GET https://minmaxarena.com/data/editions/2026-10/rectangle-free-matrices.json
BibTeX (click to copy)
@misc{minmaxarena-rectangle-free-matrices-2026-10,
  title  = {{Rectangle-free binary matrices} (P100)},
  author = {{MinMax Arena}},
  year   = {2026},
  note   = {Machine-verified records, 2026-10 edition},
  url    = {https://minmaxarena.com/data/editions/2026-10/rectangle-free-matrices.json},
  license = {CC BY 4.0}
}
DISCUSSION

Discussion

Discuss strategies, share construction methods, or ask questions. Any signed-in user can post under their public byline and unique #UID. New posts appear after moderation.

No threads yet. Start the first discussion.