Tutorial problems for RMO 2019 : combinatorics continued

1) In how many ways can 5 men and 5 women be seated in a round table if no two women may be seated side by side?

2) Six generals propose locking a safe containing top secret with a number of different locks. Each general will be given keys to certain of these locks. How many locks are required and how many keys must each general have so that, unless at least four generals are present, the safe cannot be opened?

3) How many integers between 1000 and 9999 inclusive have distinct digits? Of these, how many are even numbers? How many consist entirely of odd digits?

4) In how many ways can 9 distinct objects be placed in 5 distinct boxes in such a way that 3 of these boxes would be occupied and 2 would be empty?

5) In how many permutations of the word AUROBIND do the vowels appear in the alphabetical order?

6) There is an unlimited supply of weights of integral numbers of grams. Using n or fewer weights, find the number of ways in which a weight of m grams can be obtained. Prove that there is a bijection of the set of all such ways on the set of increasing words of length (n-1) or (m+1) ordered letters.

7) How many distinct solutions are there of x+y+z+w=10 (a) in positive integers and (b) in non-negative integers?

8) A train with n passengers aboard makes m stops. In how many ways can the passengers distribute themselves among these m stops as alighting passengers? if we are concerned only with the number of alighting passengers at each stop, how would the answer be modified?

9) There are 16 books on a bookshelf. In how many ways can 6 of these books be selected if a selection must not include two neighbouring books?

10) Show that there are {(n=5)} \choose 5 distinct throws of a throw with n non-distinct dice.

11) Given n indistinguishable objects and n additional distinct objects —- also distinct from the earlier n objects — in how many ways can we choose n out of the 2n objects?

12) Establish the following relations:
12a) B_{n+1}=\sum_{k=0}^{n}(B_{k}){n \choose k}
12b) \sum_{k}{p \choose k}{q \choose {n-k}}={{p+q} \choose n}
12c) S_{n+1}^{m} = \sum_{k=0}^{n}{n \choose k}S_{k}^{m-1}
12d) n^{p}=\sum_{k=0}^{n}{n \choose k}k! (S_{p}^{k})

13) Prove the following identity for all real numbers x:
x^{n}= \sum_{k=1}^{n}S_{n}^{k}[x]_{k}

14) Express x^{4} in terms of {x \choose 4}, {x \choose 3}, …by using the S_{n}^{k}‘s. Express {x \choose 4} in terms of x^{4}, x^{3}, …by using the s_{n}^{k}‘s.

15) A circular loop is divided into p parts, p prime. In how many ways can we paint the loop with n colours if we do not distinguish between patterns which differ only by a rotation of the loop? Deduce Fermat’s Little theorem: n^{p}-n is divisible by p if p is prime.

16) In problem 15, prove that n^{p}-n is also divisible by 2p if p \neq 2. Where is the hypothesis that p is prime used in Problem 15 or in this problem?

17) How many equivalence relations are possible on an n-set?

18) The complete homogeneous symmetric function of n variables \alpha_{1}, \alpha_{2}, \ldots, \alpha_{n} of degree r is defined as h_{r}(\alpha_{1},\alpha_{2}, \alpha_{3}, \ldots, \alpha_{n})=\sum \alpha_{1}^{i_{1}}\alpha_{2}^{i_{2}}\ldots \alpha_{n}^{i_{n}} the summation being taken over all ordered partitions of r, where the parts are also allowed to be zero. How many terms are there in h_{r}?

Test yourself ! Improve your mettle in math !
Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.