Competition problem — Combinatorics

Library / /12 of 42

Combinatorics Difficulty 5.5 AIME, harder Prove it Romania

There are 2024 cards of the same size, face-down on a table, on which the integers $1$ , $2$ , $3$ , $\dots$ , $2024$ are written. We say that a card is a *winner* if it has a number divisible by $13$ or by $100$ . What is the minimum number of cards we need to turn face up to make sure that we obtain at least one winner?

Solution

There are $155$ multiples of $13$ not larger than $2024$ : $13 \cdot 1$ , $13 \cdot 2$ , $\dots$ , $13 \cdot 155$ .

There are $20$ multiples of $100$ not larger than $2024$ : $100 \cdot 1$ , $100 \cdot 2$ , $\dots$ , $100 \cdot 20$ .

There is only one common multiple of $13$ and $100$ not larger than $2024$ , namely $1300$ .

There are $155 + 20 - 1 = 174$ numbers not larger than $2024$ , that are multiples of $13$ or multiples of $100$ . This leaves $2024 - 174 = 1850$ non-winners.

We are sure that we have obtained a winner as soon as we pick $1850 + 1 = 1851$ cards.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.