Relations and Functions · Question 17

Let A = \1, 2, 3, , 100\ and R be a relation on A such that R = \(a, b) : a = 2b + 1\. Let (a1, a2), (a2, a3), (a3, a4), , (ak, ak+1) be a sequence of k elements of R such that the second entry of an ordered pair is equal to the first entry of the next ordered pair. Then the largest integer k, for which such a sequence exists, is equal to :

1. 6
2. 8
3. 7
4. 5

Answer

(4) 5

Solution

(ai, ai+1) R ai = 2ai+1 + 1 ai + 1 = 2(ai+1 + 1)

a1 + 1 = 2k(ak+1 + 1)

ak+1 1 and a1 100: 2k(ak+1 + 1) 101

2k 2 101 2k+1 101 k + 1 6 k 5

k = 5 is possible: (63, 31), (31, 15), (15, 7), (7, 3), (3, 1)

largest k = 5

Answer: (4)