next up previous
Next: About this document ... Up: prob2 Previous: prob2

Introduction to Discrete Mathematics, Fall 2000
Problem Set 2, 3-5 Oct.


  1. Prove the following claims:
    1. All subsets of the set of natural numbers ${\mathbf N}$ are either finite or countably infinite.
    2. The cartesian product ${\mathbf N}\times{\mathbf N}$ is countably infinite. (Hint: Think of the pairs $(m,n) \in {\mathbf N}\times{\mathbf N}$ as laid down in a two-dimensional table. Enumerate the elements of the table along diagonals that go in the lower left to upper right direction.) Note: It follows easily from this result that also the set of rational numbers ${\mathbf Q}$ is countably infinite.

  2. Prove that in any group of $n > 1$ people, there are at least two persons who have exactly equally many acquaintances in the group. A person is not counted among his/her own acquaintances, and we assume that the acquaintedness relation is symmetric, so that if $a$ is acuainted with $b$, then also $b$ is acquainted with $b$. (Hint: Apply the pigeonhole principle.)

  3. A pack of cards contains 52 cards that are divided into four ``suites'' (hearts, diamonds, clubs, spades). The cards belonging to each suite are numbered 1,...,13.
    1. How many different five-card ``poker hands'' (five-card subsets) are there?
    2. In how many ways is it possible to form a five-card ``flush'', i.e. a subset of five cards where all the cards are of the same suite?
    3. In how many ways is it possible to form a ``full house'', i.e. a five-card subset consisting of a ``three-of-a-kind'' (three cards of the same numerical value), and a ``pair'' (two cards of the same numerical value)? The same card in a full house obviously cannot belong both to the pair and the three-of-a-kind combination.

  4. Prove the following properties of the binomial coefficients:
    1. ${{n}\choose{k}} = \frac{n-k+1}{k}{{n}\choose{k-1}}, %%\qquad
\mbox{ for } 1 \leq k \leq n.$ Deduce from this fact that the binomial coefficients are increasing with respect to the index $k$ ( ${{n}\choose{k-1}} < {{n}\choose{k}}$), when $k \leq n/2$, and decreasing ( ${{n}\choose{k}} > {{n}\choose{k+1}}$), when $k \geq n/2$.
    2. Verify Pascal's formula ${{n}\choose{k}} = {{n-1}\choose{k-1}} + {{n-1}\choose{k}}, %%\qquad
\mbox{ for } 1 \leq k \leq n,$ by a direct calculation based on the defining formula for the binomial coefficients.
    3. $\sum_{i=0}^r {{n+i}\choose{n}} = {{n+r+1}\choose{n+1}},$ by induction on $r$. Which familiar formula do you obtain from this identity in the case $n=1$? Can you come up with a combinatorial argument for proving the identity?

  5. Estimate the size of the ``middlemost'' binomial coefficient ${{2n}\choose{n}}$, by approximating the factorial function with Stirling's formula: $n! \sim \sqrt{2\pi n}(n/e)^n$.

  6. Natural numbers $m$ ja $n$ are relatively prime, if they have no common factors, i.e. if their greatest common denominator is $\gcd(m,n)=1$. The value of Euler's totient function $\phi(n)$ indicates the number of natural numbers less than $n$ that are relatively prime to $n$, i.e. $\phi(n) =
\vert\{m \in {\bf N} : 1 \leq m \leq n, \gcd(m,n) = 1\}\vert.$ (Thus, for instance, $\phi(5) = 4$, $\phi(6) = 2$.) Show, using the inclusion-exclusion principle, that if the different prime factors of number $n$ are $p_1$, $p_2$,..., $p_k$, then

    \begin{displaymath}\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots
(1-\frac{1}{p_k}).\end{displaymath}


next up previous
Next: About this document ... Up: prob2 Previous: prob2
Pekka Orponen 2000-10-05