Track / Stage 5 / 160 of 400 #1240 of 2444

Problem 1240

AIME late

Combinatorics Difficulty 5.3 Prove it Bulgarian Mathematical Competitions · Bulgaria

Ivo writes consecutively the integers $1, 2, \ldots, 100$ on 100 cards and gives some of them to Yana. It is known that for every card of Ivo and every card of Yana, the card with the sum of the numbers on the two cards is not in Ivo and the card with the product of these numbers is not in Yana. How many cards does Yana have if the card with number 13 is in Ivo?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Yana has at least one card, say $k \neq 1$ . If Ivo has $1$ , then the product $1 \cdot k = k$ does not belong to Yana, a contradiction. Therefore Yana has $1$ .

If $12$ is in Ivo, then the sum $13 = 1 + 12$ belongs to Yana, a contradiction. Therefore $12$ belongs to Yana. Since the sum $13 = 6 + 7$ is in Ivo, both cards $6$ and $7$ belong to one and the same person. They are not in Ivo since otherwise the sum $1 + 6 = 7$ is in Yana. Using similar arguments we conclude that all cards $1, 2, \ldots, 12$ belong to Yana. Further, all cards $13k$ , $k = 1, \ldots, 7$ , are in Ivo, and all the others belong to Yana. Therefore Yana has $100 - 7 = 93$ cards.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.