Question number 25. Tom wrote down several distinct positive integers, none of them greater than 100. Their product was not divisible by 18. At most how many numbers could he have written? So when avoiding divisibility by 18, Tom has to avoid dividing by the factors that make up 18. So 18 has the prime factorization 9 times 2, so 3 squared times 2 and prime factors, and there are two choices. So either if Tom here avoids evens, what happens? He skips the 50 even integers between 1 and 100 and has the other numbers remaining, so has 50 integers. So this product would contain 50 integers. On the other hand, if Tom avoids multiples of 3, what happens then? He skips exactly 33 numbers. There are 33 multiples of 3 between 1 and 100 and has therefore the other remaining 67 integers. And of these 67 integers, a lot of them are going to be even. So what we can do is then allow one even integer in the product. So the product will be divisible by 2 and by 3. So when we choose this even integer, we have to allow one even integer here, which should also say not also divisible by 3. So say that we allow the number 2. So we have 67 integers and then some other integer that is only divisible by 2 and not by 3. So 6, for example, would not be allowed because we want to make sure that we have no two factors of 3. So this product is divisible by 2 and by 3, but then in the end not by 18. OK, and how many integers do we have in this product? We would have our 67 integers here and then one more here that's divisible by 2 and not by 3. So for a total of 68 numbers in the product, 68 factors, and the answer here is C.

divisibility

strategy

numbers

maximum

product