RankRizz
JEE MAIN 2025 · 02 APR S2+4 / −1HARDTRANSCRIBED

JEE Main 2025 Mathematics question — Cartesian products and counting relations

Let A={1,2,3,…,100}A = \{1, 2, 3, \ldots, 100\} and R be a relation on A such that R={(a,b):a=2b+1}R = \{(a, b) : a = 2b + 1\}. Let (a1,a2),(a2,a3),(a3,a4),…,(ak,ak+1)(a_1, a_2), (a_2, a_3), (a_3, a_4), \ldots, (a_k, a_{k+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 :

SOLUTION

We are given A={1,2,3,…,100}A = \{1, 2, 3, \ldots, 100\} and the relation R={(a,b):a=2b+1}R = \{(a, b) : a = 2b + 1\} on AA.

Step 1: Identify all ordered pairs in R

For (a,b)∈R(a, b) \in R, we need a=2b+1a = 2b + 1 where both aa and bb are in AA.

Since a=2b+1a = 2b + 1, aa must be odd. The valid pairs are:

(3,1),(5,2),(7,3),(9,4),(11,5),(13,6),…,(99,49)(3, 1), (5, 2), (7, 3), (9, 4), (11, 5), (13, 6), \ldots, (99, 49)

That is, for each bb from 11 to 4949, we get the pair (2b+1,b)(2b+1, b).

Step 2: Understand the chain condition

We need a sequence (a1,a2),(a2,a3),(a3,a4),…,(ak,ak+1)(a_1, a_2), (a_2, a_3), (a_3, a_4), \ldots, (a_k, a_{k+1}) of kk elements of RR such that the second entry of each pair equals the first entry of the next pair.

This means: a1=2a2+1a_1 = 2a_2 + 1, a2=2a3+1a_2 = 2a_3 + 1, a3=2a4+1a_3 = 2a_4 + 1, and so on.

Step 3: Express a1a_1 in terms of ak+1a_{k+1}

From the recurrence ai=2ai+1+1a_i = 2a_{i+1} + 1, we can write:

a1=2a2+1=2(2a3+1)+1=4a3+3a_1 = 2a_2 + 1 = 2(2a_3 + 1) + 1 = 4a_3 + 3

a1=4(2a4+1)+3=8a4+7a_1 = 4(2a_4 + 1) + 3 = 8a_4 + 7

In general: a1=2k⋅ak+1+(2k−1)a_1 = 2^k \cdot a_{k+1} + (2^k - 1)

Step 4: Find the maximum kk

We need a1≤100a_1 \leq 100 and ak+1≥1a_{k+1} \geq 1.

Setting ak+1=1a_{k+1} = 1 (the smallest possible value):

a1=2k⋅1+(2k−1)=2k+1−1a_1 = 2^k \cdot 1 + (2^k - 1) = 2^{k+1} - 1

We need 2k+1−1≤1002^{k+1} - 1 \leq 100, so 2k+1≤1012^{k+1} \leq 101.

Checking: 26=64≤1012^6 = 64 \leq 101 ✓ and 27=128>1012^7 = 128 \gt 101 ✗

So k+1≤6k + 1 \leq 6, which gives k≤5k \leq 5.

Step 5: Verify with k=5k = 5

With k=5k = 5 and a6=1a_6 = 1:

a6=1,a5=2(1)+1=3,a4=2(3)+1=7a_6 = 1, \quad a_5 = 2(1) + 1 = 3, \quad a_4 = 2(3) + 1 = 7

a3=2(7)+1=15,a2=2(15)+1=31,a1=2(31)+1=63a_3 = 2(7) + 1 = 15, \quad a_2 = 2(15) + 1 = 31, \quad a_1 = 2(31) + 1 = 63

The chain is: (63,31),(31,15),(15,7),(7,3),(3,1)(63, 31), (31, 15), (15, 7), (7, 3), (3, 1)

All values are in A={1,2,…,100}A = \{1, 2, \ldots, 100\} ✓

Therefore, the largest integer kk is 5\mathbf{5}.

Hence, the correct answer is Option C.

Tagged Cartesian products and counting relations. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicCartesian products and counting relations
TypeMultiple choice