Author |
Topic: Subsets Without Consecutive Integers (Read 5306 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Subsets Without Consecutive Integers
« on: Sep 17th, 2003, 4:14pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Sep 18th, 2003, 12:41am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Subsets Without Consecutive Integers
« Reply #1 on: Sep 18th, 2003, 1:16am » |
Quote Modify
|
Cute indeed!
The answer involves the Fibonacci sequence, once again - only shifted a bit or two.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Subsets Without Consecutive Integers
« Reply #2 on: Sep 18th, 2003, 1:48am » |
Quote Modify
|
It seems simple to find the answer with induction..
|
| « Last Edit: Sep 18th, 2003, 1:51am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Subsets Without Consecutive Integers
« Reply #3 on: Sep 18th, 2003, 2:12am » |
Quote Modify
|
It never fails to amaze me how often that sequence appears...
::
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).
::
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!
|
| « Last Edit: Sep 18th, 2003, 2:14am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Subsets Without Consecutive Integers
« Reply #4 on: Sep 18th, 2003, 3:28am » |
Quote Modify
|
on Sep 18th, 2003, 2:12am, 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 wm(n) denotes the number of ways you can pave a m by n pathway using mx1 paving stones, then wm(n) = wm(n-1) + wm(n-m); wm(k) = 1 for 0 <= k < m (0 included to make recurrence formula applicable for n=m).
|
| « Last Edit: Sep 18th, 2003, 3:36am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print