مسئلهٔ اعداد روی دایره
۱۰۱ عدد طبیعی دور یک دایره نوشته شدهاند و مجموع همهٔ آنها برابر ۳۰۰ است.
نشان دهید که میتوان تعدادی از این اعداد را که پشت سر هم (متوالی) روی دایره قرار دارند انتخاب کرد (مثل یک «وتر» روی دایره)، بهطوریکه مجموع آنها دقیقاً برابر ۲۰۰ شود.
سادهسازی مسئله: از کجا شروع کنیم؟
جورج پولیا، در کتاب مشهورش How to Solve It،
یک توصیهٔ کلیدی برای برخورد با مسئلههای سخت دارد که معمولاً اینگونه نقل میشود:
اگر مسئلهای هست که نمیتوانی آن را حل کنی،
حتماً یک مسئلهٔ سادهترِ مرتبط وجود دارد که میتوانی حلش کنی؛
آن را پیدا کن.
این جمله فقط یک توصیهٔ فلسفی نیست؛
بلکه یک استراتژی عملیِ حل مسئله است.
وقتی با یک مسئلهٔ دشوار روبهرو میشویم، اغلب مشکل این نیست که هیچ راهی وجود ندارد،
بلکه این است که مسئله با تمام پیچیدگیهایش یکجا جلوی ما قرار گرفته است.
پولیا پیشنهاد میکند که بهجای درجا زدن:
- مسئله را سادهتر کنیم،
- بعضی قیدها را موقتاً کنار بگذاریم،
- و ببینیم در نسخهٔ سادهشده چه اتفاقی میافتد.
اگر نسخهٔ ساده را بفهمیم، معمولاً میتوانیم همان ایده را—با کمی دقت—به مسئلهٔ اصلی برگردانیم.
اگر دایره نبود، چه میشد؟
حالا دقیقاً طبق همین توصیهٔ پولیا عمل میکنیم و یکی از قیدهای مسئله را موقتاً حذف میکنیم.
فرض کنید این ۱۰۱ عدد، بهجای اینکه دور یک دایره نوشته شده باشند، روی یک خط پشت سر هم قرار گرفتهاند.
در این حالت، مسئله آشناتر میشود: ما بهدنبال تعدادی عدد متوالی هستیم که جمعشان دقیقاً ۲۰۰ شود.
در چنین موقعیتی، یک ابزار طبیعی و بسیار قدرتمند داریم: جمعهای جزئی.
جمعهای جزئی: چرا این ایده اینقدر مهم است؟
وقتی با مسئلهای سروکار داریم که در آن «جمعِ بخشهای متوالی» اهمیت دارد، اولین کاری که میتوانیم بکنیم این است که بهجای محاسبهٔ تکتکِ این جمعها، یک نمای کلی از اطلاعات بسازیم.
اینجاست که ایدهٔ جمعهای جزئی وارد میشود.
فرض کنید اعداد روی خط بهترتیب چنین باشند: \(a_1, a_2, a_3, \dots, a_{101}\)
جمعهای جزئی را اینگونه تعریف میکنیم: \(s_0 = 0\) و برای هر $k$ از $1$ تا $101$: \(s_k = a_1 + a_2 + \dots + a_k\)
این دنبالهٔ جدید، در واقع «تاریخچهٔ تجمعی» اعداد است: هر $s_k$ به ما میگوید اگر از ابتدای لیست حرکت کنیم و به خانهٔ $k$ برسیم، جمع اعداد چقدر شده است.
چرا جمعهای جزئی کار ما را ساده میکنند؟
مزیت بزرگ جمعهای جزئی این است که: جمع هر قطعهٔ متوالی را بهصورت اختلاف دو عدد بیان میکنند.
اگر بخواهیم جمع اعداد از $a_{i+1}$ تا $a_j$ را حساب کنیم، کافی است بنویسیم: \(a_{i+1} + a_{i+2} + \dots + a_j = s_j - s_i\)
یعنی: بهجای جمع کردن تعداد زیادی عدد، فقط کافی است دو عدد را از هم کم کنیم.
اما اهمیت اصلی این ایده فراتر از راحتی محاسبه است. این بازنویسی، مسئله را تغییر شکل میدهد.
تغییر زاویهٔ نگاه
در مسئلهٔ ما، هدف این است که یک قطعهٔ متوالی پیدا کنیم که جمعش ۲۰۰ شود. با زبان جمعهای جزئی، این دقیقاً یعنی:
دو عدد از میان $s_0, s_1, \dots, s_{101}$ وجود دارند
که اختلافشان برابر ۲۰۰ باشد.
این جمله بسیار سادهتر از صورت اولیهٔ مسئله است، چون دیگر با «انتخاب قطعه» سروکار نداریم، بلکه فقط دنبال دو عدد با اختلاف مشخص میگردیم.
چرا این تکنیک بارها و بارها جواب میدهد؟
جمعهای جزئی یکی از آن ایدههایی هستند که در ظاهر سادهاند، اما تقریباً در هر مسئلهای که با «قطعات متوالی»، «بازهها» یا «حرکت قدمبهقدم» سروکار دارد، دوباره و دوباره ظاهر میشوند.
دلیلش هم روشن است: این تکنیک به ما اجازه میدهد بهجای نگاه محلی و جزءبهجزء، یک تصویر سراسری از مسئله بسازیم و از خواص کلی آن استفاده کنیم.
اصل لانهٔ کبوتر
چرا یک اصل ساده، اینهمه قدرتمند است؟
در ادامهٔ حل، به یکی از سادهترین اما عمیقترین اصول ریاضی نیاز داریم: اصل لانهٔ کبوتر.
صورت کلاسیک این اصل خیلی کوتاه است:
اگر بیش از $k$ شیء را در $k$ جعبه بگذاریم،
دستکم یکی از جعبهها باید بیش از یک شیء داشته باشد.
در نگاه اول، این جمله آنقدر بدیهی است که شاید حتی «ریاضی» بهنظر نرسد. اما قدرت واقعی این اصل نه در ظاهرش، بلکه در جایی است که به کار میرود.
چرا این اصل مهم است؟
اصل لانهٔ کبوتر به ما اجازه میدهد بدون آنکه یک نمونهٔ مشخص بسازیم، وجود یک پدیده را با قطعیت ثابت کنیم. این اصل بهخصوص در موقعیتهایی کاربرد دارد که:
- تعداد حالتها زیاد است،
- اما تعداد «طبقهبندیها» محدود است،
- و ما دنبال یک برخورد اجباری بین حالتها هستیم.
در چنین شرایطی، حتی اگر ندانیم دقیقاً کدام حالتها با هم برخورد میکنند، میدانیم که برخورد حتماً رخ میدهد.
یک مثال خیلی ساده
فرض کنید ۱۰ عدد طبیعی دلخواه انتخاب کنیم و هرکدام را بر حسب باقیماندهٔ تقسیم بر ۹ دستهبندی کنیم.
چون فقط ۹ باقیماندهٔ ممکن داریم، طبق اصل لانهٔ کبوتر، حداقل دو تا از این عددها باقیماندهٔ یکسانی دارند.
نتیجه: تفاضل این دو عدد بر ۹ بخشپذیر است.
نه عددها را میشناسیم، نه جای دقیقشان را؛ اما وجود چنین جفتی اجتنابناپذیر است.
ارتباط اصل لانهٔ کبوتر با مسئلهٔ ما
در مسئلهٔ اعداد روی دایره، ما تعداد زیادی «جمع جزئی» داریم، اما وقتی آنها را بهصورت مناسب دستهبندی کنیم میبینیم که تعداد دستهها کمتر از تعداد جمعهاست. اینجاست که اصل لانهٔ کبوتر وارد عمل میشود: دو جمع جزئی ناچاراً در یک دسته میافتند.
دقیقاً دنبال چه چیزی هستیم؟
صورت مسئله میگوید باید روی دایره یک «وتر» (شماری عدد پشت سر هم) پیدا کنیم که مجموع اعداد روی آن دقیقاً ۲۰۰ باشد.
به یک نکتهٔ ساده اما بسیار مهم توجه کنید: مجموع کل اعداد روی دایره برابر ۳۰۰ است.
پس اگر یک وتر متوالی پیدا کنیم که مجموعش ۱۰۰ باشد، وترِ مکملِ آن (یعنی بقیهٔ دایره، که خودش هم تعدادی عدد متوالی است) مجموعی برابر خواهد داشت با: \(300 - 100 = 200.\)
یعنی در واقع:
ما لازم نیست حتماً یک وتر با مجموع ۲۰۰ پیدا کنیم؛
کافی است یا یک وتر با مجموع ۲۰۰
یا یک وتر با مجموع ۱۰۰ پیدا کنیم.
در هر دو حالت، برندهایم.
بازنویسی هدف مسئله
با این دید جدید، مسئله را میتوان اینگونه بازنویسی کرد:
نشان دهید روی دایره،
یک قطعهٔ متوالی از اعداد وجود دارد
که مجموعش مضربی از ۱۰۰ است
(و در عین حال نه صفر و نه کل ۳۰۰).
اگر بتوانیم چنین قطعهای پیدا کنیم، آنگاه آن مضربِ ۱۰۰ ناچاراً یا ۱۰۰ است یا ۲۰۰ و در هر دو حالت مسئله حل میشود.
حل پایانی با جمعهای جزئی و اصل لانهٔ کبوتر
حالا میخواهیم همان ایدهٔ «دستهبندی بر حسب باقیمانده» را دقیق اجرا کنیم.
برای راحتی، یکی از ۱۰۱ عدد را بهعنوان نقطهٔ شروع انتخاب میکنیم
و اعداد را به ترتیب دور دایره میخوانیم.
پس یک دنبالهٔ خطی به دست میآید:
جمعهای جزئی را تعریف میکنیم:
\[s_k = a_1 + a_2 + \dots + a_k \quad (1 \le k \le 101).\]پس $s_{101} = 300$.
گام ۱: دستهبندی بر حسب باقیمانده بر ۱۰۰
به باقیماندهٔ هر $s_k$ هنگام تقسیم بر ۱۰۰ نگاه میکنیم.
هر $s_k$ دقیقاً یکی از ۱۰۰ باقیماندهٔ ممکن را دارد:
اما ما ۱۰۱ عدد داریم:
\[s_1,s_2,\dots,s_{101}.\]پس طبق اصل لانهٔ کبوتر دو تا از $s_1,s_2,\dots,s_{101}$ باقیماندهٔ یکسان دارند. اختلاف این دو مضرب ۱۰۰ است.
گام ۲: نتیجهٔ کلیدی
اگر برای دو شاخص $1 \le i < j \le 101$ داشته باشیم
\[s_i \equiv s_j \pmod{100},\]آنگاه اختلافشان مضربی از ۱۰۰ است:
\[s_j - s_i \equiv 0 \pmod{100}.\]اما
\(s_j - s_i = a_{i+1} + a_{i+2} + \dots + a_j\) که دقیقاً جمع یک قطعهٔ متوالی از اعداد است. پس ثابت کردیم:
یک قطعهٔ متوالی از اعداد وجود دارد که جمعش مضربی از ۱۰۰ است.
از طرفی چون اعداد طبیعیاند، این جمع صفر نیست. و همچنین شامل کل اعداد دایره نمیشود. پس جمعش نمیتواند ۳۰۰ باشد. بنابراین این مضربِ ۱۰۰ فقط دو گزینه دارد:
\[\set{100, 200}.\]گام ۳: از ۱۰۰ به ۲۰۰
اگر همان قطعهٔ متوالی، مجموع ۲۰۰ داشته باشد، کار تمام است.
اگر مجموعش ۱۰۰ باشد، به وترِ مکمل آن نگاه میکنیم: بقیهٔ دایره نیز یک قطعهٔ متوالی است و مجموعش
\[300 - 100 = 200\]خواهد بود.