Scribd
Upload
3 views3 pages

Discrete Math Solutions

The document provides detailed explanations of various concepts in discrete mathematics, including birthday probability using the pigeonhole principle, properties of integral domains, and examples of relations. It also covers invertible functions, truth tables, conditions for simple graph existence, perfect graphs, Euler and Hamiltonian circuits, normal subgroups, and equivalence relations. Each section includes definitions, calculations, and examples to illustrate the concepts.

Uploaded by

mkumar847104
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Discrete Math Solutions

The document provides detailed explanations of various concepts in discrete mathematics, including birthday probability using the pigeonhole principle, properties of integral domains, and examples of relations. It also covers invertible functions, truth tables, conditions for simple graph existence, perfect graphs, Euler and Hamiltonian circuits, normal subgroups, and equivalence relations. Each section includes definitions, calculations, and examples to illustrate the concepts.

Uploaded by

mkumar847104
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Discrete Mathematics Solutions

Step-by-Step Detailed Explanations

a) Birthday Probability (Pigeonhole Principle)

Problem: How many people among 200,000 are born at the same time (hour, minute,
second)?

1. Calculate total seconds in a day: 24 × 60 × 60 = 86,400 slots.

2. Apply the Generalized Pigeonhole Principle: At least ⌈N/k⌉ people share a slot, where N =
200,000 and k = 86,400.

3. Calculation: ⌈200,000 / 86,400⌉ = ⌈2.314⌉ = 3.

Result: At least 3 people share the exact same birth second.

b) Integral Domain

An Integral Domain is a commutative ring with identity (1 ≠ 0) that has no zero divisors.

• It is a commutative ring under addition and multiplication.


• It contains a multiplicative identity element.
• No Zero Divisors: If a ⋅ b = 0, then a = 0 or b = 0.

c) Relation Example

Goal: Reflexive but neither symmetric nor transitive.

Let set A = {1, 2, 3}. Relation R = {(1,1), (2,2), (3,3), (1,2), (2,3)}.

• Reflexive: Includes (1,1), (2,2), (3,3).


• Not Symmetric: Has (1,2) but lacks (2,1).
• Not Transitive: Has (1,2) and (2,3) but lacks (1,3).
d) Invertible Function

A function f: A → B is invertible if there exists g: B → A such that g(f(x)) = x and f(g(y)) = y. For a
function to be invertible, it must be Bijective (both one-to-one and onto).

e) Truth Table

Expression: (p ↔ q) ∧ (∼r)

p q r p↔q ∼r Result

T T T T F F

T T F T T T

T F T F F F

T F F F T F

F T T F F F

F T F F T F

F F T T F F

F F F T T T

f) Simple Graph Existence

Degrees: 1, 3, 4, 6, 7. Vertices: 6.

Impossible:

1. Handshaking Lemma: Sum of degrees (1+3+4+6+7 = 21) is odd. Sum must be even.
2. Vertex Limit: In a simple graph with 6 vertices, max degree is n-1 = 5. Degrees 6 and 7
are impossible.

g) Perfect Graph

A graph where for every induced subgraph H, the chromatic number equals the size of the
maximum clique: χ(H) = ω(H).
h) Euler vs Hamiltonian Circuit

Example: Butterfly Graph (two triangles sharing one vertex).

• Euler: Exists because all vertices have even degrees.


• Hamiltonian: Does not exist because the shared vertex must be visited twice to
complete the cycle, violating the rule.

i) Normal Subgroup

A subgroup H of G is normal (H ⊴ G) if it is invariant under conjugation: gHg-1 = H for all g ∈


G.

j) Equivalence Relation

A relation is an Equivalence Relation if it is Reflexive, Symmetric, and Transitive.

Example: Congruence modulo n on integers. a ≡ b (mod n) if n divides a - b.

Generated Solution Document

You might also like