سؤال ۱۷

گزینه (۱) درست است.

اگر عدد $k$ فرد باشد٬ آن‌گاه یکی از دو عدد $\lceil \frac{k}{2} \rceil$ و $\lfloor \frac{k}{2} \rfloor$ زوج و دیگری فرد می‌باشد. اگر عدد فرد را $\alpha$ و عدد زوج را $\beta$ در نظر بگیریم٬ چون دو عدد $\alpha$ و $\beta$ متوالی می‌باشند٬ بنابراین در شمردن $f(\beta)$ تمام اعداد تولید شده٬ در شمردن $f(\alpha)$ نیز به کار رفته‌اند. در این حالت می‌توان تساوی $f(k)=f(\alpha)+2$ را نتیجه گرفت چون در محاسبه $f(k)$ دو عدد $k$ و $\beta$ نسبت به اعداد تولید شده در محاسبه $f(\alpha)$ بیشتر می‌باشند.

اگر عدد $k$ زوج باشد٬ آن‌گاه دو عدد $\lceil \frac{k}{2} \rceil$ و $\lfloor \frac{k}{2} \rfloor$ باهم برابر می‌باشند که آن را $\theta$ می‌نامیم. در این حالت نیز باکمی دقت به تساوی $f(k)=f(\theta)+1$ خواهد رسید.

از طرف دیگر معلوم می‌شود که اگر عدد $k$ در بازه‌ی $[2^n,2^{n+1}-1]$ در نظر گرفته شود٬ آن‌گاه عدد $f(\alpha)$ و یا $\theta$ی تعریف شده در فوق٬ در بازه‌ی $[2^{n-1},2^n-1]$ قرار خواهد گرفت٬ به این معنا که اگر ماکزیمم مقدار $f$ در بازه‌ی $[2^{n-1},2^n-1]$ برابر$m$ باشد٬ آن‌گاه ماکزیمم مقدار $f$ در بازه $[2^n,2^{n+1}-1]$ برابر $m+2$ خواهد شد.

ماکزیمم مقدار در بازه‌ی $[4,7]$ برابر ۵ می‌باشد. بنابراین ماکزیمم مقدار در بازه‌های $[2048,4095],[1024,2047],...,[32,63],[16,31],[8,15]$ به ترتیب برابر ۱۱٬۹٬۷،…،۲۱ و ۲۳ خواهد شد. در مورد عدد ۳۹۹۹ مقدار $f$ به شکل زیر برابر ۲۳ می‌شود:

$$3999 \rightarrow 2000,1999 \rightarrow 1000,999 \rightarrow 500,499 \rightarrow 250,249 \rightarrow 125,124\\ \rightarrow 62,63 \rightarrow 31,32 \rightarrow 16,15 \rightarrow 8,7 \rightarrow 3,4 \rightarrow 2,1$$