TheCATExam
Sign in

CAT 2023 Slot 1 — QA Question 13

Miscellaneous ProgressionsEasy

A lab experiment measures the number of organisms at 8 am every day. Starting with 2 organisms on the first day, the number of organisms on any day is equal to 3 more than twice the number on the previous day. If the number of organisms on the nth day exceeds one million, then the lowest possible value of n is

Answer & solution

Answer: 19

Solution

Easy

The recurrence an=2an−1+3a_{n}=2a_{n-1}+3 is linear — adding a constant. Solve it in closed form (a clean trick: add 33 to both sides to expose a pure doubling), then find the smallest nn pushing the count past one million.

1

Set up the recurrence with a1=2a_1=2:

an=2an−1+3a_n=2a_{n-1}+3
2

Add 33 to both sides so the +3+3 folds into a geometric term:

an+3=2(an−1+3)⇒ an+3=(a1+3) 2 n−1=5⋅2 n−1⇒ an=5⋅2 n−1−3\begin{aligned} &a_n+3=2(a_{n-1}+3)\\ &\Rightarrow\ a_n+3=(a_1+3)\,2^{\,n-1}=5\cdot 2^{\,n-1}\\ &\Rightarrow\ a_n=5\cdot 2^{\,n-1}-3 \end{aligned}
3

Require an>1,000,000a_n>1{,}000{,}000:

5⋅2 n−1−3>106⇒ 2 n−1>106+35=200000.6\begin{aligned} &5\cdot 2^{\,n-1}-3>10^6\\ &\Rightarrow\ 2^{\,n-1}>\frac{10^6+3}{5}=200000.6 \end{aligned}
4

Smallest power of two above 200000.6200000.6:

217=131072 (too small),218=262144 (✓)⇒ n−1=18 ⇒ n=19\begin{aligned} &2^{17}=131072\ (\text{too small}),\quad 2^{18}=262144\ (\checkmark)\\ &\Rightarrow\ n-1=18\ \Rightarrow\ n=19 \end{aligned}
n=19n=\mathbf{19}
CAT 2023 Slot 1 QA Q13: A lab experiment measures the number of organisms at 8 am every day. Starting with 2 organisms on the first da — Solution | TheCATExam