MTH4150 Home

MTH 4150: Final Practice 3

Problem 1

Let \(A=\left\{1,2,3,4,5\right\}\) and \(B=\left\{5,6,9,11\right\}\). Provide example of two functions \(f:A\to B\) and \(g:A\to B\) with domain \(A\) and codomain \(B\) such that \(f\) is onto but \(g\) is not onto.

Problem 2

Let \(A=\{1,2,3,4,5,6,7\}\). Provide an example of a permutation \(\sigma\) on \(A\) that satisfies all of the following three conditions:

  • \(1^{\circ}\) The permutation \(\sigma\) has one cycle of length 4 and one cycle of length 3;

  • \(2^{\circ}\) The number \(1\) is sent to a number greater than \(4\), i.e. \(\sigma(1) > 4\); and

  • \(3^{\circ}\) The number \(7\) is sent to a number smaller than or equal to \(5\), i.e. \(\sigma(7)\leq 5\).

Problem 3

Let \(F(X)\) be the generating function of the sequence \((a_n)_{n=0}^{\infty}\) defined as \(a_n=n\) for \(n\in\{0,1,2\}\), and \(a_n=5\), for \(n\geq 3\). Calculate \(F\left(\frac 13\right)\).

Problem 4

A box contains \(30\) red, \(40\) green, and \(50\) blue marbles.

  • (a) What is the smallest number of marbles that a blindfolded person has to take from the box to be sure that at least three marbles are of the same color?

  • (b) What is the smallest number of marbles that a blindfolded person has to take from the box to be sure that at least three marbles of different colors are taken?

Problem 5

Determine the number of ways in which the faces of the cube can be painted in \(5\) colors in such a way that not all faces are of the same color. The paintings that can be obtained from each other using rotations are considered identical.

Problem 6

Initially the numbers \(10\), \(15\), and \(20\) are written on three different whiteboards. Two players \(A\) and \(B\) play the following game. The player \(A\) starts and players alternate the moves. In each of the moves, a player has to choose one of the whiteboards, erase the number written on the board and replace it by a bigger two-digit number. The player who makes the last move is the winner. Prove that \(A\) has the winning strategy. What should player \(A\) do in its first move?

Problem 7

Let us denote by \(A\) the set of all positive integers smaller than or equal to \(10\). Find the number of functions \[f:A\to\left\{1,2,3,4,5\right\}\] for which the set \(B=\left\{x\in A: f(x)=5\right\}\) has an odd number of elements.

Problem 8

Let \(U=\left\{1,2,3,\dots, 100\right\}\) and let \[F=\left\{ (A,B,C): A, B, C\subseteq U\mbox{ such that } A\subseteq B\subseteq C\subseteq U\right\}.\] (In words, \(F\) is the sequence of all triplets whose components are subsets of \(U\) such that the first component is a subset of the second, and the second is the subset of the third.) Calculate \(|F|\).