Math Problems Vault

Problem 62

(a)(b)(c)

Let $X$ be a set of three elements. Find the number of

?

(a)

two-place functions that can be defined on $X$ ;

(b)

three-place functions that can be defined on $X$ ;

(c)

three-place relations that can be defined on $X$ .

Problem 63

Let $A=\left\{ a, b, c, d, e, f, g, h\right\}$ . How many

?

(a)

three-element subsets of the set $A$ are there?

(b)

five-element subsets of the set $A$ containing $b$ are there?

(c)

five-element subsets of the set $A$ not containing $b$ are there?

(d)

five-element subsets of the set $A$ containing $c$ but not containing $f$ and $h$ are there?

(e)

subsets of the set $A$ containing at least three elements are there?

(f)

subsets of the set $A$ containing at most six elements are there?

Problem 64

(a)(b)(c)

How many strictly increasing sequences of integers are there that

?

(a)

begin with 1 and end with 7?

(b)

begin with 4 and end with 11?

(c)

begin with $k$ and end with $k+m$ ?

Problem 65

Suppose there are $n$ pairwise disjoint sets $A_{1}, A_{2}, \ldots , A_{n}$ and $\left|A_{i}\right|=k_{i}, i=1, \ldots , n$ . Prove that the number of sets containing at most one element from each $A_{i}$ equals $\left(k_{1}+1\right)\left(k_{2}+1\right) \cdots \left(k_{n}+1\right)$ .

?

Problem 66

Let $n=p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{r}^{k_{r}}$ be the factorization of $n$ into prime factors. Using the previous problem, prove that the number of distinct divisors of $n$ equals $t(n)=\prod_{i=1}^{r}\left(k_{i}+1\right)$ . Prove that $n$ is a perfect square if and only if $t(n)$ is odd.

?

Problem 67

The number $e$ is the sum of the following series: $e=\sum_{i=0}^{\infty } 1 / i!$ . Let $e_{n}$ be the sum of the first $n$ terms of this series: $e_{n}=\sum_{i<n} 1 / i!$ . Prove that $A_{n}$ — the total number of arrangements without repetition of $n$ objects taken any number of positions $m$ — equals $e_{n} n!$ . Conclude that for large $n$ it is approximately equal to en!.

?

Problem 68

(a)(b)(c)

Prove the identities:

?

(a)

$C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}$ ;

(b)

$n C_{n-1}^{k-1}=k C_{n}^{k}$ ;

(c)

$C_{n}^{k} C_{n-k}^{m-k}=C_{m}^{k} C_{n}^{m}$ .

Problem 69

Prove the binomial theorem using mathematical induction.

?

Problem 70

Prove that

\begin{aligned} C_{n}^{0}<C_{n}^{1}<\ldots <C_{n}^{\lfloor n / 2\rfloor -1} & <C_{n}^{\lfloor n / 2\rfloor } \\ & =C_{n}^{\lceil n / 2\rceil }>C_{n}^{\lceil n / 2\rceil +1}>\ldots >C_{n}^{n-1}>C_{n}^{n}, \end{aligned}

where $\lfloor x\rfloor$ and $\lceil x\rceil$ denote rounding of the number $x$ to the nearest integer down and up, respectively.

?

Problem 71

How many distinct paths are there in the plane from the point $(0,0)$ to the point $(x, y)$ , passing through points with integer coordinates, in which each unit-length segment goes either left to right or bottom to top?

?

Problem 72

(a)(b)

?

(a)

In the expansion of $(x+2 y)^{7}$ find the coefficient of $x^{3} y^{4}$ .

(b)

In the expansion of $(5 x-y)^{6}$ find the coefficient of $x^{3} y^{3}$ .

Problem 73

In the expansion of $\left(1+x^{2}+x^{5}\right)^{15}$ find the coefficient of $x^{20}$ .

?

Problem 74

Prove that the number of partitions of an $n$ -element set into $k$ subsets, the first of which contains $n_{1}$ elements, the second $n_{2}$ elements, $\ldots$ , the $k$ -th $-n_{k}$ elements, equals $\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!}$ .

?

Problem 75

Determine how many distinct words can be formed from the letters of the word АБРАКАДАБРА, if each letter must be used exactly once.

?

Problem 76

Prove the equality

\left(x_{1}+x_{2}+\cdots +x_{k}\right)^{n}=\sum _{n_{1}+n_{2}+\cdots +n_{k}=n} \frac{n!}{n_{1}!n_{2}!\ldots n_{k}!} x_{1}^{n_{1}} x_{2}^{n_{2}} \ldots x_{k}^{n_{k}}.

?

Problem 77

(a)(b)(c)(d)

Find the number of deals for each of the following card games.

?

(a)

In bridge, a deck of 52 cards is dealt to four players, 13 cards each.

(b)

In preferans, a deck of 32 cards is dealt to three players, 10 cards each, and the remaining 2 cards are left in the widow (talon). The order of the cards in the widow matters.

(c)

In durak, a deck of 36 cards is dealt to four players — 6 cards each, and the remaining 12 cards are left in the stock. The order of the cards in the stock matters.

(d)

Suppose that in some card game a deck of $N$ cards is dealt to $k$ players — $r$ cards each, and the remaining $m=N-k r$ cards are left in the widow. Derive formulas determining in how many ways such a deal can be made in the cases when (i) the order of the cards in the widow is immaterial, (ii) the order of the cards in the widow matters.

Problem 78

A lecturer plans to teach the same course for 20 years. To avoid boring the students, he decided to tell them three jokes each year, and this set of three jokes must never repeat. What is the minimum number of jokes he must prepare?

?

Problem 79

It is known that among all five-element subsets of the set $\left\{ 1,2,3, \ldots , n\right\} , n \geqslant 7$ , a quarter contain the element 7. Determine the value of $n$ .

?

Problem 80

On an island there lives a tribe of natives whose set of teeth in the mouth consists of at most 30 teeth. Moreover, on the island there are no two inhabitants with identical sets of teeth (two sets are identical if for both people each tooth is either simultaneously present or simultaneously absent). Can this island have more inhabitants than there are in

?

(a)

Torzhok?

(b)

Tver?

(c)

Moscow?

(d)

Russia? $\circledast$

(e)

the entire world?

Problem 81

Prove the Cauchy identity:

C_{n+m}^{k}=\sum _{i=0}^{i=k} C_{n}^{i} C_{m}^{k-i}.

?

Problem 82

Prove that the number $C_{n}^{k}$ is odd if and only if $\rho (k) \subseteq \rho (n)$ , where the value of the function $\rho (x)$ is the set of binary digit positions that contain ones in the binary representation of the number $x$ . In other words, if in the binary representation of $k$ some digit position holds a one, then the binary representation of $n$ must also hold a one in that position. Hint. Use induction on $n$ , represent $n=2^{u}+m$ for $1 \leqslant m \leqslant 2^{u}$ and apply the Cauchy identity.

?

Problem 83

A multiset is an unordered collection of elements, each of which can occur in it any number of times. Two multisets are equal if each element occurs in them the same number of times. For example, the multiset $\left\{ 1,2,1,3\right\}$ equals the multiset $\left\{ 3,1,1,2\right\}$ and does not equal the multiset $\left\{ 1,2,2,3\right\}$ .

Prove that the number of ways in which one can produce a $k$ -element multiset, having $n$ pairwise distinct elements and using each of them any number of times, equals $C_{n+k-1}^{k}$ .

?

Problem 84

Determine how many natural-number solutions the equation $x+y+z+u=10$ has.

?

Problem 85

How many natural-number solutions does the equation $x_{1}+\cdots +x_{n}=k$ have, if $x_{i} \geqslant m$ for all $i=1, \ldots , n$ ?

?

Problem 86

How many natural-number solutions does the equation $x_{1}+\cdots +x_{n}=k$ have, if $k \geqslant (n-1) m$ and $x_{i} \leqslant m$ for all $i=1, \ldots , n$ ?

?

Problem 87

The parliament of a certain country has 401 seats. In how many ways can the seats in the parliament be distributed among three parties so that none of them has an absolute majority (more than half of the seats)?

?

Problem 88

(a)(b)(c)

A pastry shop sells four kinds of pastries: choux, shortcrust, "kartoshka", and sponge cake. In how many ways can one buy

?

(a)

6 pastries?

(b)

7 pastries?

(c)

7 pastries, if at least one pastry of each kind must be bought?

Problem 89

Let us call two outcomes of the Russian football championship coinciding in the main respect if in these outcomes the holders of the gold, silver, and bronze medals coincide, as well as the two teams leaving the premier league (that is, the two teams taking the last two places). Find the number of distinct main outcomes (recall that 16 teams take part in the championship).

?

Problem 90

In how many ways can one arrange $n$ balls, of which $m$ are black and the rest white, in a row so that no two black balls end up adjacent?

?

Problem 91

Prove the identity $\sum_{2 m \leqslant n+1} C_{n-m+1}^{m}=F_{n+2}$ .

?

Problem 92

There are $n$ books on a bookshelf. In how many ways can one take $m$ books so as not to take adjacent books nor books standing at the ends of the shelf?

?

Problem 93

Around King Arthur's round table sit 12 knights. Each of them is at odds with his neighbors. Five knights need to be chosen to free the princess. In how many ways can this be done so that no two enemies are among the chosen knights?

Solve this problem for the case when $k$ knights need to be chosen from $n$ knights seated at the table.

?

Problem 94

Prove the inclusion–exclusion principle in set-theoretic form: if $A_{1}, \ldots , A_{n}$ are finite sets, then

\left|\bigcup _{i=1}^{n} A_{i}\right|=-\sum _{\substack {I \subseteq \left\{ 1, \ldots , n\right\} \\ I \neq \varnothing }}(-1)^{\left|I\right|}\left|\bigcap _{i \in I} A_{i}\right|.

?

Problem 95

How many of the first hundred positive natural numbers are not divisible by any of the numbers $2,3,5$ ? And among the first thousand numbers?

?

Problem 96

Determine how many integer solutions the following system has:

\begin{cases} x+y & +z=11 \\ 0 & \leqslant x \leqslant 4 \\ 0 & \leqslant y \leqslant 3 \\ 0 & \leqslant z \leqslant 7 \end{cases}

?

Problem 97

Find the number of permutations of $n$ elements in which no element remains in its original position.

?

Problem 98

How many permutations of the letters $\left\{ a, c, f, m, p, r, t, x\right\}$ are there if

?

(a)

there are no restrictions;

(b)

there must be two or three letters between $a$ and $c$ ;

(c)

the letters $a$ and $c$ must not be separated by two or three letters;

(d)

the first four letters must be chosen from $a, c, f$ and $r$ ;

(e)

the letters $a, c, f$ and $r$ must stand next to each other?

Problem 99

Two teams play volleyball until one of them has three wins. How many different ways are there for the score to evolve across the sets?

?

Problem 100

$n$ students take part in a programming olympiad. The three people taking the prize places receive diplomas of the first, second, and third degree, and another five people receive identical laureate diplomas. How many different ways of awarding are there?

?

Problem 101

$n$ girls form a round dance. In how many different ways can they stand in a circle?

?

Problem 102

Five young men and five young women bought 10 movie tickets in the same row. In how many ways can they take their seats if

?

(a)

all the young men will sit together;

(b)

two young men will sit at the ends;

(c)

no two young men will sit next to each other;

(d)

neither the young men nor the young women will all sit together;

(e)

one young man and one young woman will always sit next to each other;

(f)

one young man and one young woman refuse to sit next to each other?

Problem 103

Prove that the number of words of length $n$ over an alphabet of $k$ letters, in which every letter occurs at least once, equals

U^{*}(n, k)=\sum _{i=0}^{k-1}(-1)^{i} C_{k}^{i}(k-i)^{n}

?

Problem 104

The head of a laboratory has five employees. In how many ways can he distribute 8 distinct tasks among them so that everyone has at least one task?

?