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.

See The Solution Submitted by K Sengupta    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts 2 computer solutions; the second is probably right | Comment 1 of 6
Method 1:

The program counts all possible locations on the 1-15 integral number line for the triplet and three separately chosen numbers for the other three.

To prevent two separate triplets or any quadruplets, quintuplets or sextuplets from being counted more than once, the triplet that's chosen as the specific triplet must be the first triplet encountered. That is, for example 2,3,4,7,8,9 is counted only when the 2,3,4 is the dedicated triplet and 7, 8 and 9 are the individual numbers chosen, not the other way around.  The individual numbers themselves are in order a < b < c, so permutations of those are not counted separately either.

The result is 2155 by method 1.

But method 2 counts only 550:

Method 2:

Just look at all the subsets and count how many meet the criterion.

It finds only 550.

Somehow the first method must be finding some subsets more than once, despite the precautions taken. Hmmm...

DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 
 Text1.Text = ""
 crlf = Chr(13) & Chr(10)
 
 For triple = 1 To 13
   For a = 1 To 13
     If a < triple Or a > triple + 2 Then
   For b = a + 1 To 14
     If b < triple Or b > triple + 2 Then
   For c = b + 1 To 15
     If c < triple Or c > triple + 2 Then
     
     s$ = Space$(15)
     Mid(s, triple, 3) = "xxx"
     Mid(s, a, 1) = "x"
     Mid(s, b, 1) = "x"
     Mid(s, c, 1) = "x"
     ix = InStr(s, "xxx")
     If ix = triple Then
       ct = ct + 1
     End If
     
     End If
   Next
     End If
   Next
     End If
   Next
 Next


 Text1.Text = Text1.Text & crlf & ct & " done method 1"
 
 ct = 0
 For a = 1 To 10
 For b = a + 1 To 11
 For c = b + 1 To 12
 For d = c + 1 To 13
 For e = d + 1 To 14
 For f = e + 1 To 15
 
 hit = 0
 If b = a + 1 Then cons = 1 Else cons = 0
 If c = b + 1 Then
  cons = cons + 1
  If cons = 3 Then hit = 1
 Else
  cons = 0
 End If
 If d = c + 1 Then
  cons = cons + 1
  If cons = 3 Then hit = 1
 Else
  cons = 0
 End If
 If e = d + 1 Then
  cons = cons + 1
  If cons = 3 Then hit = 1
 Else
  cons = 0
 End If
 If f = e + 1 Then
  cons = cons + 1
  If cons = 3 Then hit = 1
 Else
  cons = 0
 End If
 If hit Then ct = ct + 1
 
 Next
 Next
 Next
 Next
 Next
 Next
 Text1.Text = Text1.Text & crlf & ct & " done method 2"
  
End Sub

2155 done method 1
550 done method 2

  Posted by Charlie on 2016-02-09 16:06:19
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 (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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