MathDB
Number does not exceed (n + 1)(n^2 + n + 1) [ILL 1974]

Source:

January 2, 2011
linear algebramatrixgeometryrectanglepigeonhole principlecombinatorics unsolvedcombinatorics

Problem Statement

An (n2+n+1)×(n2+n+1)(n^2+n+1) \times (n^2+n+1) matrix of zeros and ones is given. If no four ones are vertices of a rectangle, prove that the number of ones does not exceed (n+1)(n2+n+1).(n + 1)(n^2 + n + 1).
Back to ProblemsView on AoPS