What is the maximum number of integers that can be chosen from $1,2,\dots,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 3-digit number?
Problem
Source: 2023 Singapore MO Round 2 Junior Q2
Tags: number theory
24.04.2024 14:46
is it 90???????????????
14.06.2024 19:15
Let us define set L{} which contains "large" numbers and set S{}, which contains "small" numbers. Let us define "large" numbers as if you choose any 2 numbers inside, the product will always be more than 999. This also means that "small" numbers are the rest of the smaller numbers. This means that set L = {32, 33, 34 ... , 98, 99} And set S = {2, 3 ... , 30, 31} (Note that we cannot have 1 as it is impossible to derive a three digit number) We should arrange these numbers is the fashion "large", "small", "large", "small", "large", "small" ... This is the most optimal way to arrange the numbers as there are more "large" numbers than "small" numbers. But we should note that every "small" number will be surrounded by 2 "large" numbers. Although 31 is a "small" number, it can only multiply with one other "large" number, it being 32. This is because any number larger than 32 will result in a product larger than 999. To counter this issue, we can group, say [4 and 31] as a singular small number. Thus the pattern will look something like "small", "large", "small", "large" ... "large", 4, 31, 32, "small", "large" This leads us to the final answer being n(S) x 2 - 1 = 59