Question number 25. Tom wants to write several distinct positive integers, none of them exceeding 100. Their product cannot be divisible by 54. At most, how many integers can he write? So we note that the product is not divisible by 54. We just write it like that, not divisible by 54, and so it's easier to check divisibility if we have the prime factorization, and that would be 2 times 3 cubed is 54. So now we note that between 1 and 100, there are 50 even integers, and 33 exactly integers divisible by 3. So we have a couple of choices. In our product, we can avoid even numbers, or we can avoid numbers divisible by 3. Now if we avoid numbers divisible by 3, we would be left with 67 factors, and that's more than if we were to avoid even numbers. So let's do that. Let's multiply the 67 numbers not divisible by 3. So then 3 does not divide our product, but 2 probably does. 2 probably divides the product, and so we can throw in some more factors that are divisible by 3. We are allowed 2 factors that are divisible by 3, so we can then multiply by 3 and by 6, which we could not have used before to get 69 factors, and still only divisible by 2 times 3 squared. And throwing in one more factor, 2 times 3 cubed divides it. So we can't do that. 69 is then therefore the best result. Increasing that number by one more would break the divisibility condition. So we started with 67, we threw in the maximum number of factors to keep our divisibility condition, and that came out to be 2 more factors, so our best result here is 69, and that's answer D.

distinct integers

divisibility

product rule

positive integers

maximum count