المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۶:سوال ۱۷

سؤال ۱۷

روی تخته تعدادی عدد طبیعی نوشته‌ شده است. در هر مرحله یک عدد روی تخته مانند $a$ ($a \gt 1$) را پاک می‌کنیم و به‌ جای آن $\lceil a/2 \rceil$ و $\lfloor a/2 \rfloor$ را می‌نویسیم این کار را آن‌قدر ادامه می‌دهیم تا همه اعداد روی تخته برابر با ۱ شوند. حال فرض کنید در ابتدا فقط عدد $n$ روی تخته نوشته‌ شده باشد. تعداد اعداد متفاوتی که در طول عملیات فوق روی تخته نوشته می‌شود را $f(n)$ بنامید. مثل $f(۷) = ۵$، زیرا ابتدا به‌جای ۷، دو عدد ۳ و ۴ را می‌نویسیم. سپس به‌جای ۲،۴ تا ۲ و به‌جای ۱،۳ و ۲ را می‌نویسیم. در پایان نیز به‌جای هر ۲،دو تا ۱ می‌نویسیم. بنابراین ۵ عدد مختلف ۴،۳،۲،۱ و ۷ در طول این عملیات روی تخته نوشته می‌شوند. بزرگ‌ترین مقدار $f(n)$ به ازای $1 \le n \le 4000$ چند است؟

  1. ۲۳
  2. ۳۱
  3. ۲۱
  4. ۱۹
  5. ۲۰۰۰

پاسخ

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

اگر عدد $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$$


ابزار صفحه