Maths Olympiad Prep

Library / /18 of 19

Combinatorics Difficulty 8.8 Shortlist Prove it Estonia

In Wonderland, the government of each country consists of exactly aa men and bb women, where aa and bb are fixed natural numbers and b>1b > 1. For improving of relationships between countries, all possible working groups consisting of exactly one government member from each country, at least nn among whom are women, are formed (where nn is a fixed non-negative integer). The same person may belong to many working groups. Find all possibilities how many countries can be in Wonderland, given that the number of all working groups is prime.

Solution

Let rr be the number of countries in Wonderland. If the minimal number of women in working groups is n=0n = 0 then forming a working group means just choosing one government member from each country. Thus there are (a+b)r(a+b)^r different working groups. This number can be prime only if r=1r = 1 because a+bb>1a+b \ge b > 1.

If the minimal number of women in working groups is n1n \ge 1 then a working group containing exactly kk women (nkrn \le k \le r) can be formed as follows. Choose kk countries out of rr, that send a woman to that particular working group, then choose one woman out of bb from each of the kk governments, and finally choose one man out of aa from each of the remaining rkr-k countries. Hence there are (rk)bkark\binom{r}{k} b^k a^{r-k} working groups with exactly kk women, and k=nr(rk)bkark\sum_{k=n}^{r} \binom{r}{k} b^k a^{r-k} working groups with at least nn women altogether. As n1n \ge 1, all terms of this sum are divisible by bb, whence the sum can be a prime only if it is equal to bb. This is possible only if r=1r=1 since otherwise the last term (corresponding to k=rk=r) of the sum would be greater than bb.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.