What a difference ....

We can use recurrence relations to solve this problem.

Let $a_{n}$ be the number of subsets of $\{1, 2, ..., n\}$ in which no two elements have a difference less than $3$ . We then have two cases to look at to set up the recurrence relation:

(i) for subsets that exclude $n$ we have $(n - 1)$ consecutive elements remaining to choose from, giving us $a_{n-1}$ subsets;

(ii) for subsets that include $n$ we must exclude $(n - 1)$ and $(n - 2)$ , but we can include any of the other $(n - 3)$ consecutive elements remaining, giving us $a_{n-3}$ subsets.

So we have the recurrence relation $a_{n} = a_{n-1} + a_{n-3}$ , which only makes sense for $n \gt 3$ . It is clear, though, that $a_{1} = 2, a_{2} = 3$ and $a_{3} = 4$ . Using these seed values and the relation we can fairly quickly work our way up the sequence to find that $a_{15} = \boxed{406}$ .

(We might want to find a closed-form formula if we want to deal with large $n$ , but for $n = 15$ it was easy enough to just to work our way up the sequence one at a time.)

Imagine a strip of $17$ squares numbered $1,2,3,\ldots,17$ , where we put $n$ blocks that cover $3$ squares each, and write the smallest number that it covers on top of it. Then no two of these "block numbers" have difference less than $3$ and all of them are taken from $\{1,2,\ldots,15\}$ , since $16, 17$ cannot appear (if they appear, then a smaller number must be covered by the block and thus the block doesn't show the smallest number it covers, contradiction), and hence the blocks numbers form a subset that satisfies the asked property. In addition, if we know the block numbers, we can construct the unique configuration of blocks, thus we have a bijection between subsets of $A$ with $n$ elements that have the desired property and configurations of $n$ blocks.

Now, to count the number of possible configurations, we can imagine that we put smaller blocks that cover $1$ square each for the uncovered squares. Thus we have $n$ large, 3-square blocks, and $17-3n$ small, 1-square blocks. There are clearly $\binom{n + (17-3n)}{n}$ = $\binom{17-2n}{n}$ configurations of these blocks, and since we have a bijection, there are also $\binom{17-2n}{n}$ satisfying subsets of $n$ elements.

Clearly $0 \le n \le 5$ ; for $n > 5$ , we have a negative number of 1-square blocks, and for $n < 0$ , we have a negative number of 3-square blocks. Thus add up $\binom{17-2n}{n}$ for $0 \le n \le 5$ :

$\displaystyle\sum_{n=0}^5 \binom{17-2n}{n}$

$= \binom{17}{0} + \binom{15}{1} + \binom{13}{2} + \binom{11}{3} + \binom{9}{4} + \binom{7}{5}$

$= 1 + 15 + 78 + 165 + 126 + 21 = \boxed{406}$

In this case,maximum number of elements that can be selected is 5 at a time.

Now imagine that we have selected those 5 elements with the required conditions and number of elements not chosen between any two elements is $x_{i}$ .

Then $x_{1}$ + $x_{2}$ + $x_{3}$ + $x_{4}$ + $x_{5}$ + $x_{6}$ =10 (Here, $x_{1}$ are the leading elements and $x_{6}$ are trailing elements)

Now $x_{2}$ , $x_{3}$ , $x_{4}$ , $x_{5}$ are minimum 2 then

Let

$x_{2}$ -2=w

$x_{3}$ -2=x

$x_{4}$ -2=y

$x_{5}$ -2=z

We`ll get $x_{1}$ +w+2+x+2+y+2+z+2+ $x_{6}$ =10 and hence,

$x_{1}$ +w+x+y+z+ $x_{6}$ =2

where w,x,y,z can be 0.Now,this has turned to standard Ball-and-urn problem whose solution is $\begin{pmatrix} 2+6-1 & \\ 2 & \end{pmatrix}$ =21 Similarly,we`ll take case with 4 elements ,3 elements,2 elements,1 element and get

$\begin{pmatrix} 2+6-1 & \\ 2 & \end{pmatrix}+\begin{pmatrix} 5+5-1 & \\ 5 & \end{pmatrix}+\begin{pmatrix} 8+4-1 & \\ 8 & \end{pmatrix}+\begin{pmatrix} 11+3-1 & \\ 11 & \end{pmatrix}+\begin{pmatrix} 14+2-1 & \\ 14 & \end{pmatrix}$

=21 +126+165+78+15=405

And we add 1 for null set

$\Longrightarrow$ $\boxed{405+1=406}$

Intuitive C++ program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>

int main() {
    int a[16],i,j,s=0;
    a[0]=1;
    a[1]=1;
    a[2]=1;
    for(i=3;i<16;++i){
        a[i]=0;
        for(j=0;j<=i-3;++j){
            a[i]+=a[j];
        }
    }
    for(i=0;i<16;++i){
        s+=a[i];
    }

    std::cout<<s<<"\n";
    return 0;
}