Question

Combinatorics problem, feel free to take a stab at it.

How many subsets of \(\{1,2,...,20\}\) DO NOT contain two elements whose difference is 2?

Answer 1

For a bigger challenge, try to find the number of subsets of the set of \(n\) consecutive positive integers, \(\{1,2,...,n\}\) that do not contain two elements whose difference is \(k\), where \(k\le n-1\).

Answer 2

there's a diffrence 2 ,so i think first we need to consider two sets\[S_1=( 1,3,5,7,,19)\\and\\S_2=(2,4,6,8,,,,20)\\here~each ~term ~has~a~ diffrence ~2\]
is it ok? i dont know
cant think of next step

Answer 3

ok i can define\[X={(1,2,3,4,....20})\]
now if i take a subset of X say Y
then \[Y=s_1 \bigcup s_2,\\for~no~elements~with~diffrence~2\]

Answer 4

Is it 20736 for the first one?

Answer 5

@eliassaab Full disclosure: I hadn't made any concrete attempts to the problem yet, so I don't have a solution yet. I've only been thinking about to approach it, and I think it'd be a lot like figuring out how many subsets a set of \(n\) elements has (which is \(2^n\)) in the sense that it'd be a sum of binomial coefficients.

@sidsiddhartha I'm not sure I follow. I think I do, but not certain.

Answer 6

Can we calculate the number of subsets that do contains 2 elements with difference k, then subtract that from the total number of subsets ? o.O

Answer 7

sounds like one of those nice applications of pigeonhole principle

Answer 8

LOL ''pigeonhole''

Answer 9

yes i found some thing called " pigeonhole principle" but it just flew over my head like a pigeon :P

Answer 10

found this one , but did'nt get the solution

Answer 11

nice :)

Answer 12

can u please explain the solution @ganeshie8 :)

Answer 13

the number of subsets of \(\{1,2,3,\ldots ,2n\}\) that DO NOT contain two elements whose difference is 2 is

\[\large F_{n+2}^2\]

Answer 14

that pdf has proof for that, lets see the general idea

Answer 15

Consider a subset \(T\) satisfying given condition

This subset cannot have consecutive even numbers and also cannot have consecutive odd numbers

Answer 16

yes

Answer 17

say the number of subsets with ONLY EVEN numbers that satisfy the given condition = \(a_n\)

then the number of subsets with ONLY ODD numbers will also be \(a_n\)

consequently the total number of subsets would be \(a_n \times a_n = a_n^2\)

Answer 18

Next we use induction

Answer 19

nice i getting it now :)

Answer 20

ok!!

Answer 21

actually that was no typo :

number of subsets of {1} containing `no two consecutive elemtns` = 2

number of subsets of {1, 2} `no two consecutive elemtns` = 3 (there is a typo in ur pdf)

Answer 22

for \(n\ge 3\) :

number of subsets without \(n\) containing `no two consecutive elements` = \(a_{n-1}\)

number of subsets with \(n\) containing `no two consecutive elements` = \(a_{n-2}\)

Overall : total number of subsets of {1,2,3,...,n} containining `no two consecutive elements` = \(a_{n-1}+a_{n-2}\)

Answer 23

thats how a fibonacci series is generating :O

Answer 24

the sequence \(\{a_n\}\) starts like below :
\[2, 3, \ldots\]
\(a_{n} = a_{n-1}+a_{n-2}\)

Answer 25

yes thats easy :) lets see if we can figure out the hard problem when the difference is "k"

Answer 26

great!!

Answer 27

using the same idea, we can split the set into "k" groups of size \(\frac{n}{k}\) each

Answer 28

maybe lets also assume \(k | n\) (this is necessary for using the previous idea)

Answer 29

ok i'm following :)

Answer 30

lets rephrase the problem :

Find the number of subsets of the set of consecutive positive integers, \(\{1,2,\ldots,kn\}\) that do not contain two elements whose difference is \(k\), where \(k\le kn-1\).

Answer 31

lets divide the set into k groups : \(0\pmod {k}, ~1\pmod{k}, ~\ldots, ~ k-1 \pmod{k} \)

Answer 32

we mimic the same argument again

Answer 33

Consider a subset \(T\) satisfying given condition

This subset cannot have consecutive elements from any of the above \(k\) groups

Answer 34

yes

Answer 35

say the number of subsets satisfying the given condition from any one of the above \(k\) groups = \(a_n\)

consequently the total number of subsets satisfying the given condition would be \(\large {a_n}^k\)

Answer 36

Notice that in each of the above k groups, below property holds :

number of subsets satisfying given condition = number of subsets with no cnsecutive elements

Answer 37

yes necessary condition :)

Answer 38

we're done if we find the number of subsets of a group with no consecutive elements : \(a_n\)

Answer 39

number of subsets of {1} containing no two consecutive elemtns = 2

number of subsets of {1, 2} containing no two consecutive elemtns = 3

Answer 40

you arrive at the same formula : \(a_n = a_{n-1}+a_{n-2}\)

Answer 41

The desired count would be \[\large {F_{n+2}}^k\]

\(\square\)

Answer 42

lets test if that really works for few n, k values

Answer 43

Clearly that works when k=2 as we have proven earlier

Answer 44

yes this works nicely :)

Answer 45

thank u for ur explanation :)

Answer 46

and i would like to learn that "Pigeon hole" concept from you sometime :)

Answer 47

if its first time, you will find it amazing seeing its application in action :)
below is a problem that can be worked out using pigeonhole principle

```
The tail of a rational number contains repeated digit pattern
```

another interesting problem
http://math.stackexchange.com/questions/1031818/a-pigeonhole-principle-question

i'll need to review a bit, haven't used this recently

Answer 48

thanks i'll check it out

Answer 49

have fun ;)

Answer 50

Actually, that how I saw 144^2=20736 which a square a the Fibonacci number 144, but did not have a proof. I got it, by writing a small script in Mathematica that took a bit of time to do it.

Answer 51

Here is the Mathematica Script
TestDifTwo[S_List] := Module[{T, k, test, H, n, Q, p},
Q = {};
p = Length[S];
H = Subsets[S];
n = Length[H];
For [ j = 1, j <= n,
test = 1;
S1 = H[[j]];

k = Length[S1];
T = Sort[S1] ; If[k == 0, Q = Append[Q, T]];
If[k == 1, Q = Append[Q, T]];
If[k == 2 && T[[2]] - T[[1]] != 2, Q = Append[Q, T]];
If [ k > 2,
For[i = 1, i <= k - 2,

If[T[[i + 2]] - T[[i]] == 2 || T[[i + 1]] - T[[i]] == 2 ||
T[[i + 2]] - T[[i + 1]] == 2, test = 0;]; i++];
If [ test == 1, Q = Append[Q, S1]]; ] j++];
Return[ Length[Q]
]

Answer 52

we have two abstract groups of order 2
\(\large \{1,3\},...\{17,19\}\\
\large \{2,4\},...,\{18,20\}\)
that can't be a subset of any set

Answer 53

now , there is 2^20 sets

18 of order 2 + 18(18) combination of order 3 + 9(18) combination of order 4+....+ 1 of order 20 xD
ugh lol too much work

Answer 54

Actually in the case of k=1, the answer is very well known.
If
\[
r=\frac{1}{2}
\left(\sqrt{5}+1\right)
\]
then the number of subsets of{0,1,23,...n} that do not contain consecutive integers is
\[
\frac{r^{n+2}-(1-r)^{n+2}}{\sq
rt{5}}
\]

Answer 55

\[\frac{r^{n+2}-(1-r)^{n+2}}{\sqrt{5}}\]
@ganeshie8

Answer 56

thats nth term of fibonacci sequence xD

Answer 57

pretty amazing !