Problem 10 · The product that dodges 18
Since $18 = 2 \cdot 3^2$, it's enough to control the threes.
Integer answer, at most 4 digitsClara wrote down several positive integers, all different and strictly less than $101$. She computed their product and got a number not divisible by $18$. At most how many numbers can Clara have written?
Reasoned solution
Key idea: $18 = 2 \cdot 3^2$: the product escapes if it lacks the factor $2$ or carries at most one factor $3$.
Between $1$ and $100$ there are $33$ multiples of $3$, i.e. $67$ numbers that aren't. Clara can take all $67$ of them and add one multiple of $3$ that isn't a multiple of $9$ (say $3$ itself): the product has exactly one factor $3$, is not divisible by $9$, hence not by $18$. Total: $68$ numbers.
She can't do better: with $69$ numbers at least two would be multiples of $3$ (only $67$ aren't), so $9$ would divide the product; and since there are only $50$ odd numbers, some even number would be included too. The product would be a multiple of $2 \cdot 9 = 18$.