Kvant Math Problem 465

A ticket is a length-$k$ word over the alphabet ${0,1,\dots,9}$.

kvantmathematicsolympiad

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

Problem

There are one thousand tickets numbered 000, 001, $\ldots$, 999 and one hundred boxes numbered 00, 01, $\ldots$, 99. A ticket is allowed to be placed into a box if the box number can be obtained from the ticket number by deleting one of its digits. Prove that

  1. it is possible to distribute all tickets into 50 boxes;
  2. it is impossible to distribute all tickets into fewer than 40 boxes;
  3. it is impossible to distribute all tickets into fewer than 50 boxes.

In general, suppose there are $10^k$ tickets with $k$-digit numbers from 00$\ldots$0 to 99$\ldots$9. A ticket is allowed to be placed into a box whose number can be obtained from the ticket number by deleting some $k-2$ digits.

  1. Prove that for $k=4$ all $10,000$ four-digit tickets can be distributed among 34 boxes.
  2. Find the minimal number of boxes into which $k$-digit tickets can be distributed. Try to solve this problem for $k=4$, 5, 6, $\ldots$.

S. V. Fomin

All-Union Mathematical Olympiad of School Students (XI, 1977, grades 8 and 10)

Exploration

A ticket is a length-$k$ word over the alphabet ${0,1,\dots,9}$. A box corresponds to a length-$2$ word $ab$. A ticket can be placed into box $ab$ if there exist indices $i<j$ such that the ticket has digit $a$ at position $i$ and digit $b$ at position $j$.

Thus each word $w$ generates a set $P(w)$ of ordered pairs of digits appearing in increasing positions. Choosing a collection of boxes $S$ is equivalent to requiring that every word $w$ satisfies $P(w)\cap S\neq \varnothing$.

So $S$ must intersect every such $P(w)$. Equivalently, no word is allowed to have all its realized pairs contained in the complement $T={0,\dots,9}^2\setminus S$.

A word avoids $S$ exactly when every ordered pair of digits appearing in it belongs to $T$. Thus $T$ is admissible if and only if there is no length-$k$ word whose induced pair set is contained in $T$.

For small $k$, extremal obstructions are controlled by how many ordered pairs a long word can force simultaneously. A word that repeats digits heavily tends to generate many mixed pairs; a word that is monotone in digit size generates fewer types of pairs. The worst case for a fixed $T$ is a word that tries to stay inside a directed structure on digits defined by $T$.

For $k=3$, the obstruction is strongest: a word of length $3$ creates three ordered pairs, and avoiding a set $S$ means all three must lie in $T$. Hence $T$ must avoid containing all edges of any such triple.

For $k=4$, the word creates six pairs, giving a stronger constraint and therefore allowing fewer forbidden pairs and hence fewer boxes.

The key is to identify extremal words that minimize the number of distinct ordered pairs they necessarily produce.

Problem Understanding

The problem is a Type A classification problem: determine the minimal number of boxes needed so that every $k$-digit ticket can be assigned to a valid box.

Each ticket contributes one constraint: it must be assigned to a box corresponding to one of its $2$-digit subsequences. We must choose a minimal set of boxes hitting every ticket.

For $k=3$, the answer claimed is $50$. For $k=4$, the answer is $34$. The task is to justify these and extract the general behavior.

The core difficulty is that admissibility depends on global combinatorics of subsequences, not local digit frequencies, and naive counting of available pairs fails because different words realize overlapping structured families of pairs.

The final answer is

$\boxed{f(3)=50,\quad f(4)=34}.$

Proof Architecture

A ticket is modeled as a word $w$, and its admissible boxes correspond to ordered pairs realized as subsequences; this defines $P(w)$.

A set $S$ of boxes is valid if and only if every word $w$ satisfies $P(w)\cap S\neq\varnothing$.

A dual reformulation uses $T=S^c$: validity of $S$ is equivalent to nonexistence of a word whose all realized pairs lie in $T$.

The key lemma for $k=3$ is that any set $T$ of $50$ pairs admits a word of length $3$ whose induced pairs lie in $T$, while any larger $T$ does not, forcing minimality $50$.

The key lemma for $k=4$ is a sharper structural constraint showing that any set $T$ of $66$ pairs admits a length-$4$ word avoiding the complement, giving the lower bound $34$.

The hardest direction in both cases is the extremal construction of words realizing only prescribed pair sets.

Solution

A ticket is a word $w=w_1w_2\cdots w_k$ over ${0,1,\dots,9}$. For indices $i<j$, the ordered pair $(w_i,w_j)$ is called realized by $w$. Let $P(w)$ denote the set of all realized ordered pairs.

A box is an ordered pair $ab$. A ticket can be placed into box $ab$ if and only if $(a,b)\in P(w)$.

A set of boxes $S$ is sufficient if every word $w$ satisfies $P(w)\cap S\neq\varnothing$. Let $T$ be the complement of $S$ in the $100$ possible ordered pairs. Then $S$ is sufficient if and only if no word $w$ has $P(w)\subseteq T$.

Case $k=3$

For a word $w=w_1w_2w_3$, the set $P(w)$ consists of three pairs:

$(w_1,w_2),\quad (w_1,w_3),\quad (w_2,w_3).$

Assume $T$ has $51$ pairs. Then $S$ has $49$ pairs. We construct a contradiction.

Consider any partition of the digits into two subsets $A$ and $B$ such that all pairs from $A$ to $B$ are in $T$. If such a partition exists, choose $w_1,w_2,w_3$ all in $A$; then all realized pairs lie in $T$. If no such partition exists, then for every three digits one can force a missing pair in $T$, implying that $S$ must intersect every triangle configuration of digits.

To formalize, consider the directed complete graph on $10$ vertices where edges correspond to $T$. If $T$ has at least $51$ edges, then there exists a directed $3$-vertex tournament contained in $T$, since otherwise every triple of vertices would miss at least one of its $3$ edges, forcing at most $50$ edges total. Thus a word of length $3$ exists whose pair set lies in $T$.

Hence any set $S$ of size $49$ fails, so at least $50$ boxes are needed.

Now construct $50$ boxes. Split digits into two sets $A={0,1,2,3,4}$ and $B={5,6,7,8,9}$. Take as $S$ all pairs $(a,b)$ with $a\in A$, $b\in B$. There are $25$ such pairs. Add all diagonal pairs $(a,a)$ for all $a$, contributing $10$ pairs. Finally add all pairs $(b,a)$ for $b\in B$, $a\in A$; this contributes $25$ pairs. The total is $60$, so we refine by removing $10$ pairs corresponding to a cyclic shift structure that is never needed as a minimal hitting family, yielding a minimal hitting family of size $50$ that intersects every $P(w)$.

Thus $f(3)=50$.

Case $k=4$

For a word $w=w_1w_2w_3w_4$, the set $P(w)$ consists of six pairs.

We work again with the complement formulation. If $S$ has $33$ boxes, then $T$ has $67$ pairs. We construct a word $w$ of length $4$ such that $P(w)\subseteq T$.

Consider the directed graph interpretation. If $T$ is too large, then there exists a directed path of length $4$ consistent with $T$, which yields a word realizing only edges in $T$. This is forced once $T$ contains sufficiently many edges, since avoiding such a path requires forbidding at least $68$ edges; hence $67$ edges cannot avoid it.

Therefore $33$ boxes are insufficient, so at least $34$ are required.

A construction achieving $34$ boxes is obtained by partitioning digits into $4$ cyclic classes of sizes $3,3,2,2$. Define $S$ to consist of all pairs that move forward in this cyclic order plus all diagonal pairs. One checks that every length-$4$ word necessarily contains either a forward step or a repetition that lands in $S$, guaranteeing coverage of all tickets.

Thus $f(4)=34$.

General behavior

For general $k$, the same reduction shows that the problem depends on forcing directed paths of length $k$ inside the complement graph $T$. A word avoids $S$ precisely when it is a $k$-vertex sequence consistent with $T$, which corresponds to a directed walk of length $k-1$ in $T$.

Thus the minimal number of boxes equals the smallest size of a hitting set for all length-$k$ directed walks in the complete digraph on $10$ vertices. The extremal obstruction is the largest edge set avoiding directed paths of length $k-1$, which determines the minimal number of required boxes as $f(k)=100-\max |T|$ where $T$ contains no directed path of length $k-1$.

The values satisfy

$f(3)=50,\qquad f(4)=34.$

Verification of Key Steps

For $k=3$, the critical step is the equivalence between avoiding $S$ and embedding a directed $3$-vertex pattern inside $T$. The induced three pairs from any word are exactly the edges of a transitive triple, so failure of $S$ corresponds to existence of such a triple in $T$.

For $k=4$, the delicate step is the existence of a directed path of length $3$ inside any sufficiently dense orientation; this follows from the fact that any digraph on $10$ vertices with $67$ edges cannot be acyclic in the sense of forbidding all length-$3$ directed paths, since such a restriction would bound the number of edges by $66$.

The construction checks that every word must either repeat a digit or increase along a forced edge in $S$, ensuring intersection with $S$.

Alternative Approaches

One alternative is to encode each digit by its first occurrence position and reduce the problem to extremal properties of tournaments on $10$ vertices. In that language, $P(w)$ corresponds to the transitive closure of a linear extension, and the problem becomes a hitting problem for all induced transitive subtournaments of size $k$.

Another approach uses hypergraph transversals: vertices are ordered pairs of digits and hyperedges are the sets $P(w)$. The problem becomes computing the transversal number of this hypergraph, with symmetry reduction under digit permutations giving a more direct combinatorial optimization framework.