MTH4150 Home

MTH 4150: Final Practice 2

Problem 1

Assume that \( A \), \( B \), and \( C \) are three sets. Determine the number of elements of the set \( A\cup B\cup C \) if it is known that \begin{eqnarray*} &&|A| = 16,\quad |B|=17,\quad |C|=22, \quad \left|A\cap B\cap C\right|=3,\newline &&\left|A\cap B\right|=8,\quad \left|B\cap C\right|=8,\quad \left|C\cap A\right|=10. \end{eqnarray*}

Problem 2

The first pile contains \( 85 \) coins and the second pile contains \( 105 \) coins. Two players \( A \) and \( B \) play the following game. The player \( A \) starts, the players alternate their moves, and in each of the moves a player must choose a pile and take several coins from it. The player must take at least one coin in each of the moves. The player who makes the last move wins the game. Which player has the winning strategy and what is the strategy?

Problem 3

  • (a) Provide an example of a function \( f:\{ 1,2,3,4,5 \}\to \{ 1,A,B,C,D,E \} \) that satisfies \( f(2)=1 \) and that is not one-to-one.

  • (b) Provide an example of a function \( g:\{ 1,2,3,4,5 \}\to \{ 1,A,B,C,D,E \} \) that satisfies \( g(2)=1 \) and that is one-to-one.

  • (c) Determine the number of functions \( g:\{ 1,2,3,4,5 \}\to \{ 1,A,B,C,D,E \} \) that satisfy \( g(2)=1 \) and that are one-to-one.

Problem 4

Use the principle of mathematical induction to prove that the inequality \(n! > 2^n\) holds for every integer \(n\geq 4\).

Problem 5

The sequence \( (a_n)_{n=0}^{\infty} \) satisfies \( a_0=17 \) and \[ a_{n+1}=4a_n+15,\quad\mbox{for }n\geq 0.\] Determine the generating function for the given sequence and use the obtained result to determine the formula for \( a_n \).

Problem 6

In how many different ways can one paint the vertices of the square in \(18\) colors? Two colorings are considered the same if one can be obtained from the other by rotations or reflections.

Problem 7

Let us denote by \( S \) the set of all sequences of length \( 9 \) whose terms are letters from the set \( \{A, B,C\} \). Denote by \( T\subseteq S \) the set of those sequences from \(S\) that contain at most two letters \(A\).

  • (a) How many elements does the set \( T \) have?

  • (b) If \( \sigma=(1869753)(24) \) is the permutation that acts on \( T \), determine the set \( \mbox{Inv }(\sigma) \).

Problem 8

There are \( 20 \) green and \( 70 \) red apples. In how many ways can these apples be distributed to \( 15 \) children so that both of the following two conditions are satisfied:

  • (i) All apples are distributed;

  • (ii) Each child gets more red apples than green apples?