====== سوال ۸ ======

سهیل دنباله‌ی $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$ 

می‌شود.

</پاسخ>

  * [[سوال ۹|سوال بعد]]
  * [[سوال ۷|سوال قبل]]