Prove that the number of ways of choosing $6$ among the first $49$ positive integers, at least two of which are consecutive, is equal to $\binom{49}6-\binom{44}6$.
Problem
Source: Bulgaria 1980 P5
Tags: combinatorics
30.11.2021 23:05
Given the desired result, this likely is a complementary counting problem. We try to find the number of ways of choosing $6$ integers among the first $49$ positive integers such none of them are consecutive. Say we have the set $\{1, 2, 3, \dots, 44\}$ with the property that the $n$th element has value $n$. Then we could select any $6$ integers from here, but they could be consecutive. Now consider inserting an integer between the integer choices we made. The second one's value would increase by $1$, the third's by $2$,... continued for the sixth by $5$. We then end up with a set with $49$ elements as desired. Since there is now something between integers, none of our choices could be consecutive. Therefore, there are ${44\choose6}$ ways to choose without any consecutive integers, and ${49\choose6}-{44\choose6}$ ways to choose with some consecutive integers.
06.12.2021 01:44
Clever bijections go BRRRRRR This was literally 2009 AIME II Problem 6. Let's use complementary counting. Given an invalid subset $S$, we may name an element $s \in S$ with a label $B$ and all other elements as $A$. We may remove exactly one $A$ in between each pair of $B$'s, giving us $44$ elements ($6$ $A$s and $38$ $B$'s). There are exactly $\binom{44}{6}$ invalid subsets so from the total, we have $$\binom{49}{6} - \binom{44}{6}$$ valid subsets. In fact, in general if we want to choose an $k$ element subset from the first $k$ positive integers, we have $$\binom{n}{k} - \binom{n-k+1}{k}$$ distinct valid subsets using the reasoning above.