Opsimath

2021/09/20阅读：172主题：默认主题

# TBO Problem Solving Booklet Solutions: 1-3

### Incidentally ...

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?

*Solution*.

(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
?

作者介绍