سوال ۸
سهیل دنبالهی $42$ عضویِ سیبوناچی را به صورت زیر تعریف کرده است:
- $5$ عضو اول دنباله عبارتاند از: $s_1 = 37, s_2 = 42, s_3 = 84, s_4 = 24, s_5 = 41$
- برای $5 < n \leq 42$ داریم: $s_n = s_{n - 1} + s_{n - 2} + s_{n - 3} + s_{n - 4} + s_{n - 5}$
او یک بازه (تعدادی عضو متوالی) از دنباله را عجیب میداند، اگر حاصلجمع اعضای آن بازه عددی فرد باشد. مثلا بازهی $\langle s_3, s_4, s_5 \rangle$ عجیب است چون جمع اعضایش عددی فرد میشود، ولی $\langle s_2, s_3 \rangle$ عجیب نیست چون حاصلجمع اعضایش فرد نمیباشد.
دنبالهی $42$ عضوی سیبوناچی، چند بازهی عجیب دارد؟
- $392$
- $400$
- $420$
- $448$
- $462$
پاسخ
گزینه (3) درست است.
به راحتی میتوان مشاهده کرد که از هر عدد فقط زوجیت آن مهم است. برای حل این مسئله، دنبالهی $p$ را به عنوان جمع پیشوندهای $s$ تعریف میکنیم. یعنی:
$p_i = s_1 + s_2 + \ldots + s_i$.
بنابراین، جمع بازهی $l$ تا $r$ برابر است با:
$p_r - p_{l - 1}$.
این عبارت زمانی فرد میشود که زوجیت $p_r$ با زوجیت $p_{l - 1}$ متفاوت باشد؛ به عبارت دیگر، باید تعداد جفتهای $i$ و $j$ را بشماریم که $0 \leq i < j \leq 42$ برقرار باشد و زوجیت $p_i$ و $p_j$ متفاوت باشد. در واقع، ما بازهی $l$ تا $r$ را با $i = l - 1$ و $j = r$ متناظر کردیم.
محاسبهی زوجیت دنبالهها
اگر زوجیت $12$ عضو اول این دو دنباله را بنویسیم، به دنبالههای زیر میرسیم:
$s = \{1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0\}$
$p = \{1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0\}$
همانطور که مشاهده میکنید، با دوره تناوب $6$، این دو دنباله تکرار میشوند. در دنبالهی $p$، از هر $6$ عدد، $4$ تایشان $1$ هستند.
بنابراین در $42$ عضو اول دنبالهی $p$، تعداد $1$ ها برابر است با:
$42 \times \frac{4}{6} = 28$.
همچنین تعداد $0$ ها با احتساب $p_0 = 0$ برابر با:
$43 - 28 = 15$.
در نتیجه جواب سوال حاصل ضرب تعداد صفرها و یکها است که:
$28 \times 15 = 420$
میشود.
| ▸ سوال قبل | سوال بعد ◂ |