All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Consecutive Numbers and Subset Choice (Posted on 2016-02-09) Difficulty: 3 of 5
M is the number of six-element subsets that can be chosen from the set of the first 15 positive integers so that at least three of the six numbers are consecutive.
Find M.

No Solution Yet Submitted by K Sengupta    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
General Solution (from the first T numbers) Comment 6 of 6 |
Starting with T integers. instead of 15

The number of subsets with 6 consecutive is (T-5).

The number of subsets with 5 consecutive (but not six) consecutive are:
12345  = 1*(T-6) choices for the 6th element
other end = T-6 
other = (T-6) strings * (T-7) choices for the 6th element 
Total = (T-6)*(T-5)

The number of subsets with 4 consecutive (but not 5) consecutive are:
1234  = 1*c(T-5,2) choices for the 5th & 6th element = (T-5)*(T-6)/2
other end = (T-5)*(T-6)/2
other = (T-5) strings * c(T-6,2) choices for the 5th & 6th element = (T-7)(T-6)(T-5)/2
Total = (T-6)*(T-5)*(T-5)/2

The number of subsets with 3 consecutive (but not 4) consecutive are:
123  = 1*c(T-4,3) choices for the 4th & 5th & 6th element = (T-4)*(T-5)*(T-6)/6
other end = (T-4)*(T-5)*(T-6)/6
other = (T-4) strings * c(T-5,3) choices for the 4th & 5th & 6th element = 
  (T-4)*(T-5)*(T-6)*(T-7)/6
Total (including double counts) =  (T-4)*(T-5)*(T-6)*(T-5)/6 

But this double counts
123 + T-6 higher sets 
234 + (T-7) higher sets
etc.
In total, (T-6)+ (T-7) ... + 1 = (T-5)*(T-6)/2

Final Answer = 
(T-5) + (T-6)*(T-5) + (T-6)*(T-5)*(T-5)/2 + (T-4)*(T-5)*(T-6)*(T-5)/6 - (T-5)*(T-6)/2

= (T-5) + (T-6)*(T-5)/2 + (T-6)*(T-5)*(T-5)/2 + (T-4)*(T-5)*(T-6)*(T-5)/6 

= (T-5)*(T-4)/2 + (T-6)(T-5)(T-5)(T-1)/6



Checking:
when T = 6, 1*2/2 = 1
when T = 15, 10*11/2 + 9*10*10*14/6 = 55 + 2100 + 2155

  Posted by Steve Herman on 2016-02-10 20:55:43
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information