26-27-1-离散数学II-期中

1.(8分)

Find 1942mod  4119^{42} \mod 41.

2.(12分)

A box of candies, when grouped by 7, leaves 4 candies remaining. When grouped by 11, leaves 5 candies remaining. Find the smallest positive number of candies in this box.

3.(10分)

There are 7 students: 4 boys and 3 girls. Answer the following questions.

  1. How many ways are there to select a committee of 4 students with at least one girl?
  2. How many ways to arrange all 7 students in a row if the 3 girls must stand together as one block?

4.(6分)

We have unlimited red, yellow and blue balls. Answer the following questions.

  1. How many ordered arrangements of 4 balls can we make?
  2. How many unordered groups of 4 balls can we make?

5.(6分)

How many solutions does the equation x1+x2+x3≤10x_1 + x_2 + x_3 \le 10 have, where x1≥2x_1 \ge 2, x2x_2 and x3x_3 are nonnegative integers.

6.(8分)

Prove: If we pick 10 integers from the set {1,2,3,…,18}\{1, 2, 3, \ldots, 18\}, then there must exist two selected integers such that one divides the other.

7.(10分)

Let ∗* be a binary operation on a set AA. Suppose that for all a,b,c∈Aa, b, c \in A, the following properties hold:

a∗a=a,a∗b=b∗a,(a∗b)∗c=a∗(b∗c).\begin{aligned} a * a &= a, \\ a * b &= b * a, \\ (a * b) * c &= a * (b * c). \end{aligned}

Define a relation ≤\le on AA by a≤b⇔a∗b=aa \le b \Leftrightarrow a * b = a. Prove that the relation ≤\le has the following properties:

  1. Prove that ≤\le is reflexive.
  2. Prove that ≤\le is antisymmetric.
  3. Prove that ≤\le is transitive.

8.(10分)

Let A={0,1}A = \{0, 1\} and A∗A^{*} denote the set of all finite strings over AA, including the empty string ε\varepsilon. The operation on A∗A^{*} is string concatenation, denoted by ⋅\cdot. Let T={w∈A∗∣the number of 1s in w is even}T = \{w \in A^{*} \mid \text{the number of 1s in } w \text{ is even}\}.

  1. Prove that (A∗,⋅)(A^{*}, \cdot) is a monoid, and identify its identity element.
  2. Prove that (T,⋅)(T, \cdot) is a submonoid of (A∗,⋅)(A^{*}, \cdot).
  3. Define the mapping f ⁣:A∗→Z2f \colon A^{*} \to \mathbb{Z}_{2}, f(w)=[the number of 1s in w]2f(w) = [\text{the number of 1s in } w]_{2}. Prove that ff is a homomorphism from A∗A^{*} to Z2\mathbb{Z}_{2}.

9.(10分)

Let S={1,2,3,…}S = \{1, 2, 3, \ldots\} be the set of positive integers under the operation of ordinary addition. Define a relation RR on SS by a R ba \, R \, b if and only if a≡b(mod3)a \equiv b \pmod{3}. Answer the following questions:

  1. Prove that RR is a congruence relation on the semigroup (S,+)(S, +).
  2. Define an operation ⊕\oplus on S/RS/R by [a]⊕[b]=[a+b][a] \oplus [b] = [a + b]. Construct the operation table of the quotient semigroup (S/R,⊕)(S/R, \oplus).
  3. Prove that (S/R,⊕)(S/R, \oplus) is a semigroup.

10.(10分)

Let G=RG = \mathbb{R} - {0}\{0\}, and define a binary operation ∗* on GG by a∗b=ab/4a * b = ab/4.

  1. Prove that (G,∗)(G, *) is an Abelian group.
  2. Solve the equation x∗4=10x * 4 = 10 in GG.

11.(10分)

Let G=(Z24,+24)G = (\mathbb{Z}_{24}, +_{24}) be the additive group of integers modulo 24, and let H={[0],[8],[16]}H = \{[0], [8], [16]\}.

  1. Prove that HH is a subgroup of GG.
  2. Find the orders of GG and HH, that is, determine ∣G∣|G| and ∣H∣|H|.