Track / Stage 5 / 50 of 400 #650 of 1964

Problem 650

AIME late

Number theory Difficulty 5.2 Find the answer

8. How few numbers is it possible to cross out from the sequence
$1,2,3, \ldots, 2023$
so that among those left no number is the product of any two (distinct) other numbers?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

Solution. It is clear that, if we remove 43 numbers $2,3, \ldots, 44$ , then, since $45^{2}=$ 2025, among those left no one is the product of any two others. This is the minimal number. To prove that consider 43 triples $(k, 89-k,(89-k) k)$ , for $k=2, \ldots, 44$ . They do not have numbers in common and we have to remove at least one number from every such triple.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.