Manager
Joined: 11 Nov 2023
Posts: 196
Given Kudos: 76
WE:Business Development (Advertising and PR)
Re: If the number of three-element subsets of (1, 2, 3, 4, 5, . . . n), wh
[#permalink]
06 Dec 2023, 11:22
This one caught me off guard initially because I spent time thinking about a formula for the rules for elements 2 and 4, but realized it's much simpler than that.
If the part about not having 2 and 4 simultaneously wasn't a rule and we only had to find the number of 3-element subsets for each set, that can be calculated using the combination formula, \(n!/(n-3)!3!\), since order of selection does not matter.
n=4: \(\frac{4!}{1!3!} = \frac{4*3*2}{3*2} = 4\)
n=6: \( \frac{6!}{3!3!} = \frac{6*5*4}{3*2} = 20\)
n=7: \(\frac{7!}{4!3!} = \frac{7*6*5}{3*2} = 35\)
We do have to subtract the number of subsets that DO contain 2 and 4 simultaneously for each, but you could actually just answer the question here and save some time because without knowing the exact number, even for the greatest option for n we can see it'll be LESS than 35.
The number of subsets that DO contain 2 and 4 simultaneously is (n-2). Think about the 3 "spaces" for a subset of 3. If we're forced to fill 2 of those spaces with 2 and 4, then we're only left with one space to fill. The number of options left to fill that space would be n-2.