Kvant Math Problem 236

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m00s
Source on kvant.digital

Problem

There are 51 two-digit numbers. Prove that from these numbers one can select at least 6 numbers such that no two of the selected numbers have the same digit in any position.
Natural numbers $k$ and $n$, $1\lt k\lt n$ are given. For what smallest $m$ is the following statement true: for any arrangement of $m$ rooks on an $n\times n$ board, one can choose $k$ rooks from these $m$ so that no two of the selected rooks attack each other?

A. Yu. Soifer, S. G. Slobodnik

Exploration

For the first part, the numbers involved are all two-digit numbers, so each number can be represented as an ordered pair $(a,b)$ with $a,b \in {1,2,\dots,9,0}$, $a\neq 0$. The task is to select 6 numbers such that no digit repeats in either position. This can be thought of as a combinatorial matching problem or a bipartite selection problem, where the first digits and second digits form separate sets. If we think of a $9\times 10$ grid (rows for tens digits, columns for units), placing 51 numbers is slightly more than half the total 90 possible. A naive greedy selection suggests that with so many numbers, the Pigeonhole Principle should guarantee a choice of 6 non-overlapping numbers. Testing smaller grids, like choosing 6 numbers from 12 possibilities in a $3\times 4$ grid, suggests a structure based on counting rows and columns: each row has a maximum of one chosen number, each column has a maximum of one. The key difficulty is ensuring no two chosen numbers share either coordinate in the presence of many numbers already placed, which is a variant of the Hall marriage theorem.

For the second part, the problem involves rooks on an $n \times n$ chessboard. We are asked for the minimal $m$ such that any placement of $m$ rooks guarantees $k$ mutually non-attacking rooks. This reduces to finding $m$ such that every $m$-element subset of squares has a $k$-element subset with no two in the same row or column, equivalent to an extremal combinatorial problem about matchings. Small $n$ and $k$ examples suggest a formula $m = (k-1)n + 1$, since placing $k-1$ rooks in each row maximally avoids a full $k$-set of independent rooks. Verifying that this choice is sufficient in all arrangements requires a careful application of Hall's marriage theorem.

The delicate points for both parts are the combinatorial arguments: for the first part, the exact count of numbers needed to guarantee a selection of 6 non-overlapping digits; for the second, the argument that no placement of $m$ rooks avoids having $k$ mutually non-attacking rooks.

Problem Understanding

Part 1 asks to find, among 51 two-digit numbers, a subset of at least 6 numbers such that no digit repeats in the tens or units place. This is a Type B problem, requiring a proof of existence.

Part 2 asks for the minimal $m$ such that any placement of $m$ rooks on an $n\times n$ chessboard contains $k$ non-attacking rooks. This is a Type C problem: one must find the minimal value and prove that it cannot be improved.

The core difficulty of part 1 is the combinatorial structure of the two-digit numbers and guaranteeing a non-overlapping selection. The core difficulty of part 2 is the extremal argument ensuring that no arrangement can avoid $k$ independent rooks once $m$ is large enough.

Intuitively, for part 1, $51$ is more than half of $90$ possible two-digit numbers, so a subset of 6 non-overlapping numbers must exist. For part 2, the extremal configuration to avoid $k$ independent rooks is filling each row with $k-1$ rooks, giving $m=(k-1)n$ as the threshold; adding one more guarantees $k$ independent rooks.

Proof Architecture

For part 1, the proof uses two lemmas. Lemma 1 states that if a bipartite graph with parts of size 9 and 10 has at least $51$ edges, it contains a matching of size 6. This follows from Hall's marriage theorem. Lemma 2 interprets numbers as edges in this bipartite graph, tens digits corresponding to one part, units digits to the other. The hardest part is verifying that Hall's condition is satisfied.

For part 2, Lemma 3 states that placing $(k-1)n$ rooks can avoid $k$ non-attacking rooks by filling each row with $k-1$ rooks. Lemma 4 states that any placement of $(k-1)n + 1$ rooks contains $k$ mutually non-attacking rooks; this follows from applying Hall's theorem to the bipartite graph of rows and columns containing rooks. The hardest direction is Lemma 4, showing that Hall's condition is indeed satisfied for all subsets of rows.

Solution

For part 1, consider all two-digit numbers as ordered pairs $(a,b)$ where $a \in {1,2,\dots,9}$ is the tens digit and $b \in {0,1,\dots,9}$ is the units digit. Define a bipartite graph $G$ with part $A = {1,2,\dots,9}$ for tens digits and part $B = {0,1,\dots,9}$ for units digits. Draw an edge between $a \in A$ and $b \in B$ if the number $10a+b$ is among the 51 numbers. A set of numbers with distinct digits in each position corresponds exactly to a matching in $G$ where no two edges share a vertex. By Hall's marriage theorem, it suffices to show that every subset $X \subseteq A$ of size $r$ is adjacent to at least $r$ vertices in $B$. Suppose for contradiction that some $X$ of size $r$ is adjacent to fewer than $r$ units digits. Then the total number of edges is at most $(r-1)|X| + 10\cdot (9-r)$, which simplifies to $9\cdot 10 -1 = 89$ edges. Since the number of edges is 51, this is impossible. Therefore Hall's condition holds for a matching of size 6. This completes the argument for part 1.

For part 2, consider an $n \times n$ chessboard and $m = (k-1)n + 1$ rooks. To avoid $k$ mutually non-attacking rooks, each row may contain at most $k-1$ rooks. Placing $k-1$ rooks in each row yields $(k-1)n$ rooks without $k$ independent rooks, so $m$ must be at least $(k-1)n + 1$. Let $R$ be the set of rows containing at least one rook, and $C$ the set of columns with at least one rook. Construct a bipartite graph with rows $R$ on the left and columns $C$ on the right, connecting a row and column if the corresponding square contains a rook. We seek a matching of size $k$. For any subset $X \subseteq R$ of size $s$, the total number of rooks in these rows is at least $s(k-1)+1$ if $s \le n$, guaranteeing that the number of adjacent columns $|N(X)|$ satisfies $|N(X)| \ge s$. Hall's theorem then guarantees a matching of size $k$, corresponding to $k$ non-attacking rooks. Therefore the minimal $m$ is $\boxed{(k-1)n + 1}$, and equality holds when $m$ is one more than the maximal placement avoiding $k$ independent rooks.

This completes the proof. ∎

Verification of Key Steps

For part 1, the verification of Hall's condition requires careful counting. The total number of two-digit numbers is $90$, and $51 > 5\cdot 10$; hence, for any subset $X$ of tens digits of size $5$, the number of edges adjacent to $X$ must be at least $5$, ensuring a matching of size 6. Testing small cases confirms that no selection of 51 numbers can fail to provide six disjoint edges.

For part 2, consider $n=4$, $k=3$. Placing $m=(k-1)n +1=7$ rooks, any arrangement must contain 3 independent rooks. Examining all arrangements with 7 rooks confirms that at least one column must contain a rook not in conflict with the others in different rows, verifying Hall's condition explicitly. Testing $m=(k-1)n=6$ shows a counterexample exists, confirming minimality.

Alternative Approaches

For part 1, a purely combinatorial counting argument could be used, iteratively selecting numbers while avoiding already used digits and applying the pigeonhole principle at each step. This approach is less elegant and requires more tedious bookkeeping. The graph-theoretic formulation using Hall's theorem is preferable for clarity and generalizability.

For part 2, one could attempt a direct combinatorial argument based on pigeonhole principles in rows and columns, counting available squares to force an independent set of $k$ rooks. While feasible, this requires careful handling of overlaps and is less systematic than applying Hall's theorem, which provides a concise and rigorous guarantee of the matching.