We are given A={1,2,3,…,100} and the relation R={(a,b):a=2b+1} on A.
Step 1: Identify all ordered pairs in R
For (a,b)∈R, we need a=2b+1 where both a and b are in A.
Since a=2b+1, a must be odd. The valid pairs are:
(3,1),(5,2),(7,3),(9,4),(11,5),(13,6),…,(99,49)
That is, for each b from 1 to 49, we get the pair (2b+1,b).
Step 2: Understand the chain condition
We need a sequence (a1,a2),(a2,a3),(a3,a4),…,(ak,ak+1) of k elements of R such that the second entry of each pair equals the first entry of the next pair.
This means: a1=2a2+1, a2=2a3+1, a3=2a4+1, and so on.
Step 3: Express a1 in terms of ak+1
From the recurrence ai=2ai+1+1, we can write:
a1=2a2+1=2(2a3+1)+1=4a3+3
a1=4(2a4+1)+3=8a4+7
In general: a1=2k⋅ak+1+(2k−1)
Step 4: Find the maximum k
We need a1≤100 and ak+1≥1.
Setting ak+1=1 (the smallest possible value):
a1=2k⋅1+(2k−1)=2k+1−1
We need 2k+1−1≤100, so 2k+1≤101.
Checking: 26=64≤101 ✓ and 27=128>101 ✗
So k+1≤6, which gives k≤5.
Step 5: Verify with k=5
With k=5 and a6=1:
a6=1,a5=2(1)+1=3,a4=2(3)+1=7
a3=2(7)+1=15,a2=2(15)+1=31,a1=2(31)+1=63
The chain is: (63,31),(31,15),(15,7),(7,3),(3,1)
All values are in A={1,2,…,100} ✓
Therefore, the largest integer k is 5.
Hence, the correct answer is Option C.