 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability/2/b/iii/solution

R^{2} = {(a, c), (b, d)}

R^{3} = {(a, d)}

, and

R^{i} = \emptyset

for

i \geq 4

. For

k = 1

(a, b), (b, c) \in T

but

(a, c) \in / T

, so transitivity fails. For

k = 2

(a, c), (c, d) \in T

but

(a, d) \in / T

, so it still fails.

For

k = 3

T

consists of every pair in which the first endpoint precedes the second in

a, b, c, d

. Composing any two such pairs again gives such a pair, so

T

is transitive. Thus the smallest $k$ is $3$ ; this

T

R

 New to topics? Read the docs here!