TBO Problem Solving Booklet Solutions: 1-3
My initial source of interview questions has been used up. I am now turning to another set of problems: the (in)famous TBO Problem Solving Booklet. It contains 151 questions; I will do 3 of them per day (since they are a little harder than my previous questions).
1. Arrangement of digits
Question. How many ways can you arrange each of the digits 1 to 6 to create distinct 6 digit numbers? How many of these contain the digits 1, 2 and 3 next to each other and in that order? In how many arrangements does 5 occur before 1? How many distinct 6 digit numbers are there in which all of the digits 1 to 5 appear?
(i) It's obviously (6 for the first digit, 5 for the second, etc.).
(ii) It must be of the pattern 123xxx, x123xx, xx123x, and xxx123, where each x represent one of 4, 5, or 6. Thus, the number of arrangements is .
(iii) It's just half the answer of (i) which is 360 due to symmetry.
(iv) Assuming leading zeroes count as 6 digit numbers. Using the principle of inclusion-exclusion, we have ways without any restrictions, ways without including as a digit for which there are combinations for , ways without including nor , for which there are combinations, and so on.
Hence, the solution (including leading zeroes) is We can then subtract the number of combinations with leading zeroes, giving .
Extension. What about digits for the last part?
2. The power set
Question. The power set is formed from all subsets of a given set. If a set contains elements, what is the cardinality of its power set? How many subsets contain a given element ?
Solution. For a subset, each element is either selected or unselected, giving possible elements of a power set, of which half containing a particular element (i.e., ).
Extension. Think of another method for the first part by considering binomial coefficients. Then prove their equivalence.
3. A round table
Question. If a round table has people sitting around it, what is the probability of person A sitting exactly seats away from person B?
Solution. If or , the probability is trivially 0. Otherwise, there are arrangements in total. There are exactly two seats B can take in a particular arrangement due to symmetry, the probability being .
Extension. The above solution is actually incomplete. What if is even and is half of ?