Competition problem — Combinatorics

Library / /24 of 104

Combinatorics Difficulty 5.3 AIME, harder Prove it Bulgaria

Problem:

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?

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.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.