Kvant Math Problem 758

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m21s
Source on kvant.digital

Problem

What is the smallest number of integers that must be crossed out from the sequence 1, 2, 3, $\dots$, 1982 so that none of the remaining integers is equal to the product of two other remaining integers?

L. D. Kurlyandchik

All-Union Mathematical Olympiad for School Students (1982, 9th grade)

Exploration

Let $R$ be the set of remaining integers, and let $A=R\setminus{1}$.

The condition says that no element of $R$ is equal to the product of two other elements of $R$. Since the factors must be different from the product itself, the number $1$ plays no role. Thus for $A$ the condition becomes:

If $a,b\in A$ and $ab\le 1982$, then $ab\notin A$.

A very simple construction is obtained by deleting all integers from $2$ to $44$. Then every remaining integer greater than $1$ is at least $45$, and

$$45^2=2025>1982.$$

Hence the product of any two remaining integers greater than $1$ exceeds $1982$, so the condition is satisfied. This uses only $43$ deletions.

The question is whether fewer than $43$ deletions can suffice.

Suppose some numbers from $2,3,\dots,44$ remain. Let $B$ be the set of such remaining numbers and let $t=|B|$. Every number in $(2,\dots,44)\setminus B$ has been deleted, contributing $43-t$ deletions.

Now consider the products of elements of $B$. If $m=\max B$, then for every $b\in B$ the product $mb$ is at most $44^2=1936$, hence lies in the interval $[1,1982]$. These $t$ products are distinct. None of them can remain, because both factors belong to $R$. Thus at least $t$ additional numbers must be deleted.

This yields at least

$$(43-t)+t=43$$

deletions. The construction above attains $43$, so the answer should be $43$.

The step most likely to hide an error is the claim that the products $mb$ are all distinct and all must be deleted. That point needs a completely explicit justification.

Problem Understanding

We must remove as few integers as possible from

$$1,2,3,\dots,1982$$

so that among the remaining integers there is no number equal to the product of two other remaining integers.

This is a Type C problem. We seek the minimum possible number of deletions.

The anticipated answer is $43$. The reason is that deleting all integers from $2$ through $44$ leaves only numbers greater than $44$ (besides $1$), and any product of two such numbers exceeds $1982$.

Proof Architecture

Lemma 1. If all integers $2,3,\dots,44$ are deleted, then the condition of the problem is satisfied. The reason is that any two remaining integers greater than $1$ have product exceeding $1982$.

Lemma 2. Let $B$ be the set of remaining integers belonging to $[2,44]$, and let $t=|B|$. Then at least $t$ integers outside $[2,44]$ must also be deleted. The reason is that if $m=\max B$, the $t$ numbers $mb$ with $b\in B$ are distinct elements of $[1,1982]$ and none of them may remain.

Lemma 3. Any admissible configuration req