# Recent questions and answers in Discrete Mathematics

1
Which one of the following well-formed formulae in predicate calculus is NOT valid ? $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$ $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$ ... $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$
2
Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. the integers greater than $10$ the odd negative integers the integers with absolute value less ... $A \times Z^{+}$ where $A = \{2, 3\}$ the integers that are multiples of $10$
3
Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. the negative integers the even integers the integers less than $100$ the real ... $\frac{1}{2}$ the positive integers less than $1,000,000,000$ the integers that are multiples of $7$
4
Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = 2a_{n-1} - 2a_{n-2}.$ [Note: These are complex numbers.] Find the solution of the recurrence relation in part $(A)$ with $a_{0} = 1\:\text{and}\: a_{1} = 2.$
5
Give a big-O estimate for the function $f$ in question $12$ if $f$ is an increasing function.
6
Let $f: A \rightarrow B$ a function, and let E and F be subsets of $A$. Consider the following statements about images. $S1: f(E \cup F) = f(E) \cup f(F)$ $S2: f(E \cap F)=f(E) \cap f(F)$ Which of the following is true about S1 and S2? Only S1 is correct Only S2 is correct Both S1 and S2 are correct None of S1 and S2 is correct
7
Let (G,*) be a group such that O(G) = 8, where O(G) denotes the order of the group. Which of the following is True ? There exist no element a in G whose order is 6. There exist an element a in G whose order is 4. There exist more then one element in G whose order is 1 None of these
8
Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the greatest common divisor of $m$ and $n$. $p(q - 1)$ $pq$ $\left ( p^{2}-1 \right ) (q - 1)$ $p(p - 1) (q - 1)$
9
What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs $(a,b)$ and $(c,d)$ in the chosen set such that, $a \equiv c\mod 3$ and $b \equiv d \mod 5$ $4$ $6$ $16$ $24$
10
The minimum number of cards to be dealt from an arbitrarily shuffled deck of $52$ cards to guarantee that three cards are from same suit is $3$ $8$ $9$ $12$
11
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
12
Let $f$ be a function from the set $A$ to the set $B$. Let $S$ adn$T$ be subsets of $A$ .Show that $f(S \cup T) = f(S) \cup f(T)$ $f(S \cap T) = f(S) \cap f(T)$
13
For the composition table of a cyclic group shown below: ... $a,b$ are generators $b,c$ are generators $c,d$ are generators $d,a$ are generators
14
Which one of the following is false? The set of all bijective functions on a finite set forms a group under function composition. The set $\{1, 2, \dots p-1\}$ forms a group under multiplication mod $p$, where $p$ is a prime number. The set of all strings over a finite alphabet forms a group ... group $\langle G, * \rangle$ if and only if for any pair of elements $a, b \in S, a * b^{-1} \in S$.
15
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
16
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ? $\sum_{k=1}^{n-1} k!(n-k)!$ $\frac{n!}{2}\bigg[\sum_{k=1}^{n-1} \frac{1}{k(n-k)}\bigg]$ $n!\bigg[\sum_{k=1}^{n-1} \frac{1}{k}\bigg]$ $\frac{n!(n-1)}{2}$ None of the above
17
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree
18
$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ ... $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$
19
In how many ways can a given positive integer $n \geq 2$ be expressed as the sum of $2$ positive integers (which are not necessarily distinct). For example, for $n=3$, the number of ways is $2$, i.e., $1+2, 2+1$. Give only the answer ... positive integer $n \geq k$ be expressed as the sum of $k$ positive integers (which are not necessarily distinct). Give only the answer without explanation.
20
15. a) How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two of the four aces are chosen? b) How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two of the four aces and at least ... many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds?
21
How many pairs $(x,y)$ such that $x+y <= k$, where x y and k are integers and $x,y>=0, k > 0$. Solve by summation rules. Solve by combinatorial argument.
22
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
23
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
24
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
1 vote
25
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
26
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.
27
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
28
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find $f (5)$ $f (125)$ $f (3125)$
29
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find $f (2)$ $f (8)$ $f (64)$ $(1024)$
30
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find $f (3)$ $f (27)$ $f (729)$
31
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
32
Determine a value for the constant C in Example $4$ and use it to estimate the number of bit operations needed to multiply two $64$-bit integers using the fast multiplication algorithm.
33
Express the fast multiplication algorithm in pseudocode.
34
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
35
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?
36
How many comparisons are needed for a binary search in a set of $64$ elements?
1 vote
37
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... is $m,$ there is a particular solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
Prove Theorem $4:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $r^{k}-c_{1}r^{k-1}-\dots c_{k} = 0$ has $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]
It can be shown that Cn, the average number of comparisons made by the quick sort algorithm (described in preamble to question $50$ in exercise $5.4),$ when sorting $n$ ... $48$ to solve the recurrence relation in part $(A)$ to find an explicit formula for $C_{n}.$