24-25-1-离散数学II-期中

1.

Find 7602mod  617^{602} \mod 61.

2.

Find all solutions, if any, to the system of congruences

{x≡3(mod7)x≡2(mod5)\begin{cases} x \equiv 3 (\mathrm{mod} 7) \\ x \equiv 2 (\mathrm{mod} 5) \end{cases}

3.

(a) How many different strings can be made by reordering the letters of the word MATHEMATICAL?

(b) How many bit strings of length 11 have more 0’s than 1’s?

4.

How many ways can be made by distribute hands of 7 cards each to 3 players from a standard deck of 54 cards?

5.

(a) Find the number of solutions to x+y+z=47x + y + z = 47, where xx, yy, and zz are nonnegative integers.

(b) Answer part (a), but assume that x≥7x \geq 7 and y≥15y \geq 15.

6.

How many numbers must be selected from the set {−1,−2,−3,−4,−5,−6,1,2,3,4,5,6}\{-1, -2, -3, -4, -5, -6,1, 2, 3, 4, 5, 6\} to guarantee that at least one pair of these numbers add up to 0?

7.

Let QQ be the set of rational numbers and define a∗b=a+b−aba * b = a + b - ab

(a) Is (Q,∗)(Q, *) a monoid? Justify your answer.

(b) If (Q,∗)(Q, *) a monoid, which elements of QQ have an inverse?

(c) Is (Q,∗)(Q, *) a group? Justify your answer.

8.

Consider the monoid S={e,a,b,c}S = \{e, a, b, c\} with the following operation table.

*eabc
eeabc
aaebc
bbcbc
ccbbc

Consider the congruence relation R={(e,a),(a,e),(e,e),(a,a),(b,c),(b,b),(c,b),(c,c)}R = \{(e, a), (a, e), (e, e), (a, a), (b, c), (b, b), (c, b), (c, c)\} on SS.

(a) Write the operation table of the quotient monoid S/RS/R.

(b) Describe the natural homomorphism fR:S→S/Rf_R: S \to S/R and give your reason.

9.

Consider the group (Z6,+6)(\mathbb{Z}_6, +_6).

(a) Write the operation table of the group (Z6,+6)(\mathbb{Z}_6, +_6).

(b) Consider the subgroup H={[0],[3]}H = \{[0], [3]\}. Describe the left cosets and right cosets of HH in Z6\mathbb{Z}_6.

(c) Write the operation table of the quotient group Z6/H\mathbb{Z}_6 / H.

(d) Determine whether the group (Z2×Z3,⊕)(\mathbb{Z}_2 \times \mathbb{Z}_3, \oplus) and (Z6,+6)(\mathbb{Z}_6, +_6) are isomorphic.

10.

Let GG be a group, and let HH and KK be the subgroups of GG. Let the relation RR on GG be defined as follows:

aRbaRb if and only if ∃h∈H,∃k∈K,b=hak\exists h \in H, \exists k \in K, b = hak

Show that RR is an equivalence relation.