Kvant Math Problem 496

Verified: yes
Verdicts: PASS + PASS
Solve time: 9m01s
Source on kvant.digital

Problem

Which six-digit numbers are more numerous: those that can be represented as the product of two three-digit numbers, or those that cannot?

S. V. Fomin

Exploration

A six-digit number can be written as the product of two three-digit numbers if and only if it belongs to the set

$$S={ab:100\le a,b\le 999}.$$

The question asks whether $|S|$ is larger or smaller than the number of six-digit integers outside $S$.

There are

$$900000$$

six-digit integers altogether, namely from $100000$ to $999999$.

The products of two three-digit numbers range from

$$100\cdot100=10000$$

to

$$999\cdot999=998001.$$

Hence only numbers between $100000$ and $998001$ can possibly occur. The interval contains

$$998001-100000+1=898002$$

six-digit integers.

If one could show that fewer than half of these $898002$ numbers belong to $S$, the problem would be solved immediately, because then fewer than $449001$ six-digit numbers are representable, while more than $450999$ are not.

A natural idea is to count representations. There are

$$900^2=810000$$

ordered pairs $(a,b)$ of three-digit numbers. Each pair produces one product. If every product were different, there would be $810000$ representable numbers, but many collisions occur.

The crucial point is to obtain a lower bound for the average multiplicity of representation. Numbers of the form

$$ab$$

and

$$ba$$

coincide, so every product coming from distinct factors is represented at least twice. Only squares $a^2$ arise from a single ordered pair. There are only $900$ such squares.

This suggests estimating the number of distinct products by dividing the total number $810000$ of ordered pairs by roughly $2$.

Indeed, if every non-square product contributes at least two ordered representations and squares contribute one, then the number of distinct products cannot exceed

$$900+\frac{810000-900}{2}=405450.$$

This is already below $449001$, which should settle the problem.

The delicate step is making this counting argument rigorous and ensuring that no product with distinct factors is counted only once.

Problem Understanding

We must compare two quantities among the six-digit integers:

$$R={\text{six-digit numbers representable as }ab,\ 100\le a,b\le 999},$$

and its complement among all six-digit numbers.

This is a Type A problem. We are classifying six-digit numbers into representable and non-representable and determining which class is larger.

The core difficulty is estimating the number of distinct products without computing it exactly. The key observation is that the map $(a,b)\mapsto ab$ is highly non-injective, because exchanging the factors does not change the product.

The answer should be that non-representable six-digit numbers are more numerous. Intuitively, there are only $810000$ ordered pairs of three-digit factors, while most products arise from at least two such pairs, namely $(a,b)$ and $(b,a)$.

Proof Architecture

Let $S$ be the set of six-digit numbers representable as the product of two three-digit numbers.

First claim: there are $810000$ ordered pairs $(a,b)$ with $100\le a,b\le 999$.

Second claim: among these pairs, exactly $900$ have $a=b$.

Third claim: every product arising from a pair with $a\ne b$ is represented by at least two ordered pairs, namely $(a,b)$ and $(b,a)$.

Fourth claim: the number of distinct products arising from all $810000$ ordered pairs is at most

$$900+\frac{810000-900}{2}=405450.$$

Fifth claim: there are

$$898002$$

six-digit integers that can possibly occur as such products, namely those from $100000$ to $998001$.

The hardest step is the fourth claim, where the multiplicity estimate must be converted into a bound for the number of distinct products.

Solution

Let

$$S={n:\ n=ab,\ 100\le a,b\le 999,\ n\text{ is six-digit}}.$$

We shall estimate $|S|$.

There are

$$900^2=810000$$

ordered pairs $(a,b)$ of three-digit numbers.

Among these pairs, exactly $900$ satisfy $a=b$, namely

$$(100,100),(101,101),\dots,(999,999).$$

The remaining

$$810000-900=809100$$

pairs have distinct coordinates.

Consider any product $n=ab$ obtained from a pair with $a\ne b$. Then

$$n=ab=ba,$$

and $(b,a)$ is a different ordered pair. Hence every such product is represented by at least two ordered pairs.

Therefore the $809100$ non-diagonal pairs can produce at most

$$\frac{809100}{2}=404550$$

distinct products.

The $900$ diagonal pairs produce at most $900$ additional products. Consequently the total number of distinct products of two three-digit numbers does not exceed

$$404550+900=405450.$$

Hence

$$|S|\le 405450.$$

Now every product of two three-digit numbers lies between

$$100\cdot100=10000$$

and

$$999\cdot999=998001.$$

Thus every six-digit representable number belongs to the interval

$$100000\le n\le 998001.$$

The number of integers in this interval equals

$$998001-100000+1=898002.$$

Since

$$405450<\frac{898002}{2}=449001,$$

fewer than half of the integers in this interval are representable.

Therefore the number of six-digit integers that are not representable is at least

$$898002-405450=492552,$$

which is greater than $405450$.

Thus among the six-digit numbers, those that cannot be represented as the product of two three-digit numbers are more numerous.

$$\boxed{\text{The non-representable six-digit numbers are more numerous.}}$$

Verification of Key Steps

The first delicate point is the estimate for the number of distinct products. The argument does not assume that every non-square product has exactly two representations. Some products may have many more, for example

$$360000=600\cdot600=500\cdot720=450\cdot800.$$

Additional representations only decrease the number of distinct products obtainable from a fixed number of ordered pairs. The bound

$$\frac{809100}{2}$$

remains valid because each distinct non-square product consumes at least two non-diagonal ordered pairs.

The second delicate point is the treatment of squares. A square such as

$$40000=200^2$$

may also have representations with unequal factors. Counting all $900$ diagonal pairs as producing different additional products gives the largest possible value of $|S|$. Since we seek an upper bound, this cannot invalidate the argument.

The third delicate point is the comparison threshold. The interval from $100000$ to $998001$ contains

$$898002$$

numbers, not $898001$. The extra $1$ comes from including both endpoints. Half of this number is

$$449001,$$

and the estimate

$$405450<449001$$

is the inequality that yields the conclusion.

Alternative Approaches

One may regard the $810000$ ordered pairs as vertices of a counting problem and partition them into the $900$ diagonal pairs and the unordered pairs ${(a,b),(b,a)}$ with $a\ne b$. Every distinct product corresponds to at least one such block, while each non-diagonal block contains two ordered pairs producing the same product. Counting blocks directly again yields the upper bound $405450$.

Another approach is probabilistic. Choose an ordered pair of three-digit numbers uniformly at random. The symmetry $(a,b)\leftrightarrow(b,a)$ shows that, except on the diagonal of size $900$, products occur in pairs of ordered representations. Averaging multiplicities gives an average representation count exceeding $2$ by a negligible amount, leading to the same estimate for the number of distinct products. The direct counting argument used above is preferable because it is completely elementary and avoids introducing probabilistic language.