P100 · Extremal configurations · Classic

Rectangle-free binary matrices · n = 27

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

Instancen = 27
ObjectiveMaximize number of ones

Record comparison

number of ones · Higher is better
RecordValue / intervalAuthor / holderSource
Proven optimum147Narjess Afzaly & Brendan McKayExtremal Graphs and Turan Numbers ↗
Site recordNo player record yet——

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.
Inspect in editor ↗

Layout shown: starter layout

VERIFIED CONSTRUCTION147 ones

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.

The current arrangement for Rectangle-free binary matrices n = 27
LAYOUT & HISTORY

Starter layout

Inspect the layout, solver notes and record history.

The optimum is proven; no further improvement is possibleSubmit a proof / idea ↓Share a proof or bound argument in the discussion board. Accepted contributions earn proof points.
ANSWER FORMAT

How to write your answer

Submit an array named rows containing n strings of length n, using only 0 and 1.

Starter answer

{
  "rows": [
    "110100000000100000010000001",
    "101000110000000000000100010",
    "011010000010000000100000000",
    "001101001000000000001000000",
    "100011000000010010000010000",
    "000110100001000100000000100",
    "010001010000001100000001000",
    "010000101100000001000010000",
    "000100010100010000100000000",
    "000001000111000000000100001",
    "000000011010100010000000100",
    "100000001001001000100000000",
    "001000000001110001000001000",
    "000010000100101000001000010",
    "000000100010011000010000000",
    "001000000100000110010000000",
    "100000000010000101001000000",
    "000100000000001011000100000",
    "000001000000000001110000110",
    "000000100000000010101001001",
    "000000010001000000011010000",
    "000000000000100100100110000",
    "000010001000000000010101000",
    "010000000000010000001100100",
    "000100000010000000000011010",
    "001000000000001000000010101",
    "000000001000010100000000011"
  ]
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer+

Instance parameters

{
  "n": 27
}

Starter answer

{
  "rows": [
    "110100000000100000010000001",
    "101000110000000000000100010",
    "011010000010000000100000000",
    "001101001000000000001000000",
    "100011000000010010000010000",
    "000110100001000100000000100",
    "010001010000001100000001000",
    "010000101100000001000010000",
    "000100010100010000100000000",
    "000001000111000000000100001",
    "000000011010100010000000100",
    "100000001001001000100000000",
    "001000000001110001000001000",
    "000010000100101000001000010",
    "000000100010011000010000000",
    "001000000100000110010000000",
    "100000000010000101001000000",
    "000100000000001011000100000",
    "000001000000000001110000110",
    "000000100000000010101001001",
    "000000010001000000011010000",
    "000000000000100100100110000",
    "000010001000000000010101000",
    "010000000000010000001100100",
    "000100000010000000000011010",
    "001000000000001000000010101",
    "000000001000010100000000011"
  ]
}

Submit an array named rows containing n strings of length n, using only 0 and 1. · Verifier v1.0.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.