An integer set T is orensan if there exist integers a<b<c, where a and c are part of T, but b is not part of T. Count the number of subsets T of {1,2,...,2019} which are orensan.
Problem
Source: 2019 Spain Mathematical Olympiad P1
Tags: Spain, Problem Sets, combinatorics
07.04.2019 21:28
Welcome to AoPS!
05.01.2020 23:14
juanbri wrote: An integer set T is orensan if there exist integers a<b<c, where a and c are part of T, but b is not part of T. Count the number of subsets T of {1,2,...,2019} which are orensan. We count the number of non-oresan sets.The total number of subsets are $2^{2019}$.Now clearly $\phi$ and single element sets aka $\{1\},\{2\},\cdots \{2019\}$ are non-oresan.Now for any $\ell_1<\ell_2$ we have the non-oresan set containing $\ell_1,\ell_2$ as the minimum and maximum element respectively must have all numbers $\ell_1<i<\ell_2$ in it.This gives a bijection between the the non-oresan sets of cardinality $\geq 2$ and the number of ways to choose two distinct numbers from $\{1,2,\cdots 2019\}$.The latter is clearly $\binom{2019}{2}$.Hence the answer is \[2^{2019}-2020-\binom{2019}{2} \; \square\]
28.04.2021 12:27
The same solution could be attained by subtracting $\frac{2019(2020)}{2}+1$(summing $1$ to count the empty set)