Competition problem — Combinatorics

Library / /4 of 14

Combinatorics Difficulty 5.3 AIME, harder Prove it 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?

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$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.