P100 · Extremal configurations · Classic · Hard

Rectangle-free binary matrices · n = 43

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

Instancen = 43
ObjectiveMaximize number of ones

Record comparison

number of ones · Higher is better
RecordValue / intervalAuthor / holderSource
External best known290user480282015MathOverflow ↗
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.
Open full editor ↗

Layout shown: starter layout

VERIFIED CONSTRUCTION290 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 = 43
LAYOUT & HISTORY

Starter layout

Inspect the layout, solver notes and record history.

Challenge this record ↗Submit 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": [
    "0000000010000000010110000000000010011000000",
    "0000001010010000000000000010000001000001001",
    "1000000001000100000000001000010000000101000",
    "0100000101000000000000010100000000010000001",
    "0010000000000101100000000001000000010000000",
    "1000100110000000101000000000000000100000000",
    "1000011000000001000101010000000000000000000",
    "1001000000000000000010000111000100000000000",
    "0010100000000000000001000100000000001001000",
    "0000000000100000000010010000100000100001000",
    "1010000000001000010000000000101000000000001",
    "0000000001100000100000100010001000001000000",
    "1000000000010010000000100000000000010010000",
    "0000000010100011000000001100000000000000010",
    "0101010010000100000000100000100000000000000",
    "0000000100010001000000000000100100001100000",
    "0000000010000000000000010001001000000100100",
    "0000100000000001000010100000010000000000101",
    "0000000000000000100100000100110001000010000",
    "0000000000100100001100000000000100000000001",
    "0000001000000000000000000000011100110000010",
    "0001000000000000100001000000000010000100011",
    "0001000001000001010000000000000001100000000",
    "0000000000000000001001001010100000010000100",
    "0000010000000000000000001001000000101010001",
    "0000100000000100010000010010000000000010010",
    "0000000011001000000001000000000100000010000",
    "0000101001000010000000000001100010000000000",
    "0100000000000001001000000000001010000011000",
    "0011001100100000000000000000000000000010100",
    "0000000100000110000011000000001001000000000",
    "0100001000001000100010001000000000000000000",
    "0100000000110000010001000001010000000000000",
    "0000000000011100000000000100000010100000100",
    "0000000100001000000100100001000000000001010",
    "0001000000001010001000010000010000001000000",
    "0000110000101000000000000000000001010100000",
    "0110000000000010000100000010000000100100000",
    "0000010000000010110000000000000100000001100",
    "0010000000000000000000111000000111000000000",
    "1100000000000000000000000000000001001000110",
    "0000001000000000011000100100000000000100000",
    "0010010001010000001010000000000000000000010"
  ]
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer+

Instance parameters

{
  "n": 43
}

Starter answer

{
  "rows": [
    "0000000010000000010110000000000010011000000",
    "0000001010010000000000000010000001000001001",
    "1000000001000100000000001000010000000101000",
    "0100000101000000000000010100000000010000001",
    "0010000000000101100000000001000000010000000",
    "1000100110000000101000000000000000100000000",
    "1000011000000001000101010000000000000000000",
    "1001000000000000000010000111000100000000000",
    "0010100000000000000001000100000000001001000",
    "0000000000100000000010010000100000100001000",
    "1010000000001000010000000000101000000000001",
    "0000000001100000100000100010001000001000000",
    "1000000000010010000000100000000000010010000",
    "0000000010100011000000001100000000000000010",
    "0101010010000100000000100000100000000000000",
    "0000000100010001000000000000100100001100000",
    "0000000010000000000000010001001000000100100",
    "0000100000000001000010100000010000000000101",
    "0000000000000000100100000100110001000010000",
    "0000000000100100001100000000000100000000001",
    "0000001000000000000000000000011100110000010",
    "0001000000000000100001000000000010000100011",
    "0001000001000001010000000000000001100000000",
    "0000000000000000001001001010100000010000100",
    "0000010000000000000000001001000000101010001",
    "0000100000000100010000010010000000000010010",
    "0000000011001000000001000000000100000010000",
    "0000101001000010000000000001100010000000000",
    "0100000000000001001000000000001010000011000",
    "0011001100100000000000000000000000000010100",
    "0000000100000110000011000000001001000000000",
    "0100001000001000100010001000000000000000000",
    "0100000000110000010001000001010000000000000",
    "0000000000011100000000000100000010100000100",
    "0000000100001000000100100001000000000001010",
    "0001000000001010001000010000010000001000000",
    "0000110000101000000000000000000001010100000",
    "0110000000000010000100000010000000100100000",
    "0000010000000010110000000000000100000001100",
    "0010000000000000000000111000000111000000000",
    "1100000000000000000000000000000001001000110",
    "0000001000000000011000100100000000000100000",
    "0010010001010000001010000000000000000000010"
  ]
}

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.