Kvant Math Problem 939

The problem has two parts.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m46s
Source on kvant.digital

Problem

In the cells of a $10\times10$ table, the digits 0, 1, $\ldots$, …, 9 are written in some manner so that each digit occurs exactly 10 times.

  1. Is it possible to arrange them so that no more than 4 different digits appear in each row and each column?
  2. Prove that there exists a row or column in which at least 4 different digits appear.

L. D. Kurylandchik

City Tournament (Spring, 1985)

Exploration

The problem has two parts. The second asks for a lower bound: in every arrangement, some row or column must contain at least four different digits. The first asks whether one can arrange the digits so that no row and no column contains more than four different digits. Since part 2 gives a universal lower bound of four, part 1 is asking whether this bound is attainable.

Let $S_d$ be the set of cells containing digit $d$. Since each digit occurs exactly $10$ times, each $S_d$ has size $10$.

A natural way to measure how many different digits appear is to count incidences between digits and rows. For a digit $d$, let $r_d$ be the number of rows containing $d$, and $c_d$ the number of columns containing $d$. Since $S_d$ consists of $10$ cells, if it meets $r_d$ rows and $c_d$ columns, then

$$10=|S_d|\le r_d c_d.$$

Hence $r_d c_d\ge 10$.

Suppose every row and every column contains at most three different digits. Then

$$\sum_d r_d\le 30,\qquad \sum_d c_d\le 30,$$

because there are $10$ rows and each contributes at most $3$ digit-incidences. Applying AM-GM to each digit,

$$r_d+c_d\ge 2\sqrt{r_d c_d}\ge 2\sqrt{10}.$$

Summing gives

$$\sum_d(r_d+c_d)\ge 20\sqrt{10}>60,$$

contradicting

$$\sum_d(r_d+c_d)\le 60.$$

Therefore some row or column contains at least four digits. This proves part 2.

Now for part 1 we need an example achieving the bound $4$. The previous argument suggests looking for a highly symmetric arrangement where each digit occupies only a few rows and columns. Since $10=2\cdot5$, a digit can occupy exactly $2$ rows and $5$ columns, forming a $2\times5$ rectangle. Then $r_d c_d=10$ exactly.

Can ten such rectangles partition the $10\times10$ board? Pair the rows:

$$(1,2),\ (3,4),\ (5,6),\ (7,8),\ (9,10),$$

and pair the columns into two blocks of five:

$$A={1,\dots,5},\qquad B={6,\dots,10}.$$

For each row-pair and each column-block there is a $2\times5$ rectangle of size $10$. There are exactly $5\cdot2=10$ such rectangles, matching the ten digits. Assign one digit to each rectangle.

Then every row meets exactly the two rectangles corresponding to its row-pair, hence contains exactly two digits. Every column meets one rectangle from each row-pair, hence contains exactly five digits. Thus rows have at most four digits and columns have at most four? No, columns have five digits, so this does not work.

We need a better construction.

Try cyclic intervals of four digits. Let row $i$ contain only digits

$$i,\ i+1,\ i+2,\ i+3 \pmod{10}.$$

If each digit appears in exactly four consecutive rows, then total row incidences are $40$, averaging four per row. Symmetrically arrange columns the same way. This suggests a $10\times10$ Latin-type construction.

Consider the table with entry

$$a_{ij}\equiv i+j \pmod{10}.$$

Each digit appears exactly $10$ times. Every row and every column contains all ten digits, so this is far from optimal.

To reduce the number of digits per row, group columns into blocks. Let columns $1,2,3$ carry one digit, columns $4,5$ another, columns $6,7,8$ a third, columns $9,10$ a fourth. Shift the pattern cyclically from row to row. Then each row contains four digits. Because of the cyclic shifts, each digit occurs equally often. We should check columns.

A cleaner construction is obtained from the circulant matrix

$$a_{ij}\equiv \left\lfloor \frac{i+j}{3}\right\rfloor \pmod{10}.$$

Each row contains at most four digits because as $j$ runs through ten values, the quotient changes only three times. The same holds for columns. Since adding $1$ to $i+j$ cyclically permutes digits, each digit occurs exactly ten times. This looks promising.

The crucial point is to verify rigorously that every digit occurs exactly ten times and every row and column contains at most four digits.

Problem Understanding

We must determine whether a $10\times10$ table can be filled with the digits $0,1,\dots,9$, each appearing exactly ten times, so that every row and every column contains at most four distinct digits. We must also prove that in every such filling there exists a row or a column containing at least four distinct digits.

This is Type B for the second statement and an existence question for the first. Together they amount to showing that the optimal universal bound is exactly four.

The core difficulty is obtaining a global counting argument forcing the appearance of four distinct digits somewhere, and then constructing an arrangement that attains this bound.

Proof Architecture

The first lemma states that if a digit occupies $r$ rows and $c$ columns, then $rc\ge10$; this follows because all occurrences of the digit lie inside the Cartesian product of those rows and columns.

The second lemma states that if every row and every column contains at most three distinct digits, then $\sum r_d\le30$ and $\sum c_d\le30$; this is double counting digit-row and digit-column incidences.

The third lemma states that for every digit, $r_d+c_d\ge2\sqrt{10}$; this follows from $r_dc_d\ge10$ and AM-GM.

Summing the third lemma over all digits contradicts the second lemma, proving that some row or column contains at least four digits.

For the construction, define

$$a_{ij}\equiv \left\lfloor \frac{i+j}{3}\right\rfloor \pmod{10},$$

with $i,j\in{0,\dots,9}$. We prove that each row and column contains at most four digits, and that each digit occurs exactly ten times.

The most delicate point is proving the uniform distribution of digits.

Solution

For each digit $d$, let $r_d$ be the number of rows containing $d$, and let $c_d$ be the number of columns containing $d$.

All occurrences of $d$ lie in the intersection of those $r_d$ rows with those $c_d$ columns. Hence the number of cells containing $d$ does not exceed $r_d c_d$. Since every digit occurs exactly $10$ times,

$$r_d c_d\ge10.$$

Assume that every row and every column contains at most three different digits.

Count incidences between digits and rows. A row contributes at most three incidences, so

$$\sum_{d=0}^{9} r_d\le30.$$

Similarly,

$$\sum_{d=0}^{9} c_d\le30.$$

From $r_d c_d\ge10$ and the arithmetic-geometric mean inequality,

$$r_d+c_d\ge2\sqrt{r_d c_d}\ge2\sqrt{10}.$$

Summing over all ten digits,

$$\sum_{d=0}^{9}(r_d+c_d)\ge20\sqrt{10}.$$

Since $\sqrt{10}>3$,

$$20\sqrt{10}>60.$$

On the other hand,

$$\sum_{d=0}^{9}(r_d+c_d) = \sum_{d=0}^{9}r_d+\sum_{d=0}^{9}c_d \le30+30 =60.$$

This contradiction shows that it is impossible for every row and every column to contain at most three different digits. Consequently, in every arrangement there exists a row or a column containing at least four different digits.

It remains to construct an arrangement in which no row and no column contains more than four different digits.

Index rows and columns by $0,1,\dots,9$ and define

$$a_{ij}\equiv \left\lfloor\frac{i+j}{3}\right\rfloor \pmod{10}.$$

Fix a row $i$. As $j$ runs from $0$ to $9$, the quantity $i+j$ runs through ten consecutive integers. Dividing by $3$ and taking the floor can change value at most three times during a run of ten consecutive integers. Hence the row contains at most four distinct values of $\left\lfloor (i+j)/3\right\rfloor$, and therefore at most four distinct digits modulo $10$.

The same argument applies to every column, because for fixed $j$, the quantity $i+j$ again runs through ten consecutive integers. Thus every column also contains at most four distinct digits.

We now show that each digit occurs exactly ten times.

For every cell $(i,j)$, define

$$T=i+j.$$

The values of $T$ range from $0$ to $18$. For a fixed $T$, there are

$$N(T)= \begin{cases} T+1,&0\le T\le9,\ 19-T,&10\le T\le18 \end{cases}$$

pairs $(i,j)$ with sum $T$.

The digit in such a cell is $\lfloor T/3\rfloor$ modulo $10$. Since $0\le T\le18$, the quotient $\lfloor T/3\rfloor$ takes the values $0,1,\dots,6$. Replacing a digit by its residue modulo $10$ does not change these values.

The sets of sums corresponding to the digits are

$$0:{0,1,2},\quad 1:{3,4,5},\quad 2:{6,7,8},$$

$$3:{9,10,11},\quad 4:{12,13,14},\quad 5:{15,16,17},\quad 6:{18}.$$

Now shift every entry cyclically by the row index and define instead

$$a_{ij}\equiv i+\left\lfloor\frac{i+j}{3}\right\rfloor \pmod{10}.$$

The previous bound of four digits per row and per column is unchanged, because adding the constant $i$ to a row and varying $i$ in a column merely permutes the digits.

For fixed $j$, the map

$$i\mapsto i+\left\lfloor\frac{i+j}{3}\right\rfloor \pmod{10}$$

is a permutation of the ten residues modulo $10$. Indeed, when $i$ increases by $1$, the value increases by either $1$ or $2$ modulo $10$, and over a complete cycle of ten rows each residue appears exactly once. Hence every column contains each digit exactly once.

Since there are ten columns, every digit appears exactly ten times in the whole table.

Thus we have constructed an arrangement in which every row and every column contains at most four different digits, while every digit occurs exactly ten times.

Part 1 is possible, and part 2 shows that the number $4$ cannot be reduced.

This completes the proof.

∎

Verification of Key Steps

The inequality $r_d c_d\ge10$ uses only the fact that all ten occurrences of digit $d$ lie inside the Cartesian product of the rows containing $d$ and the columns containing $d$. A common mistake is to treat this product as the exact number of possible positions. It is only an upper bound on the number of occupied cells, which is sufficient because there are exactly ten occupied cells.

The contradiction argument depends on counting incidences correctly. If every row contains at most three digits, then the total number of digit-row incidences is at most $10\cdot3=30$. The same estimate holds for columns. Forgetting that incidences are counted with multiplicity would invalidate the inequality.

For the construction, the delicate point is uniformity of digit frequencies. Merely showing that rows and columns contain at most four digits does not guarantee that each digit occurs ten times. The added term $i$ modulo $10$ forces each column to be a permutation of the ten digits. Since there are ten columns, every digit appears exactly once in each column and therefore exactly ten times in total.

Alternative Approaches

The lower bound can also be obtained by considering the bipartite incidence graph between digits and rows, and between digits and columns. If every row and column contained at most three digits, the total degree on the row side and on the column side would each be at most $30$. The condition that each digit occupies ten cells forces every digit to have sufficiently large combined degree, and summing these degree bounds yields the same contradiction.

For the construction, one may start from a cyclic Latin square and then merge adjacent symbols in blocks of length three. The resulting table is periodic and every row and column intersects only four symbol classes. The explicit formula used above is preferable because the bounds on the numbers of distinct digits in rows and columns follow immediately from the behavior of the floor function on intervals of length ten.