Question: Let $S = \{1,2,3,.....,44,45\}$. Find the maximum value of $n$ such that it is possible to select $n$ numbers from $S$ and arrange them in a circle in such a way that the product of any two adjacent numbers in the circle is less than $100$?
Effort: I’m starting to learn the Pigeon Hole Principle and I stumbled upon this question. So I first tried to condense the information. My first question was, do you randomly select the numbers from the set? I assumed so and proceeded. So each adjacent number’s product has to be lesser than $100$. Thus, I tried to find two consecutive numbers which multiply to a number less than $100$, and tried to find the maximum values. The reason I did that’s was because I assumed that the circle went in a consecutive order, so the circle would go ie ‘$1,2,3,4,5 ,\ldots, 9, 10$’. I quickly realised that this was the wrong approach as I then I saw that it didn’t have to be consecutive. It could even be something like ‘$1,45,2,44$’ or ‘$1, 20,2,19,3,18,4,17,5,16,6,15$’. I could have proceeded, but I knew that even if I get the right answer, it wouldn’t help me in future because there was certainly a more shorter and elegant solution to the problem which I didn’t know of. Thus, I uploaded this question.
