Catarina has 210 numbered cards from 1 to 210.

a) How many of these cards have a number that is a multiple of 3?

b) How many of these cards have an even number that is not a multiple of 3?

c) What is the smallest number of cards Catarina must pick at random to be sure that at least two of them have the number 2 or the number 3 as a common divisor?
Solution

a) Since $210 \div 3=70$, there are 70 cards whose numbers are multiples of 3. More precisely, these cards are numbered $3=1 \times 3, 6=2 \times 3, 9=3 \times 3, 12=4 \times 3, \ldots, 204=68 \times 3, 207=69 \times 3$, and $210=70 \times 3$.

b) $1^{st}$ solution: A reasoning identical to that in part a) shows that there are $210 \div 2=105$ cards with even numbers between 1 and 210 (inclusive). On the other hand, the even numbers between 1 and 210 that are multiples of 3 are $2 \times 3, 4 \times 3, 6 \times 3, \ldots, 68 \times 3$, and $70 \times 3$, totaling 35. Therefore, there are $105-35=70$ cards with even numbers that are not multiples of 3.

$2^{nd}$ solution: There are 105 even cards. On the other hand, among the 70 multiples of 3, there are $70 \div 2=35$ even numbers; thus $105-35=70$ are even but not multiples of 3.

$3^{rd}$ solution: Removing the 70 cards whose numbers are multiples of 3 leaves 210-70 = 140 cards. Of these, half are even, as between two consecutive multiples of 3, one number is even and the other is odd; thus among them there are $140-70=70$ cards that are neither even nor multiples of 3.

$4^{th}$ solution: We observe that, between 1 and 6, there are two even numbers that are not multiples of 3, namely, 2 and 4. Similarly, between 7 and 13, there are two even numbers that are not multiples of 3, namely, 8 and 10. This pattern repeats every block of six consecutive numbers up to the block of 205 to 210. In this last block, the numbers that are not multiples of 3 are 206 and 208. Thus, we have $210 \div 6=35$ blocks, and in each block, there are two even numbers that are not multiples of 3, for a total of $35 \times 2=70$ numbers.

c) Parts A, B, and C of the figure below correspond to the conclusions of the previous items. Therefore, there remain cards with numbers that are neither even nor multiples of 3, corresponding to part $\mathbf{D}$. By choosing a number from part $\mathbf{A}$, another from part $\mathbf{B}$ (or $\mathbf{C}$), and 70 from part $\mathbf{D}$, we see that it is possible to choose 72 cards such that any two of them do not contain numbers that are simultaneously even or multiples of 3. On the other hand, by choosing 73 cards, the numbers of at least three of them must be outside part $\mathbf{D}$, i.e., they must belong to parts $\mathbf{A}$, $\mathbf{B}$, and $\mathbf{C}$. If two of these numbers are in the same part, they have 2 or 3 (or both, in the case of being in part A) as a common divisor. Otherwise, we have one in part A and another in part B (or C) that have 3 (or 2) as a common divisor. Therefore, Catarina must take 73 cards.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-17.jpg?height=311&width=599&top_left_y=2169&top_left_x=840)