MathDB

43

Part of 1974 IMO Longlists

Problems(1)

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

Source:

1/2/2011
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).
linear algebramatrixgeometryrectanglepigeonhole principlecombinatorics unsolvedcombinatorics