wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Subsets Without Consecutive Integers
        
(Message started by: william wu on Sep 17^th, 2003, 4:14pm)

Title: Subsets Without Consecutive Integers
Post by william wu on Sep 17^th, 2003, 4:14pm

Cute problem: Consider the set of all natural numbers from 1 to n. How many subsets of this set contain no consecutive integers? Count the empty set as a subset as well.

Note: (12:37 AM 9/18/2003 Verbose explanation for what this problem means in case anyone reading this is puzzled) Natural numbers from 1 to n means the set of numbers {1, 2, 3, ..., n}, where n is some natural number. A subset of this set is simply some collection of unique numbers, where each number is a natural number ranging between 1 and n inclusive. So for example, if n = 3, then the set of natural numbers from 1 to n is {1,2,3}, and the possible subsets are {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}, and {[emptyset]}. [emptyset] means "empty set", which is just nothingness -- nothing is always a subset of a set. How many of these subsets contain no consecutive integers? The answer is 5: {1},{2},{3},{1,3},and {[emptyset]}. All the other sets have at least one pair of integers which are back to back in the ordering of numbers; for example, {1,2} has 1 and 2 which are consecutive integers, and {1,2,3} has the pairs 1,2 and 2,3. Now the question is asking, for the set {1,...,n}, how many subsets have no consecutive integers? Your answer should be a [possibly familiar] algebraic expression in terms of the variable n.

Title: Re: Subsets Without Consecutive Integers
Post by wowbagger on Sep 18^th, 2003, 1:16am

Cute indeed!

The answer involves [hide]the Fibonacci sequence[/hide], once again - only shifted a bit or two.

Title: Re: Subsets Without Consecutive Integers
Post by towr on Sep 18^th, 2003, 1:48am

It seems simple to find the answer with induction..

Title: Re: Subsets Without Consecutive Integers
Post by Sir Col on Sep 18^th, 2003, 2:12am

It never fails to amaze me how often that sequence appears...
::[hide]
Let f(n) define the number of subsets of the natural numbers 1 to n that do not contain consecutive numbers.

Writing out the subsets for n=1,2,3,4,5, reveals that: f(1)=2, f(2)=3, f(3)=5, f(4)=8, f(5)=13.

Suggesting a second order recurrence relation, f(n)=f(n-1)+f(n-2) (Fibonacci).

This can be proved by the usual method:
Let us call the number of members found in the set of integers 1 to n, set A, and the number of members will be f(n). We shall say that it is made up of two mutually exclusive groups: those which contain n (set B), and those which do not contain n (set C).

Set C (which does not contain n) is equivalent to the complete set for 1 to (n-1). So the number of members of set C is f(n-1).

Set B (which contains n), must be mutually exclusive to set C, and so it cannot contain (n-1); otherwise it would be the complete set A. Hence the consecutive integers (n-1) and n cannot be members of this group. That is, the number of members will be equivalent to f(n-2).

Therefore, Set A = Set B + Set C, implies that f(n)=f(n-1)+f(n-2).
[/hide]::

A related problem...

Using 2x1 paving stones, how many different ways can you pave a 2 by n pathway?

What about using 3x1 stones on a 3 by n pathway?
Generalise!

Title: Re: Subsets Without Consecutive Integers
Post by wowbagger on Sep 18^th, 2003, 3:28am

on 09/18/03 at 02:12:15, Sir Col wrote:

It never fails to amaze me how often that sequence appears...

Seems to be almost omnipresent, doesn't it?
By the way, I found the recurrence relation without looking at the first few values, so I was even more surprised, I'd say.

Quote:

Using 2x1 paving stones, how many different ways can you pave a 2 by n pathway?

What about using 3x1 stones on a 3 by n pathway?
Generalise!

Wild guess: If w_m(n) denotes the number of ways you can pave a m by n pathway using mx1 paving stones, then [hide]w_m(n) = w_m(n-1) + w_m(n-m); w_m(k) = 1 for 0 <= k < m (0 included to make recurrence formula applicable for n=m)[/hide].