Learn / Library / Brainteasers

Marks on a lottery card

BrainteasersHard

A lottery card has squares numbered $1$ to $100$ . You mark distinct squares. What is the smallest number of marked squares that guarantees $2$ marked numbers that differ by exactly $10$ ?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Split the numbers into chains that step by $10$ and ask how many you can take from each chain.

Solution

Numbers with the same last digit form $10$ chains of $10$ , such as $3$ , $13$ , $23$ , …, $93$ , and a difference of $10$ only occurs between neighbours in one chain.
In a chain of $10$ you can take at most $5$ numbers with no $2$ neighbours, for example every other one.
So $10 \times 5 = 50$ numbers can avoid the difference, for example $1$ to $10$ , $21$ to $30$ , $41$ to $50$ , $61$ to $70$ and $81$ to $90$ .
Any $51$ numbers put at least $6$ in some chain, which forces $2$ neighbours, so the answer is $51$ .

Answer: $51$

Next question Back to the library