In Wonderland, the government of each country consists of exactly men and women, where and are fixed natural numbers and . For improving of relationships between countries, all possible working groups consisting of exactly one government member from each country, at least among whom are women, are formed (where 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 be the number of countries in Wonderland. If the minimal number of women in working groups is then forming a working group means just choosing one government member from each country. Thus there are different working groups. This number can be prime only if because .
If the minimal number of women in working groups is then a working group containing exactly women () can be formed as follows. Choose countries out of , that send a woman to that particular working group, then choose one woman out of from each of the governments, and finally choose one man out of from each of the remaining countries. Hence there are working groups with exactly women, and working groups with at least women altogether. As , all terms of this sum are divisible by , whence the sum can be a prime only if it is equal to . This is possible only if since otherwise the last term (corresponding to ) of the sum would be greater than .