Lesson 1

Basic Problems.

1. (10 points) How many ways are there to place a pawn, a knight, and a bishop on a chessboard so that no two of these pieces are in the same row or the same column? (In this problem, it is not important how these chess pieces move: these are just three different pieces.)
2. (10 points) There are eight people to be seated around a table, with three (disjoint) pairs of friends among them. Each pair of friends wants to sit next to each other. How many different seating arrangements are possible? (Two arrangements are considered the same if they result from each other by a rotation.)
3. (10 points) How many ways are there to arrange \(10\) different books on five distinct shelves? Each shelf can accommodate an arbitrary number of books. The order of books on each shelf is significant, and the shelves are distinguishable.
4. (10 points) Twelve people are sitting around a round table. In how many ways can they be split into pairs so that each person shakes hands with exactly one other person and no two handshakes cross?
5. (10 points) A fixed diagonal of a convex \(12\)-gon splits it into a pentagon and a nonagon. How many triangulations of the original \(12\)-gon contain this diagonal?
6. (10 points) From a group consisting of seven men and four women, one needs to select six people so that there are at least two women among them. How many ways can this be done?
7. (10 points) For \(n \ge 3\), in how many ways can \(n\) items be distributed into \(n-2\) bags? The bags are indistinguishable, and the items within each bag are unordered. Moreover, each bag must contain at least one item.
8. (10 points) Let \(n \ge m \ge k \ge 0\) be integers. Provide a combinatorial proof for the identity: \[\binom{n}{m}\binom{m}{k}= \binom{n}{k}\binom{n-k}{m-k}\ .\]
9. (10 points) A student council of \(8\) members elects a chairperson from among themselves by a secret ballot. Each member casts one vote for any of the \(8\) members. An election outcome is determined by the number of votes each candidate receives. How many distinct election outcomes are possible?
10. (10 points) How many six-digit numbers are there whose sum of digits does not exceed \(47\)?
11. (10 points) Prove the following identity: \[\binom{\binom{n}{2}}{2}= 3 \binom{n+1}{4}.\]
    Hint:

    Count the number of ways to choose two distinct edges in a complete graph on \(n\) vertices.
12. (10 points) Give a combinatorial proof of the following identity: \[\sum\limits_{i = 0}^{n} i \cdot (n-i) = \binom{n+1}{3}.\]
13. (15 points) The tickets for a New Year's party cost \(50\) cents, and there are \(30\) guests standing in a line to buy them. Half of the guests have \(1\) dollar each, while the other half have \(50\) cents. The cashier, dressed as Santa, starts selling tickets with no money in the register. How many different orders of guests in the queue ensure that Santa can always give change?
14. (15 points) Let \(s_{n}\) be the product of the terms in the \(n\)-th row of Pascal's triangle. Then \[\lim_{n \to \infty}\frac{s_{n-1}s_{n+1}}{s_n^2}= e.\]
15. (15 points) We say that a Boolean function \(f(x_{1}, \dotsc, x_{n})\) depends essentially on \(x_{i}\) if, for some assignment \((a_{1}, \dotsc, a_{n}) \in \{0,1\}^{n}\), the value of \(f\) flips when one flips the value of \(x_{i}\): \[f(a_{1}, \dotsc, a_{i-1}, a_{i}, a_{i+1}, \dotsc, a_{n}) \neq f(a_{1}, \dotsc, a_{i-1}, a_{i} \oplus 1, a_{i+1}, \dotsc, a_{n}).\] Find the number of Boolean functions of five variables that depend essentially on all five variables.