MathDB

(212) 6

Part of 1989 Tournament Of Towns

Problems(1)

TOT 212 1989 Spring J6 3n + 1 stars in the cells of a 2n x 2n array

Source:

3/7/2021
(a) Prove that if 3n stars are placed in 3n3n cells of a 2n×2n2n \times 2n array, then it is possible to remove nn rows and nn columns in such away that all stars will be removed . (b) Prove that it is possible to place 3n+13n + 1 stars in the cells of a 2n×2n2n \times 2n array in such a way that after removing any nn rows and nn columns at least one star remains.
(K . P. Kohas, Leningrad)
combinatorics