Problem

Source: Mathematics Regional Olympiad of Mexico West 2021 P4

Tags: number theory, combinatorics, Coloring



Some numbers from $1$ to $100$ are painted red so that the following two conditions are met: $\bullet$ The number $1 $ is painted red. $\bullet$ If the numbers other than $a$ and $b$ are painted red then no number between $a$ and $b$ divides the number $ab$. What is the maximum number of numbers that can be painted red?