صفحه (۲۵ نمره)

روی یک صفحه $n$ خط راست کشیده‌ایم، طوری که هیچ دو خطّی موازی و هیچ سه خطّی همرس نیستند. این خطوط، صفحه را به تعدادی ناحیه افراز کرده‌اند. ثابت کنید می‌توانیم در هر یک از ناحیه‌ها یک عدد صحیح بنویسیم، طوری که شرایط زیر برقرار باشد:

پاسخ

در ابتدا حکم مسئله را قوی‌تر می‌کنیم و به قضیه‌ی زیر می‌رسیم:

قضیه: می‌توان نواحی ایجاد شده توسط $n$ خط در حالت عمومی را طوری با اعداد صحیح پر کرد که علاوه بر برقرار بودن شرایط مسئله، شرایط زیر نیز برقرار باشد:

  • اگر عدد x به ناحیه‌ای نسبت داده شود داشته باشیم:

$$1 \le |x| \le 2^{n}$$

  • علامت عدد اختصاص داده شده به دو ناحیه‌ی مجاور با هم متفاوت باشد.

اثبات: با استقرای ضعیف بر روی $n$ به اثبات قضیه‌ی فوق می‌پردازیم.

حالت پایه: به ازای $n = 1$ که حکم واضح است.

گام استقرا:

خط $n$ ام را در نظر نمی‌گیریم و نواحی ایجاد شده با $n - 1$ خط دیگر را طبق فرض استقرا طوری عددگذاری می‌کنیم که شرایط قضیه برقرار باشد. حال خط $n$ ام را اضافه می‌کنیم و یکی از طرفین آن را در نظر می‌گیریم. حال عدد تمام نواحی طرف انتخاب شده را تغییر علامت می‌دهیم‌ (در منفی‌یک ضرب می‌کنیم). اکنون در هر کدام از طرفین خط که طبق فرض استقرا، حکم قضیه برقرار است. در مورد نقاط ایجاد شده بر روی خط $n$ ام نیز می‌توان این‌گونه گفت که با اضافه شدن خط $n$ ام هر ناحیه‌ای که این خط آن را قطع کرده، به دو ناحیه تقسیم شده است که اکنون عدد آن‌ها قرینه‌ی یکدیگر می‌باشد زیرا دقیقا یکی از طرفین تغییر علامت داده است. بنابر‌ این چون هر نقطه‌ای که بر روی خط $n$ ام قرار دارد مجاور دقیقا دو جفت از نواحی گفته شده می‌باشد، پس مجموع نواحی مجاور آن برابر ۰ خواهد بود.

حال تنها مشکلی که وجود دارد این است که ممکن است یکی از اعداد در هر دو طرف خط موجود باشد در صورتی که اعداد اختصاص داده شده به نواحی باید با هم متمایز می‌بودند. برای رفع این مشکل، یکی از طرفین خط $n$ ام را به دلخواه انتخاب کرده و تمام اعداد مثبت آن را به علاوه‌ی $2^{n - 1}$ و تمام اعداد منفی آن را منهای $2^{n - 1}$ می‌کنیم. حال تمام اعداد طرف انتخاب شده در بازه‌ی $[2^{n - 1} + 1, 2^{n}]$ و تمام اعداد طرف دیگر در بازه‌ی $[1, 2^{n - 1}]$ قرار دارند، اعداد اختصاص داده شده به نواحی، دو به دو متمایزند و همگی شرط قضیه را دارند.

حال تنها نکته‌ای که باقی‌ می‌ماند این است که آیا جمع نواحی مجاور همه‌ی نقاط برابر ۰ هست یا خیر. نقاطی که بر روی خط $n$ ام هستند که هر کدام شامل یک عدد منفی و یک عدد مثبت می‌شدند و لذا شرط موردنظر برای آن‌ها همچنان برقرار است. نقاطی که در طرف انتخاب نشده بودند نیز تغییری در نواحی مجاور آن‌ها اتفاق نیفتاده است. نقاط طرف انتخاب شده نیز هر کدام شامل دو عدد منفی و دو عدد مثبت‌ می‌شدند و لذا مجموع نواحی مجاور آن‌ها همچنان برابر صفر است. پس تمام شرایط قضیه در عددگذاری فعلی برقرار است.

بنابراین حکم به ازای تمامی $n$ها درست است.