CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 1 |
Twin primes are pairs of numbers p and p+2 such that both are primes—for instance, 5 and 7, 11 and 13, 41 and 43. The Twin Prime Conjecture says that there are infinitely many twin primes.
Let TwinPrime(n) be a predicate that is true if n and n+2 are twin primes. Which of the following formulas, interpreted over positive integers, expresses that there are only finitely many twin primes?
∀m. ∃n. m ≤ n and not(TwinPrime(n)) | |
∃m. ∀n. n ≤ m implies TwinPrime(n) | |
∀m. ∃n. n ≤ m and TwinPrime(n) | |
∃m. ∀n. TwinPrime(n) implies n ≤ m |
Question 1 Explanation:
This says that there is a bound, m, such that any twin prime is below m. In other words, that there only finitely many twin primes.
Question 2 |
A binary relation R ⊆ (S × S) is said to be Euclidean if for every a, b, c ∈ S, (a, b) ∈ R and (a, c) ∈ R implies (b, c) ∈ R. Which of the following statements is valid?
If R is Euclidean, (b, a) ∈ R and (c, a) ∈ R, then (b, c) ∈ R, for every a, b, c ∈ S. | |
If R is reflexive and Euclidean, (a, b) ∈ R implies (b, a) ∈ R, for every a, b ∈ S. | |
If R is Euclidean, (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for every a, b, c ∈ S. | |
None of the above. |
Question 2 Explanation:
(a) This option is not valid. Consider the set S = {d, e, a, b, c} and the relation R given below.
R = {(d, a), (e, a), (a, a), (a, b), (a, c), (b, b), (c, c), (b, c), (c, b)}
R is Euclidean but (a) is violated by {d, e, a}.
(b) This option is valid. Suppose R is reflexive. Then (a, a) ∈ R for every a. If (a, b) ∈ R, then by the definition of Euclidian, (b, a) ∈ R.
(c) This option is not valid. Consider the set S = {a, b, c} and the relation R given below.
R = {(a, b), (b, b), (b, c), (c, c)}
R is Euclidean but not transitive, since (a, c) 6∈ R.
(d) Since (b) is valid, this cannot be the correct answer.
R = {(d, a), (e, a), (a, a), (a, b), (a, c), (b, b), (c, c), (b, c), (c, b)}
R is Euclidean but (a) is violated by {d, e, a}.
(b) This option is valid. Suppose R is reflexive. Then (a, a) ∈ R for every a. If (a, b) ∈ R, then by the definition of Euclidian, (b, a) ∈ R.
(c) This option is not valid. Consider the set S = {a, b, c} and the relation R given below.
R = {(a, b), (b, b), (b, c), (c, c)}
R is Euclidean but not transitive, since (a, c) 6∈ R.
(d) Since (b) is valid, this cannot be the correct answer.
Question 3 |
Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured
edge or not an endpoint of any green coloured edge. If a graph G does not satisfy this property, which of the following statements about G are valid?
There is a red coloured edge. | |
Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge. | |
There is a vertex that is not an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. | |
(a) and (c). |
Question 3 Explanation:
Let r(x) denote the fact that the vertex x is the endpoint of a red coloured edge, and similarly for b(x) and g(x). The given property P can be expressed by the following formula.
∀x. [r(x) =⇒ b(x) ∨ ¬g(x)]
If a graph G does not satisfy the above property, then it means that there exists a vertex v satisfying
r(v) ∧ ¬b(v) ∧ g(v).
This is exactly what is stated in option (c).
Option (b) is not valid. Consider the graph G with vertex set V = {1, 2, 3} and (colored) edges given by
E = {((1, 2), red), ((1, 3), red), ((2, 3), green)}.
Vertex 3 witnesses the violation of the property P , but vertex 2 violates option (b).
Since (c) implies (a), (d) is the correct answer.
∀x. [r(x) =⇒ b(x) ∨ ¬g(x)]
If a graph G does not satisfy the above property, then it means that there exists a vertex v satisfying
r(v) ∧ ¬b(v) ∧ g(v).
This is exactly what is stated in option (c).
Option (b) is not valid. Consider the graph G with vertex set V = {1, 2, 3} and (colored) edges given by
E = {((1, 2), red), ((1, 3), red), ((2, 3), green)}.
Vertex 3 witnesses the violation of the property P , but vertex 2 violates option (b).
Since (c) implies (a), (d) is the correct answer.
Question 4 |
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable. The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:
Find a spanning tree with minimum number of edges. | |
Find a minimal colouring. | |
Find a minimum size vertex cover. | |
Find a maximum size independent set. |
Question 4 Explanation:
If we represent each slot by a colour, then a colouring of the graph is an assignment of courses to slots, such that courses with overlapping audiences are in different slots. A minimal colouring minimizes the number of slots needed.
There are 4 questions to complete.