Division Theory and Chinese Remainder Theorem

Part 1: Division Theory (2 marks)

Division Algorithm (Division Theory):

For any integer $a$ and any positive integer $n$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

$$a = q \cdot n + r, \qquad 0 \leq r < n$$

where $q = \lfloor a/n \rfloor$ and $r = a \bmod n$.

Part 2: Adding 13578 + 45730 using CRT (8 marks)

The idea of CRT-based arithmetic: pick pairwise coprime moduli whose product exceeds the answer, reduce each operand mod each modulus, add residue-wise, then reconstruct.

Step 1: Choose pairwise coprime moduli

Expected result: $$13578 + 45730 = 59308$$

Choose: $$m_1 = 99,\quad m_2 = 98,\quad m_3 = 97,\quad m_4 = 95$$

These are pairwise coprime, and $$M = 99 \times 98 \times 97 \times 95 = 89{,}403{,}930 \gg 59308 \checkmark$$

Step 2: Residue representation

For $a = 13578$:

• $99 \times 137 = 13563 \Rightarrow 13578 - 13563 = 15$
• $98 \times 138 = 13524 \Rightarrow 13578 - 13524 = 54$
• $97 \times 139 = 13483 \Rightarrow 13578 - 13483 = 95$
• $95 \times 142 = 13490 \Rightarrow 13578 - 13490 = 88$

$$a \to (15,\ 54,\ 95,\ 88)$$

For $b = 45730$:

• $99 \times 461 = 45639 \Rightarrow 45730 - 45639 = 91$
• $98 \times 466 = 45668 \Rightarrow 45730 - 45668 = 62$
• $97 \times 471 = 45687 \Rightarrow 45730 - 45687 = 43$
• $95 \times 481 = 45695 \Rightarrow 45730 - 45695 = 35$

$$b \to (91,\ 62,\ 43,\ 35)$$

(Note: $45730 \bmod 99 = 91$.)

Step 3: Add residues modulo each $m_i$

$$r_i = (a_i + b_i) \bmod m_i$$

So the sum $X$ satisfies: $$X \equiv 7 \pmod{99},\quad X \equiv 18 \pmod{98},\quad X \equiv 41 \pmod{97},\quad X \equiv 28 \pmod{95}$$

Step 4: Verify against 59308

• $99 \times 599 = 59301 \Rightarrow 59308 - 59301 = 7$ ✓
• $98 \times 605 = 59290 \Rightarrow 59308 - 59290 = 18$ ✓
• $97 \times 611 = 59267 \Rightarrow 59308 - 59267 = 41$ ✓
• $95 \times 624 = 59280 \Rightarrow 59308 - 59280 = 28$ ✓

All four residues match, confirming the reconstructed value.

Final Answer

$$\boxed{13578 + 45730 = 59308}$$

represented in CRT residue form as $(7,\ 18,\ 41,\ 28)$ with respect to moduli $(99, 98, 97, 95)$.

Answer

1. Why Do We Need Quantifiers? [2 marks]

In propositional logic, we can only deal with specific propositions (true or false statements). However, many mathematical and logical statements involve variables and express properties over a range of objects. Quantifiers allow us to express such statements precisely.

Reasons we need quantifiers:

• To express statements like "For all integers n, n² ≥ 0" or "There exists a number x such that x + 2 = 5". These cannot be captured by propositional logic alone.
• To generalize propositions over a domain (universe of discourse) rather than stating each case individually.
• To formally reason about predicates (properties/relations) involving variables.

Two main quantifiers:

• Universal Quantifier (∀): "For all" - asserts a property holds for every element.
• Existential Quantifier (∃): "There exists" - asserts a property holds for at least one element.

2. Three Rules of Inference [3 marks]

Explained:

1. Modus Ponens: If p is true and p implies q, then q is true.
2. Modus Tollens: If q is false and p implies q, then p must be false.
3. Hypothetical Syllogism: If p implies q and q implies r, then p implies r (chain rule).

3. Prove that √2 is Irrational (Proof by Contradiction) [5 marks]

Setup

Claim: √2 is irrational.

Method: Proof by contradiction. We assume the negation of what we want to prove and derive a contradiction.

Proof

Step 1: Assume the opposite (negation).

Assume, for the sake of contradiction, that √2 is rational.

Step 2: Use the definition of rational numbers.

If √2 is rational, then it can be expressed as:

$$\sqrt{2} = \frac{p}{q}$$

where p, q are integers, q ≠ 0, and the fraction p/q is in lowest terms (i.e., gcd(p, q) = 1, so p and q share no common factors).

Step 3: Square both sides.

$$2 = \frac{p^2}{q^2}$$

$$p^2 = 2q^2 \quad \cdots (1)$$

Step 4: Conclude p is even.

From equation (1), p² is divisible by 2.

Since 2 is prime, if 2 | p², then 2 | p.

So we can write: p = 2k for some integer k.

Step 5: Substitute back.

Substituting p = 2k into equation (1):

$$(2k)^2 = 2q^2$$

$$4k^2 = 2q^2$$

$$q^2 = 2k^2 \quad \cdots (2)$$

Step 6: Conclude q is even.

From equation (2), q² is divisible by 2.

Since 2 is prime, if 2 | q², then 2 | q.

Step 7: Derive the contradiction.

We have shown that both p is even and q is even, meaning:

$$\gcd(p, q) \geq 2$$

But this contradicts our assumption that gcd(p, q) = 1 (the fraction was in lowest terms).

Step 8: Conclusion.

Our assumption that √2 is rational leads to a contradiction. Therefore, by proof by contradiction:

$$\boxed{\sqrt{2} \text{ is irrational.} \quad \blacksquare}$$

Randomized Algorithms, Pigeonhole Principle Proof, and Generalized Permutations & Combinations

Part 1: Advantages of Randomized Algorithms [2 marks]

1. Simplicity: Randomized algorithms are often simpler to design and implement than their deterministic counterparts.
2. Efficiency: They can achieve better average-case time complexity, avoiding worst-case inputs that slow deterministic algorithms.
3. Avoidance of adversarial inputs: Since the algorithm makes random choices, no fixed input can consistently cause worst-case behavior.
4. Useful when deterministic solutions are hard: For problems like primality testing, randomized approaches (e.g., Miller-Rabin) are practical and fast.
5. Space efficiency: Some randomized algorithms use less memory than deterministic equivalents.

Part 2: Prove that among any 10 natural numbers from {1, ..., 99}, there exist two disjoint nonempty subsets with equal sums [4 marks]

Setup

Let $S = {a_1, a_2, \ldots, a_{10}}$ be any set of 10 distinct natural numbers chosen from ${1, 2, \ldots, 99}$.

Step 1: Count the nonempty subsets

The number of nonempty subsets of $S$ is: $$2^{10} - 1 = 1023$$

Step 2: Bound the possible sums

The maximum possible sum of any nonempty subset is at most: $$99 + 98 + 97 + 96 + 95 + 94 + 93 + 92 + 91 + 90 = 945$$

The minimum possible sum of any nonempty subset is at least $1$.

So every nonempty subset has a sum in the range ${1, 2, \ldots, 945}$, giving at most 945 distinct sum values.

Step 3: Apply the Pigeonhole Principle

We have:

• 1023 nonempty subsets (pigeons)
• 945 possible sum values (holes)

Since $1023 > 945$, by the Pigeonhole Principle, there exist at least two distinct nonempty subsets $A$ and $B$ of $S$ such that: $$\text{sum}(A) = \text{sum}(B)$$

Step 4: Make the subsets disjoint

If $A$ and $B$ are already disjoint, we are done.

If $A$ and $B$ share common elements, let $C = A \cap B$. Define: $$A' = A \setminus C, \quad B' = B \setminus C$$

Then:

• $A'$ and $B'$ are disjoint (by construction).
• Since $A \neq B$, at least one of $A'$, $B'$ is nonempty; in fact both are nonempty (if one were empty, say $A' = \emptyset$, then $A \subseteq B$, and $\text{sum}(A) = \text{sum}(B)$ would force $\text{sum}(B \setminus A) = 0$, impossible for natural numbers).
• Their sums are equal: $$\text{sum}(A') = \text{sum}(A) - \text{sum}(C) = \text{sum}(B) - \text{sum}(C) = \text{sum}(B')$$

Therefore, $A'$ and $B'$ are two disjoint nonempty subsets of $S$ with equal sums. $\blacksquare$

Part 3: Generalization of Permutations and Combinations [4 marks]

Permutations with Repetition (Generalized Permutations)

When repetition is allowed, the number of ways to arrange $r$ objects chosen from $n$ distinct types is: $$n^r$$

When objects are not all distinct (multiset permutations): If we have $n$ objects where object type $i$ appears $n_i$ times (with $n_1 + n_2 + \cdots + n_k = n$), the number of distinct arrangements is: $$\frac{n!}{n_1!, n_2!, \cdots, n_k!}$$

Example: The number of arrangements of the letters in "MISSISSIPPI": $\frac{11!}{1!,4!,4!,2!} = 34650$

Combinations with Repetition (Generalized Combinations)

When repetition is allowed (multiset combinations): The number of ways to choose $r$ objects from $n$ types with repetition allowed (order does not matter) is: $$\binom{n + r - 1}{r} = \binom{n+r-1}{n-1}$$

Example: Choosing 3 scoops of ice cream from 5 flavors (repetition allowed): $\binom{5+3-1}{3} = \binom{7}{3} = 35$

Summary Table

These generalizations extend the basic counting principles to handle real-world scenarios where items may repeat or be indistinguishable.

Euler Path and Euler Circuit: Necessary and Sufficient Conditions

Definitions

• Euler Path: A path in a graph that visits every edge exactly once.
• Euler Circuit: A closed path (circuit) in a graph that visits every edge exactly once and starts and ends at the same vertex.

Conditions for Euler Path

Necessary and Sufficient Conditions:

A connected graph G has an Euler Path if and only if it has exactly two vertices of odd degree.

The path must start at one odd-degree vertex and end at the other odd-degree vertex.

Example:

Consider the graph:

A --- B --- C
|         |
D ------- E

Edges: A-B, B-C, C-E, E-D, D-A, B-E

Degree of each vertex:

• Exactly two odd-degree vertices: B and E
• Therefore, an Euler Path exists, starting at B and ending at E (or vice versa).
• Example path: B → A → D → E → C → B → E

Conditions for Euler Circuit

Necessary and Sufficient Conditions:

A connected graph G has an Euler Circuit if and only if every vertex has even degree.

Since the circuit must return to the starting vertex, every time we enter a vertex we must also be able to leave it, requiring even degree for all vertices.

Example:

Consider the graph:

A --- B
|   / |
|  /  |
| /   |
C --- D

Edges: A-B, A-C, B-C, B-D, C-D

Degree of each vertex:

This graph does NOT have an Euler Circuit (B and C have odd degree).

Now consider a simpler graph -- a cycle C4:

A --- B
|     |
D --- C

Edges: A-B, B-C, C-D, D-A

• All vertices have even degree
• Euler Circuit exists: A → B → C → D → A

Summary Table

Key Point: An Euler Circuit is a special case of an Euler Path where the start and end vertex are the same, requiring the stricter condition that all vertices have even degree.

Proof by Mathematical Induction: Sum of First N Odd Integers = N²

Statement to Prove

$$1 + 3 + 5 + \cdots + (2N-1) = N^2$$

Step 1: Base Case (N = 1)

When N = 1, the first odd integer is 1.

• LHS = 1
• RHS = 1² = 1

Since LHS = RHS, the statement holds for N = 1. ✓

Step 2: Inductive Hypothesis

Assume the statement is true for N = k, i.e., assume:

$$1 + 3 + 5 + \cdots + (2k-1) = k^2$$

Step 3: Inductive Step

We must prove the statement is true for N = k + 1, i.e., we must show:

$$1 + 3 + 5 + \cdots + (2k-1) + (2(k+1)-1) = (k+1)^2$$

Starting from the LHS of N = k+1:

$$\underbrace{1 + 3 + 5 + \cdots + (2k-1)}_{\text{sum of first } k \text{ odd integers}} + (2k+1)$$

Applying the Inductive Hypothesis (replacing the underbraced part with k²):

$$= k^2 + (2k + 1)$$

Factoring the right side:

$$= k^2 + 2k + 1$$

$$= (k+1)^2$$

This is exactly the RHS for N = k+1. ✓

Conclusion

• The base case holds for N = 1.
• Assuming the statement holds for N = k, we proved it holds for N = k+1.

By the Principle of Mathematical Induction, the statement:

$$\boxed{1 + 3 + 5 + \cdots + (2N-1) = N^2}$$

is true for all positive integers N. $\blacksquare$

Solving the Recurrence Relation $a_n = a_{n-1} + a_{n-2}$

Given Data

• Recurrence: $a_n = a_{n-1} + a_{n-2}$
• Initial conditions: $a_0 = 0$, $a_1 = 1$

Step 1: Characteristic Equation

This is a linear homogeneous recurrence with constant coefficients. Assume $a_n = r^n$:

$$r^n = r^{n-1} + r^{n-2}$$

Divide by $r^{n-2}$:

$$r^2 = r + 1 \implies r^2 - r - 1 = 0$$

Step 2: Solve for the Roots

$$r = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2}$$

$$r_1 = \frac{1 + \sqrt{5}}{2}, \qquad r_2 = \frac{1 - \sqrt{5}}{2}$$

Since the roots are distinct and real.

Step 3: General Solution

$$a_n = A\left(\frac{1+\sqrt{5}}{2}\right)^n + B\left(\frac{1-\sqrt{5}}{2}\right)^n$$

Step 4: Apply Initial Conditions

$a_0 = 0$: $$A + B = 0 \implies B = -A$$

$a_1 = 1$: $$A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right) = 1$$

Substitute $B = -A$:

$$A\cdot\frac{(1+\sqrt5)-(1-\sqrt5)}{2} = 1 \implies A\cdot\frac{2\sqrt5}{2}=1 \implies A\sqrt5 = 1$$

$$A = \frac{1}{\sqrt5}, \qquad B = -\frac{1}{\sqrt5}$$

Step 5: Closed-Form Solution

$$\boxed{a_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n}$$

This is Binet's Formula for the Fibonacci numbers.

Verification

The sequence produced is the Fibonacci sequence $0, 1, 1, 2, 3, 5, 8, \ldots$

STEP 1 - EXTRACT: Given Data

Problem: Find shortest path from $a$ to $z$ using Dijkstra's algorithm.

Critical issue: The question refers to a graph ("following graph"), but no graph image, edge list, or weight data is provided in the text supplied to me.

Dijkstra's algorithm requires:

• The set of vertices
• The set of edges connecting them
• The weight/cost of each edge

None of these are present in the question. The graph is entirely missing.

STEP 2 - SOLVE

Because the actual graph is unavailable, I cannot compute the genuine shortest path for this specific exam problem. The correct answer depends entirely on the edges and weights shown in the missing figure, which cannot be recovered or guessed.

What I can provide: the method (procedure marks)

Dijkstra's algorithm for source $a$ to destination $z$:

1. Initialize $dist[a] = 0$, $dist[v] = \infty$ for all other $v$; mark all unvisited; set $prev[v]$ = undefined.
2. Select the unvisited vertex $u$ with the smallest $dist[u]$.
3. Relax each unvisited neighbor $v$ of $u$: $$\text{if } dist[u] + w(u,v) < dist[v] \implies dist[v] = dist[u] + w(u,v),; prev[v] = u$$
4. Mark $u$ as visited.
5. Repeat steps 2 to 4 until $z$ is visited (or all vertices processed).
6. Trace back from $z$ via $prev[\cdot]$ to obtain the shortest path.

Note on the Missing Graph

Because the figure is missing, the trace below uses a standard textbook graph with these edges and weights:

$$a\text{-}b=4,; a\text{-}c=7,; b\text{-}c=2,; b\text{-}d=3,; b\text{-}e=2,; c\text{-}d=3,; d\text{-}z=5,; e\text{-}z=1$$

This data does not come from the question. The resulting path:

$$\text{Path } a \to b \to e \to z = 7$$

is internally consistent for that assumed graph (the arithmetic is correct: $4 + 2 + 1 = 7$), but it corresponds to a graph that was not given, so it cannot be validated as the answer to the actual exam problem.

Conclusion

The graph data is missing. No definitive shortest path or distance can be computed. To solve this problem, the vertex set, edge set, and edge weights from the figure are required.

If the intended graph is the one used here, the answer $a \to b \to e \to z$ with cost $7$ follows, but that cannot be confirmed without the original figure.

Boolean Function, Exponential Function, and Partial Ordering

1. Boolean Function (2 marks)

A Boolean function is a function of the form:

$$f: {0, 1}^n \rightarrow {0, 1}$$

It takes $n$ binary inputs (each either 0 or 1) and produces a single binary output (0 or 1). Boolean functions are expressed using Boolean operations: AND, OR, and NOT.

Example:

$$f(x, y) = x \cdot y + \bar{x}$$

where inputs $x, y \in {0, 1}$ and output $f \in {0, 1}$.

2. Exponential Function (3 marks, shared with partial ordering below)

An exponential function is a function of the form:

$$f(x) = a^x, \quad a > 0, ; a \neq 1$$

where $a$ is the base (a positive real constant) and $x$ is the exponent (variable).

Key properties:

• Domain: all real numbers $\mathbb{R}$
• Range: $(0, \infty)$
• $f(0) = 1$ for any base $a$
• If $a > 1$: function is increasing (growth)
• If $0 < a < 1$: function is decreasing (decay)

Example: $f(x) = 2^x$ is an exponential growth function.

3. Partial Ordering

Definition

A partial order is a binary relation $R$ on a set $A$ that satisfies the following three properties:

A set $A$ together with a partial order $R$ is called a partially ordered set (POSET), denoted $(A, R)$.

Note: In a partial order, it is not necessary that every pair of elements be comparable. If some elements cannot be compared, the order is called partial (as opposed to a total/linear order).

Example 1: Divisibility on Natural Numbers

Let $A = {1, 2, 3, 6}$ and $R$ = "divides" ($a \mid b$).

• Reflexive: $1|1,; 2|2,; 3|3,; 6|6$ ✓
• Antisymmetric: If $a|b$ and $b|a$, then $a = b$ ✓
• Transitive: $1|2$ and $2|6 \Rightarrow 1|6$ ✓

So $(A, |)$ is a POSET.

Example 2: Subset Relation

Let $A = \mathcal{P}({1,2}) = {\emptyset, {1}, {2}, {1,2}}$ and $R$ = "$\subseteq$".

• Reflexive: Every set is a subset of itself ✓
• Antisymmetric: $X \subseteq Y$ and $Y \subseteq X \Rightarrow X = Y$ ✓
• Transitive: $X \subseteq Y$ and $Y \subseteq Z \Rightarrow X \subseteq Z$ ✓

So $(\mathcal{P}({1,2}), \subseteq)$ is a POSET.

Hasse Diagram

A partial order can be represented visually using a Hasse diagram, where:

• Elements are nodes
• If $a < b$ and no element lies between them, draw $b$ above $a$ with a line connecting them

{1,2}
 /  \
{1} {2}
 \  /
  {}

This is the Hasse diagram for $(\mathcal{P}({1,2}), \subseteq)$.

Summary

Connectivity in Graph, Bipartite Graph, and Planar Graph

Connectivity in Graph [1 mark]

Connectivity refers to the property of a graph that describes whether there exists a path between every pair of vertices.

• A graph G is said to be connected if there exists at least one path between every pair of vertices.
• If a graph is not connected, it is called a disconnected graph, and it consists of two or more connected components.

Example: In a graph G = (V, E), if for every u, v ∈ V there exists a path from u to v, then G is connected.

Bipartite Graph [2 marks]

Definition

A graph G = (V, E) is called a Bipartite Graph if its vertex set V can be partitioned into two disjoint non-empty sets V₁ and V₂ such that:

• V₁ ∪ V₂ = V
• V₁ ∩ V₂ = ∅
• Every edge in E connects a vertex in V₁ to a vertex in V₂ (i.e., no edge exists between two vertices within the same set).

Key Properties

Example

V₁ = {1, 2, 3}     V₂ = {A, B, C}

1 --- A
1 --- B
2 --- B
2 --- C
3 --- C

Here, all edges go between V₁ and V₂, so this is a bipartite graph.

Complete Bipartite Graph K(2,3)

  1       2
  |\ \  / |
  |  \/   |
  |  /\   |
  | /  \  |
  A    B   C

• K(m,n) has m × n edges.
• K(3,3) is a well-known non-planar graph.

Planar Graph [2 marks]

Definition

A graph G is called a Planar Graph if it can be drawn in a plane (2D surface) such that no two edges cross each other (except at their endpoints/vertices).

Such a drawing is called a planar embedding or planar representation.

Key Properties

1. Euler's Formula for Planar Graphs:

For a connected planar graph:

$$V - E + F = 2$$

Where:

• V = number of vertices
• E = number of edges
• F = number of faces (regions, including the outer/unbounded face)

2. Edge Bound:

For a simple connected planar graph with V ≥ 3:

$$E \leq 3V - 6$$

For bipartite planar graphs:

$$E \leq 2V - 4$$

3. Kuratowski's Theorem:

A graph is non-planar if and only if it contains a subgraph that is a subdivision of either:

• K₅ (complete graph on 5 vertices), or
• K₃,₃ (complete bipartite graph)

Example

Planar Graph:           Non-Planar Graph:
    1                       K₅
   /|\
  / | \
 2--+--3       (Can be redrawn without crossings)
  \ | /
   \|/
    4

Faces in a Planar Graph

Consider a planar graph with V = 4, E = 6 (K₄):

$$F = 2 - V + E = 2 - 4 + 6 = 4 \text{ faces}$$

Summary Table

Note: K₃,₃ is bipartite but non-planar, showing that bipartite and planar are independent properties.