0

The question is as such: At least how many stars should be drawn in a $4\times4$ table such that after eliminating two arbitrary columns and two arbitrary rows at least one star will remain in the table

I know the answer is $7$ stars but i don’t know how to write down my reasoning.

I just need a place to start and any help would be greatly appreciated

Alessio K
  • 10,599
user464840
  • 1
  • 1

2 Answers2

1

To prove that something is the least value subject to some constraint, first prove that it indeed satisfies the constraint (in your case, show that after eliminating two arbitrary columns and two arbitrary rows at least one star will remain in the table if 7 stars are drawn); then prove that any smaller value does not (in your case, show that after eliminating two arbitrary columns and two arbitrary rows it is possible that no stars remain in the table if less than 7 stars are drawn). Can you take it from here?

Trebor
  • 4,575
0

Suppose you have $4$ stars, then putting the stars on a diagonal is an optimal solution (however, any composition such that the rank of a $4\times 4$ matrix is full would work). That is, $$ \left[\begin{array}{cccc} * & & & \\ & * & & \\ & & * & \\ & & & * \end{array} \right] $$ Now, if rows $R$ and columns $C$ are chosen and $R\cap C\neq \emptyset$, then there would be one star left in the matrix. For example, removing rows $1$ & $2$ and columns $2$ & $3$ would leave the star at $(4,4)$ location. However, if $R\cap C = \emptyset$, then all starts will be removed. For example, removing rows $1$ & $2$ and columns $3$ & $4$ would remove all the stars.

Suppose you remove rows $1$ & $2$, then you must have at least one star in the locations $(3,1)$, $(3,2)$, $(4,1)$, and $(4,2)$. In such a case, one can change a strategy and instead choose columns $1$ & $2$, then there must be at least one star in the location $(1,3)$, $(1,4)$, $(2,3)$, and $(2,4)$.

It can be generalized to the following: When two rows $i$ & $j$ are chosen, there should be a star in the location $(k,i)$, $(k,j)$, $(l,i)$, and $(l,j)$. When two columns $i$ & $j$ are chosen, there should be a star in the location $(i,k)$, $(i,l)$, $(j,k)$, and $(j,l)$. Since any two rows or any two columns can be chosen, we must have two extra stars to 'dodge' the row and column choices. This gives $4$ stars chosen in the beginning, $2$ additional stars, and $2$ extra 'dodgers'. So the minimum number of required stars is $8$, not $7$.

For instance, the following is a solution $$ \left[\begin{array}{cccc} * & & * & * \\ & * & & \\ * & & * & \\ * & & & * \end{array}\right] $$

unobservable_node
  • 511