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$ or $1$ and the rest of columns are empty. Prove that $m\le 2^k$.
Problem
Source: 2018 Vietnam Team Selection Test
Tags: combinatorics, rectangle
30.03.2018 14:19
Did I make any mistake? Part (a.) is fairly simple:
02.12.2022 00:19
Fairly easy for a Vietnam TST #2: (a) For row $1\leq n\leq 2^k$, fill row $n$ with the first $k$ digits (append $0$ to beginning as needed) of $n-1$ in binary. Clearly, every binary string starts with at least one of these, and removing any row $n$ is impossible as the binary string that starts with $n-1$ in binary and then has zeroes will not be formed. (b) Ignore empty columns (i.e. assume it is a $m\times k$ grid), as the remaining columns provide no value. Induct on $k$: Base Case. $k=1$. If we have 3 rows, either two of them are the same, impossible, or there is a blank, which makes the other two rows redundant. Induction Step. Look at the first column, and assume there are $x$ blanks, $y$ zeroes, and $z$ ones. WLOG $y\leq z$. If $x+y<2^{k-1}$, then $z=m-2^{k-1}$, so if $m>2^k$, we know $z>2^{k-1}$ so by applying the Induction Hypothesis we get a contradiction. Thus if $m>2^k$ we have $x+y,x+z\geq 2^k$. Apply the induction hypothesis to the rows with the first column blank or 0, we get $x+y-2^{k-1}$ rows to remove. Similarly, with blank or ones we get $x+z-2^{k-1}$ rows. If any of these rows starts with a one or zero, we know it's unnecessary and can remove it, a contradiction. Thus all of these are blanks. If there is a blank row that can be removed from both sets, it can be removed entirely, absurd. Thus, the blank rows must be split between these two sets. In particular, $x+y-2^{k-1}+x+z-2^{k-1}\leq x$ implying $m=x+y+z\leq 2^k$ as desired.
12.02.2023 13:47
naman12 wrote: Fairly easy for a Vietnam TST #2: (a) For row $1\leq n\leq 2^k$, fill row $n$ with the first $k$ digits (append $0$ to beginning as needed) of $n-1$ in binary. Clearly, every binary string starts with at least one of these, and removing any row $n$ is impossible as the binary string that starts with $n-1$ in binary and then has zeroes will not be formed. (b) Ignore empty columns (i.e. assume it is a $m\times k$ grid), as the remaining columns provide no value. Induct on $k$: Base Case. $k=1$. If we have 3 rows, either two of them are the same, impossible, or there is a blank, which makes the other two rows redundant. Induction Step. Look at the first column, and assume there are $x$ blanks, $y$ zeroes, and $z$ ones. WLOG $y\leq z$. If $x+y<2^{k-1}$, then $z=m-2^{k-1}$, so if $m>2^k$, we know $z>2^{k-1}$ so by applying the Induction Hypothesis we get a contradiction. Thus if $m>2^k$ we have $x+y,x+z\geq 2^k$. Apply the induction hypothesis to the rows with the first column blank or 0, we get $x+y-2^{k-1}$ rows to remove. Similarly, with blank or ones we get $x+z-2^{k-1}$ rows. If any of these rows starts with a one or zero, we know it's unnecessary and can remove it, a contradiction. Thus all of these are blanks. If there is a blank row that can be removed from both sets, it can be removed entirely, absurd. Thus, the blank rows must be split between these two sets. In particular, $x+y-2^{k-1}+x+z-2^{k-1}\leq x$ implying $m=x+y+z\leq 2^k$ as desired. When I see the title, I confused, did I make a fake solution?