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
ItsAmeYushi
07.04.2019 21:28
Welcome to AoPS!
This is simply asking how many subsets of $\{1,2,3,...,2018,2019\}$ contain no pairs of consecutive integers. This is actually a known problem but here is a small proof:
Call an n-word a string of length n consisting of $1$'s and $0$'s such that iff the $i$th digit of the n-word is $1$ then $i$ is in the corresponding subset. An n-word with no consecutive $1$'s satisfies the condition. The n-words can either start with $0$ and proceed in $a_{n-1}$ ways or start with $1,0$ and proceed in $a_{n-2}$. Since the base cases of $a_0$ and $a_1$ are both $1$, this is the Fibonacci sequence so the answer is $F(2019)$ or the $2019$th Fibonacci number.
Pluto1708
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\]
FibonacciMoose
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)