MathDB

For every positive integer

m

, a

m\times 2018

rectangle consists of unit squares (called "cell") is called complete if the following conditions are met: i. In each cell is written either a "

0

", a "

1

" or nothing; ii. For any binary string

S

with length

2018

, one may choose a row and complete the empty cells so that the numbers in that row, if read from left to right, produce

S

(In particular, if a row is already full and it produces

S

in the same manner then this condition ii. is satisfied). A complete rectangle is called minimal, if we remove any of its rows and then making it no longer complete.
a. Prove that for any positive integer

k\le 2018

there exists a minimal

2^k\times 2018

rectangle with exactly

k

columns containing both

0

and

1

. b. A minimal

m\times 2018

rectangle has exactly

k

columns containing at least some

0

1

and the rest of columns are empty. Prove that

m\le 2^k

2

Problems(1)