سهیل دنبالهی $42$ عضویِ سیبوناچی را به صورت زیر تعریف کرده است:
او یک بازه (تعدادی عضو متوالی) از دنباله را عجیب میداند، اگر حاصلجمع اعضای آن بازه عددی فرد باشد. مثلا بازهی $\langle s_3, s_4, s_5 \rangle$ عجیب است چون جمع اعضایش عددی فرد میشود، ولی $\langle s_2, s_3 \rangle$ عجیب نیست چون حاصلجمع اعضایش فرد نمیباشد.
دنبالهی $42$ عضوی سیبوناچی، چند بازهی عجیب دارد؟
پاسخ
گزینه (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$
میشود.