Competition problem — Combinatorics

Library / /10 of 34

Combinatorics Difficulty 5.2 AIME, harder Prove it Romania

Consider the set $A = \{1, 2, 3, \dots, 2017\}$ . Determine the number of three element subsets $B \subset A$ , which satisfy the following conditions simultaneously:
a) at least two elements in the set $B$ are consecutive positive integers;
b) there is an $a \in B$ , such that $3a \in B$ .

Solution

The sets we search contain elements $a$ , $3a$ , with $3a \le 2017$ , so $a \le 672$ . For $a = 1$ , we have $\{1, 3\} \subset B$ , and the possible sets are $\{1, 2, 3\}$ and $\{1, 3, 4\}$ . For $a \in \{2, 3, 4, \dots, 672\}$ we have the sets $\{a-1, a, 3a\}$ , $\{a, a+1, 3a\}$ , $\{a, 3a-1, 3a\}$ and $\{a, 3a, 3a+1\}$ , which are all distinct, giving a total of $4 \cdot 671 = 2684$ sets. So the number of sets with the required properties is $2686$ .

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.