Track / Stage 5 / 108 of 400 #708 of 1964

Problem 708

AIME late

Combinatorics Difficulty 5.3 Prove it Singapore Mathematical Olympiad (SMO) · Singapore

What is the maximum number of integers that can be chosen from $1, 2, \ldots, 99$ so that the chosen integers can be arranged in a circle with the property that the product of every pair of neighbouring integers is a 3-digit number?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Since $31 \times 32 = 992$ and $31 \times 33 = 1023$ , any two numbers larger than $31$ cannot be neighbours. So there must be a number $< 32$ between a pair of such numbers. Also $1$ cannot be chosen. Also the two neighbours of $31$ are $32$ or less. So the maximum number of chosen integers is $\le 30 \times 2 - 1 = 59$ . This bound can be achieved by the following where $11$ follows $31$ to form a cycle.

$11, 83, 12, 76, 13, 71, 14, 66, 15, 62, 16, 58, 17, 55, 18, 52, 19, 49,$
$20, 47, 3, 99, 2, 98, 4, 97, 5, 96, 6, 95, 7, 94, 8, 93, 9, 92, 10, 46, 21, 45,$
$22, 43, 23, 41, 24, 39, 25, 38, 26, 37, 27, 35, 28, 34, 29, 33, 30, 32, 31$

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.