Manager
Joined: 11 Nov 2023
Posts: 228
Given Kudos: 78
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: 4!1!3!=4∗3∗23∗2=4
n=6: 6!3!3!=6∗5∗43∗2=20
n=7: 7!4!3!=7∗6∗53∗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.