Let A = 1,2,3,,100 and R be a relation on A such that R = (a,b) : a=2b+1.

Question

Let $A = \{1,2,3,\ldots,100\}$ and $R$ be a relation on $A$ such that $R = \{(a,b) : a=2b+1\}$. Let $(a_1,a_2),(a_2,a_3),(a_3,a_4),\ldots,(a_k,a_{k+1})$ be a sequence of elements of $R$ such that the second entry of an ordered pair equals the first entry of the next ordered pair. Then the largest integer $k$ for which such a sequence exists, is equal to:

Accepted Answer

Each $a_i = 2a_{i+1}+1$. Unrolling the recursion:
$a_1 = 2^k a_{k+1} + (2^k-1)$
For $a_{k+1}\in A$ to be a positive integer, $2^k$ must divide $(a_1+1)$, with $a_1 \leq 100$ (so $a_1+1\leq101$).

The largest power of 2 that can divide some $(a_1+1)\leq101$ while keeping $a_{k+1}\geq1$ works out to $2^5=32$ (giving $k=5$), realized by the concrete chain:
$(95,47),(47,23),(23,11),(11,5),(5,2)$
Here $a_1=95$: $95=2\cdot47+1$, $47=2\cdot23+1$, $23=2\cdot11+1$, $11=2\cdot5+1$, $5=2\cdot2+1$ --- a valid chain of length $k=5$, and this is the maximum achievable.

Solutions · 1