number of ways to choose subsets from 11 boys and 12 girls where number of girls in the subset is one more than boys Disclaimer: This is from AIME 2020 that has ended yesterday. https://www.maa.org/math-competitions/about-amc/events-calendar
A club has 11 boys, 12 girls. We need to choose a subset of kids from them, such that the number of girls is one more than the number of boys in this subset. The subset needs to have at least 1 but at most 23 kids. The subset could have as few as 1 kid or as many as 23. Let N be the number of such subsets we can form. Find the sum of prime numbers that divide N. 
I think this is equivalent of choose $m$ boys and $m$ girls at the same time. Since each of the subset asked in the problem is corresponds to $m$ boys and $m$ girls unselected. So it's sum of ${11 \choose m}*{12 \choose m}$. But what's the easy way to find summation and its prime factors? 
 A: You can quickly get a closed form for the summation as follows:
$$\sum_{k=0}^{11}\binom{11}k\binom{12}{k+1}=\sum_{k=0}^{11}\binom{11}k\binom{12}{12-(k+1)}=\binom{23}{11}$$
The last equality is Vandermonde's identity. There is a combinatorial proof as well. Instead of choosing the boys to include and the girls to include, choose the boys to include and the girls to exclude. If there are $k$ boys to incude, then there are $12-(k+1)$ girls to exclude, so you need a selection of $k+(12-(k+1))=11$ students, selected from all $23$ students.
Obviously, the primes that divide $\binom{23}{11}$ contain $23, 19, 17, 13$. You can then count the factors of $2,3 ,5$ and $7$ in the numerator and denominator to figure out which ones appear in the prime factorization.
A: Here's a way to see that $N = { 23 \choose 11 } $ directly.
Given the 23 kids, choose any 11 of them.
If a boy was chosen (or not chosen), keep his status.
If a girl was chosen (or not chosen), toggle her status.
Say there are $x$ boys chosen. Then, there were $11-x$ girls chosen originally, so there are now $ 12 - (11-x) = x + 1$ girls chosen after the toggle.
So, this satisfies the conditions.    
It is easy to see that is a bijection between sets of "1 more girl chosen than boy" and "11 kids chosen", hence $ N = { 23 \choose 11 }$.   
Proceed as in Mike's solution / expand the binomial coefficient to determine the primes. 

Obviously, this "uniquely" works because $12 = 11 + 1$.    
Also, you might recognize that this is equivalent as the ${12 \choose k+1 } = { 12 \choose 12 - (k+1) } $ step in Mike's solution.
And of course, the Vandermonde's identity step maps to the combinatorial identity that is used to prove Vandermonde.

It should be reminiscent of a problem of a similar flavor.   

You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which. How do you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.

A: You want to choose one more girl than boy, so any valid subset has $k$ boys and $k+1$ girls for some integer $k$. The question states:

The subset needs to have at least 1 but at most 23 kids. The subset could have as few as 1 kid or as many as 23.

Let $n$ be the total number of boys, so that $n+1$ is the total number of girls, i.e. $n=11$. Thus, the valid range for $k$ is $0 \leq k \leq n$.
We want to pick $k$ boys and $k+1$ girls. For a given value of $k$, then, the number of such possible choices is
$$\begin{pmatrix} n \\ k \end{pmatrix} \times \begin{pmatrix} n+1 \\ k+1 \end{pmatrix},$$
where $\begin{pmatrix} n \\ k \end{pmatrix}$ denotes "n choose k", which is defined by
$$\begin{pmatrix} n \\ k \end{pmatrix} := \frac{n!}{k!(n-k)!}.$$
Since we can use any of the valid values of $k$, the total number of valid choices, $N$, is given by
$$
\begin{align}
N  &= \sum_{k=0}^{n} {\begin{pmatrix} n \\ k \end{pmatrix} \times \begin{pmatrix} n+1 \\ k+1 \end{pmatrix}}
\\ &= \sum_{k=0}^{11} {\begin{pmatrix} 11 \\ k \end{pmatrix} \times \begin{pmatrix} 12 \\ k+1 \end{pmatrix}}.
\end{align}$$

It then remains to determine the prime factors of $N$ and compute their sum. Given that this is an AIME question, and I can't think of a more elegant solution,* I would be inclined to just compute $N$ by hand by constructing Pascal's triangle. Each term in the sum for $N$ is then the product of a number on row 11 and the number immediately to the bottom-right of it (the next number on row 12). The result is $N = 1352078$.
We can determine the prime factorisation of $N$ by repeatedly dividing it by the smallest prime number that may be a factor. When the result of a division is 1, we have determined all the prime factors and thus stop. To speed up the process, we may use various divisibility tests:


*

*$2 \mid 1352078$, division by which yields $676039$. Since $2 \not\mid 676039$, we move on to the next prime.

*$3 \not\mid 676039$, so we move on.

*$5 \not\mid 676039$, so we move on.

*$7 \mid 676039$, division by which yields $96577$. Since $7 \not\mid 96577$, we move on.

*etc. — I checked higher prime numbers, for which I didn't remember any nice tricks, simply by performing long division at each step. Since I would have to do that anyway if a divisibility test succeeded, it doesn't waste much time.


Using this process, we see that the prime factorisation of $N$ is
$$N = 2 \times 7 \times 13 \times 17 \times 19 \times 23.$$
The sum of these factors is 81.

*since we only know $N$ as a sum of terms, and — to my knowledge — there is no useful fact/theorem here, such as how to determine whether a prime is a factor of a sum based on whether it is a factor of any of the summands. Indeed, $p \mid a \wedge p \mid b \implies p \mid a+b$; but since $p \mid a$ alone does not imply $p \mid a+b$, even if one knows all the prime factors of $a$ and $b$, this does not yield all of the prime factors of $a+b$.
Example: $2 \mid 4$ and $5 \mid 5$, but $2,5 \not\mid 4+5$. Moreover, $3 \mid 4+5$, seemingly out of nowhere!
I'd love to see a more elegant solution!
