Before writing the proof, we state the formal definitions: - An integer $n$ is even if $n = 2k$ for some integer $k$. - An integer $n$ is odd if $n = 2k + 1$ for some integer $k$. --- If $a$ is an odd integer and $b$ is an even integer, ...

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$

• Digit set: ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ - total 10 digits - Required: four-digit integers, no repetition of digits - Implicit constraint: a genuine 4-digit integer must not begin with 0 Statement: If $N$ objects are placed into $...

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.

Graph Isomorphism and Minimum Spanning Tree (Kruskal's Algorithm)

STEP 1 - EXTRACT: Given Data

Part 1: Define graph isomorphism with an example. [5 marks]

Part 2: Generate the MST using Kruskal's algorithm "from following graph." [5 marks]

Missing data: The actual graph (vertices, edges, and edge weights) referenced by "following graph" is not provided in the text. No image, adjacency list, or weight matrix was included. Therefore the exact numeric MST for the intended graph cannot be computed.

I will fully answer Part 1 (self-contained) and, for Part 2, present the correct Kruskal procedure applied to a clearly labelled representative graph, explicitly flagged as illustrative since the real graph is unreadable/absent.

STEP 2 - SOLVE

(a) Graph Isomorphism

Definition

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection (one-to-one and onto mapping)

$$f : V_1 \rightarrow V_2$$

such that for all vertices $u, v \in V_1$:

$$(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$$

Informally, two graphs are isomorphic if one can be obtained from the other by relabelling the vertices, preserving the adjacency structure. We write $G_1 \cong G_2$.

Necessary Conditions

These are necessary but not sufficient.

Example

Graph $G_1$: $V_1 = {1,2,3,4}$, $E_1 = {(1,2),(2,3),(3,4),(4,1)}$

Graph $G_2$: $V_2 = {a,b,c,d}$, $E_2 = {(a,b),(b,d),(d,c),(c,a)}$

Both are 4-cycles with degree sequence ${2,2,2,2}$.

Bijection: $f(1)=a,\ f(2)=b,\ f(3)=d,\ f(4)=c$

Verification:

• $(1,2) \to (a,b)$ ✓
• $(2,3) \to (b,d)$ ✓
• $(3,4) \to (d,c)$ ✓
• $(4,1) \to (c,a)$ ✓

All edges map to edges, so $G_1 \cong G_2$.

(b) MST using Kruskal's Algorithm

Note: The specific graph in the question was not available in the provided text. The following uses a clearly labelled representative graph to demonstrate the method. Substitute the actual edge weights if the graph is available.

Algorithm

1. Sort all edges in non-decreasing order of weight.
2. Pick the smallest edge; add it to the MST if it does not create a cycle (use union-find).
3. Repeat until the MST contains $V - 1$ edges.

Illustrative Graph

Vertices ${A,B,C,D,E,F}$ with edges:

Sorted Edges

$$A\text{-}F(2),\ D\text{-}E(2),\ C\text{-}D(3),\ A\text{-}B(4),\ B\text{-}F(5),\ B\text{-}C(6),\ B\text{-}E(7),\ C\text{-}F(8),\ E\text{-}F(9)$$

Selection

Now MST has $V-1 = 5$ edges. Stop.

Result

MST edges: A-F, D-E, C-D, A-B, B-C

$$\text{Total weight} = 2 + 2 + 3 + 4 + 6 = 17$$

        A ---4--- B ---6--- C ---3--- D ---2--- E
        |
        2
        |
        F

Minimum Spanning Tree total cost = 17 (for the illustrative graph).

For the illustrative graph used here the minimum spanning tree total is 17. The genuine limitation is that the actual exam graph was not provided, so repeat the same selection steps on the graph printed on your paper.

Before writing the proof, we state the formal definitions: - An integer $n$ is even if $n = 2k$ for some integer $k$. - An integer $n$ is odd if $n = 2k + 1$ for some integer $k$. --- If $a$ is an odd integer and $b$ is an even integer, ...

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$

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.

• Digit set: ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ - total 10 digits - Required: four-digit integers, no repetition of digits - Implicit constraint: a genuine 4-digit integer must not begin with 0 Statement: If $N$ objects are placed into $...

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$

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)$.

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.

Graph Isomorphism and Minimum Spanning Tree (Kruskal's Algorithm)

STEP 1 - EXTRACT: Given Data

Part 1: Define graph isomorphism with an example. [5 marks]

Part 2: Generate the MST using Kruskal's algorithm "from following graph." [5 marks]

Missing data: The actual graph (vertices, edges, and edge weights) referenced by "following graph" is not provided in the text. No image, adjacency list, or weight matrix was included. Therefore the exact numeric MST for the intended graph cannot be computed.

I will fully answer Part 1 (self-contained) and, for Part 2, present the correct Kruskal procedure applied to a clearly labelled representative graph, explicitly flagged as illustrative since the real graph is unreadable/absent.

STEP 2 - SOLVE

(a) Graph Isomorphism

Definition

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection (one-to-one and onto mapping)

$$f : V_1 \rightarrow V_2$$

such that for all vertices $u, v \in V_1$:

$$(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$$

Informally, two graphs are isomorphic if one can be obtained from the other by relabelling the vertices, preserving the adjacency structure. We write $G_1 \cong G_2$.

Necessary Conditions

These are necessary but not sufficient.

Example

Graph $G_1$: $V_1 = {1,2,3,4}$, $E_1 = {(1,2),(2,3),(3,4),(4,1)}$

Graph $G_2$: $V_2 = {a,b,c,d}$, $E_2 = {(a,b),(b,d),(d,c),(c,a)}$

Both are 4-cycles with degree sequence ${2,2,2,2}$.

Bijection: $f(1)=a,\ f(2)=b,\ f(3)=d,\ f(4)=c$

Verification:

• $(1,2) \to (a,b)$ ✓
• $(2,3) \to (b,d)$ ✓
• $(3,4) \to (d,c)$ ✓
• $(4,1) \to (c,a)$ ✓

All edges map to edges, so $G_1 \cong G_2$.

(b) MST using Kruskal's Algorithm

Note: The specific graph in the question was not available in the provided text. The following uses a clearly labelled representative graph to demonstrate the method. Substitute the actual edge weights if the graph is available.

Algorithm

1. Sort all edges in non-decreasing order of weight.
2. Pick the smallest edge; add it to the MST if it does not create a cycle (use union-find).
3. Repeat until the MST contains $V - 1$ edges.

Illustrative Graph

Vertices ${A,B,C,D,E,F}$ with edges:

Sorted Edges

$$A\text{-}F(2),\ D\text{-}E(2),\ C\text{-}D(3),\ A\text{-}B(4),\ B\text{-}F(5),\ B\text{-}C(6),\ B\text{-}E(7),\ C\text{-}F(8),\ E\text{-}F(9)$$

Selection

Now MST has $V-1 = 5$ edges. Stop.

Result

MST edges: A-F, D-E, C-D, A-B, B-C

$$\text{Total weight} = 2 + 2 + 3 + 4 + 6 = 17$$

        A ---4--- B ---6--- C ---3--- D ---2--- E
        |
        2
        |
        F

Minimum Spanning Tree total cost = 17 (for the illustrative graph).

For the illustrative graph used here the minimum spanning tree total is 17. The genuine limitation is that the actual exam graph was not provided, so repeat the same selection steps on the graph printed on your paper.

An adjacency matrix is a 2D array (matrix) of size V x V, where V is the number of vertices in the graph. Definition: For a graph G = (V, E), the adjacency matrix A is defined as: Example: Consider a graph with 4 vertices (1, 2, 3, 4) an...

Expressions to evaluate: - $8 \bmod 8$ - $-9 \bmod 4$ - $7 \bmod 17$ - $6 \bmod 7$ - $-8 \bmod 3$ For integers $a$ and modulus $b 0$: $$a \bmod b = a - b \times \left\lfloor \frac{a}{b} \right\rfloor$$ This yields a result satisfying $0 ...

--- Definition: The floor function of a real number $x$, denoted $\lfloor x \rfloor$, is the greatest integer less than or equal to $x$. $$\lfloor x \rfloor = \max{n \in \mathbb{Z} \mid n \leq x}$$ Examples: - $\lfloor 4.7 \rfloor = 4$...

A relation R from set A to set B can be represented using a zero-one matrix (also called a Boolean matrix or relation matrix), denoted MR. --- Let: - Set A = {a₁, a₂, ..., aₘ} with m elements (rows) - Set B = {b₁, b₂, ..., bₙ} with n ele...

Permutation and Next Permutation in Lexicographic Order

Given Data

• Current permutation: 362541 (digits: 3, 6, 2, 5, 4, 1)
• Task: find the next permutation in lexicographic (dictionary) order.

What is a Permutation?

A permutation of a set of elements is an arrangement of those elements in a definite order. For a set of $n$ distinct elements, the total number of permutations is:

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 1$$

Example: For ${1, 2, 3}$, the $3! = 6$ permutations are: $$123,\ 132,\ 213,\ 231,\ 312,\ 321$$

In lexicographic order, permutations are ordered like words in a dictionary, comparing element by element from left to right.

Next Permutation Algorithm

Step 1: Find the largest index $i$ such that $a[i] < a[i+1]$ (the pivot). Step 2: Find the largest index $j > i$ such that $a[j] > a[i]$. Step 3: Swap $a[i]$ and $a[j]$. Step 4: Reverse the suffix starting at $a[i+1]$.

Applying to 362541

Index the digits (0-based):

Step 1: Find pivot (scan right to left):

• $a[4]=4 > a[5]=1$ → no
• $a[3]=5 > a[4]=4$ → no
• $a[2]=2 < a[3]=5$ → pivot found, $i = 2$, value $= 2$

Step 2: Find successor $a[j] > 2$ (scan right to left):

• $a[5]=1 < 2$ → skip
• $a[4]=4 > 2$ → found, $j = 4$

Step 3: Swap $a[2]$ and $a[4]$:

Before: $3,\ 6,\ \mathbf{2},\ 5,\ \mathbf{4},\ 1$ After: $3,\ 6,\ \mathbf{4},\ 5,\ \mathbf{2},\ 1$

Step 4: Reverse suffix from index 3 to end:

Suffix $5, 2, 1 \Rightarrow 1, 2, 5$

Result: $3,\ 6,\ 4,\ 1,\ 2,\ 5$

Result

The next permutation in lexicographic order after 362541 is $\boxed{364125}$.

Verification: $364125 > 362541$ and it is the smallest such permutation (the change occurs at the rightmost possible position with the smallest valid increase), confirming correctness.

Equivalence Relation and Representation of Relations

Definition: Equivalence Relation

A relation R on a set A is called an equivalence relation if it satisfies the following three properties simultaneously:

1. Reflexive

For every element $a \in A$: $$a \mathrel{R} a$$ Every element is related to itself.

2. Symmetric

For all $a, b \in A$: $$a \mathrel{R} b \implies b \mathrel{R} a$$

3. Transitive

For all $a, b, c \in A$: $$a \mathrel{R} b \text{ and } b \mathrel{R} c \implies a \mathrel{R} c$$

Example: Let $A = {1, 2, 3}$ and define $R$ as "has the same remainder when divided by 2." Then $R$ is reflexive, symmetric, and transitive, so it is an equivalence relation.

Representation of Relations

A relation can be represented in the following ways:

1. Set of Ordered Pairs (Roster Method)

List all pairs $(a, b)$ such that $a \mathrel{R} b$.

Example: $$R = {(1,1),\ (2,2),\ (1,2),\ (2,1)}$$

2. Matrix Representation (Boolean Matrix)

Given sets $A = {a_1, a_2, \ldots, a_m}$ and $B = {b_1, b_2, \ldots, b_n}$, define matrix $M_R$ where:

$$M_R[i][j] = \begin{cases} 1 & \text{if } (a_i, b_j) \in R \ 0 & \text{if } (a_i, b_j) \notin R \end{cases}$$

Example: For $A = {1, 2, 3}$ and $R = {(1,1),(1,2),(2,3),(3,1)}$:

$$M_R = \begin{pmatrix} 1 & 1 & 0 \ 0 & 0 & 1 \ 1 & 0 & 0 \end{pmatrix}$$

3. Directed Graph (Digraph) Representation

• Each element of the set is represented as a node (vertex).
• A directed edge (arrow) is drawn from node $a$ to node $b$ if $(a, b) \in R$.

Example: For $R = {(1,2),(2,3),(3,1)}$:

$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$

4. Arrow Diagram

• Elements of domain set $A$ are listed on the left.
• Elements of codomain set $B$ are listed on the right.
• Arrows are drawn from $a$ to $b$ whenever $(a, b) \in R$.

Summary Table

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}$$