فهرست مندرجات
سوالات ۱۸ و ۱۹
محسن یک دیگ بزرگ برنج و یک قاشق دارد. به او گفته می‌شود که تعدادی روز فرصت دارد تا برنج بخورد. تعداد دقیق روزها به محسن گفته نمی‌شود، امّا به او گفته می‌شود این تعداد از مجموعه‌ی $\{1, 2, \ldots, n\}$ است. به عبارت دقیق‌تر محسن به احتمال $\frac{1}{n}$ دقیقن یک روز فرصت دارد، به احتمال $\frac{1}{n}$ دقیقن دو روز فرصت دارد، … و به احتمال $\frac{1}{n}$ دقیقن $n$ روز فرصت دارد. محسن در هر روز می‌تواند یکی از دو کار زیر را انجام دهد:
- تعداد قاشق‌هایش را دو برابر کند.
- هر قاشق‌ش را پر از برنج کند و بخورد.
هر گاه فرصت محسن تمام شود، به او گفته می‌شود که پایان کار فرا رسیده است! محسن می‌خواهد روشی را در پیش بگیرد که امید ریاضی مجموع میزان برنجی که می‌خورد بیشینه شود. به عبارت دیگر او می‌خواهد روشی در پیش گیرد که به طور میانگین در میان $n$ حالت موجود (برای تعداد روزهایی که فرصت دارد)، بیش‌ترین میزان برنج خورده شود.
سوال ۱۸
فرض کنید $n=4$ باشد؛ یعنی به محسن گفته می‌شود تعداد روزهای فرصت‌ش از مجموعه‌ی $\{1, 2, 3, 4\}$ است. بیشینه‌ی امید ریاضی گفته شده چند قاشق برنج است؟
- $3$
- $\frac{17}{5}$
- $\frac{5}{2}$
- ۴
- ۸
پاسخ
گزینه (۱) درست است.
اگر $e_n$ امید ریاضی گفته شده باشد، پاسخ این سوال برابر $e_4$ است. داریم: $$e_n = max\Big(1+\frac{n-1}{n}e_{n-1}, 2\times\frac{n-1}{n}e_{n-1} \Big)$$ پس اگر $e_{n-1}>\frac{n}{n-1}$ باشد، روش دو برابر کردن قاشق و در غیر این صورت روش خوردن در حرکت یکم بهینه است. حال مقدار $e_4$ را به دست می‌آوریم: $$e_0 = 0 \rightarrow e_1 = 1 \rightarrow e_2 = \frac{3}{2} \rightarrow e_3 = 2 \rightarrow e_4 = 3$$
سوال ۱۹
فرض کنید $n=20$ باشد؛ یعنی به محسن گفته می‌شود تعداد روزهای فرصت‌ش از مجموعه‌ی $\{1, 2, \ldots, 20\}$ است. بیشینه‌ی امید ریاضی گفته شده چند قاشق برنج است؟
- $2^{19}$
- $\frac{21}{2}$
- $\frac{3}{5} \times 2^{15}$
- $2^{15}$
- $\frac{3}{5} \times 2^{16}$
پاسخ
گزینه (۵) درست است.
از $n=4$ به بعد $e_{n-1}\ge 2 > \frac{n}{n-1}$ بوده و در حرکت یکم به‌تر است قاشق را دو برابر کنیم، پس داریم: $$e_{20} = 2 \times \frac{19}{20} \times 2 \times \frac{18}{19} \times 2 \times \ldots \times 2 \times \frac{4}{5} \times e_4 = 3 \times \frac{4}{20} \times 2^{16} = \frac{3}{5} \times 2^{16}$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
