I am asked to determine the biggest natural number $n$ such that the complementary of any subset with $n$ elements of the set $A=\{1, 2, 3, …, 2003\}$ contains at least one pair of consecutive numbers.
My progress so far:
I know that the number of susets is $2^{2003}$. We may ask: how many subsets of ${1,2,...,2003}$ have no two consecutive numbers ? Well, the subsets are interpreted as $n$-words from the alphabet ${0,1}$. Let an be the number of words with no consecutive ones. Then, a word can start from $0$ and proceed in $a_{n−1}$ ways or start with $10$ and proceed in $an−2$ ways. Therefore, $an=a_{n−1}+a_{n−2}$, $a_1=2$,$a_2=3$. So, $a_n$=$F_{n+2}$. So, in our case, we have $F(2005)$. However, this still does not answer our question.
I saw Largest value of $n$ such that the complementary set of any $n$-element subset contains at least two elements that are coprime. Does it apply here? Any help, please?
The answer comes from insight, not calculation. There are sufficient hints in the comments, but to flesh those ideas out:
$A$ contains $1001$ even numbers and $1002$ odd numbers. If you remove all of the even numbers, the remaining subset of $1002$ odd numbers has no two consecutive numbers. If you add back one even number, it falls between two odd numbers, so it creates two distinct pairs of consecutive numbers: $2n-1,2n$ and $2n,2n+1$. So removing one odd number in an attempt to offset the added even number is insufficient to remove all pairs of consecutive numbers. In general, you have to remove at least one more odd number than the number of even numbers you restore in order to avoid consecutive pairs.
So a subset with $1002$ odd numbers plus $1$ even number (total of $1003$ elements) must have at least one pair of consecutive numbers. Therefore, the largest $n$ is $2003-1003=1000$. That is to say, you can remove $n=1001$ or more elements in some manner that leaves all non-consecutive numbers. If you remove fewer than $1001$ elements, there will always be at least $1003$ remaining elements, which perforce must feature at least one pair of consecutive numbers.