سؤال ۲۱
یک ریاضی‌دان در دفتر کار خود یک تخته‌سیاه خیلی بزرگ دارد. روزی پسرش از وی خواست تا با او بازی کند. ریاضی‌دان که به بازی‌های کودکانه چندان آشنایی نداشت، به فرزندش پیشنهاد کرد بازی «رولینگ» را انجام دهند. ریاضی‌دان به پسرش گفت که در این بازی، پسر با گچ یک نقطه روی تخته بگذارد و سپس ریاضی‌دان از آن نقطه دو نیم‌خط رسم کرد: یک نیم‌خط افقی از نقطه به سمت چپ و یک نیم‌خط عمودی از نقطه به پایین.
پسر که از این بازی کلافه شده بود از پدرش خواست تا یک بازی دیگر مثل «کوئیدیچ» را بازی کنند، ولی ریاضی‌دان برای آن‌که پسرش راضی شود به او گفت: «اگر بتوانی با انتخاب ۷ نقطه بیشترین ناحیه‌های بسته را ایجاد کنی تو را به تماشای مسابقه‌ی کوئیدیچ خواهم برد». یک ناحیه‌ی بسته، ناحیه‌ای از تخته است که دورتادور آن به‌وسیله‌ی نیم‌خط‌ها بسته شده باشد. مثلاً در شکل مقابل با انتخاب ۴ نقطه، دو ناحیه‌ی بسته ایجاد کرده‌ایم که با هاشور مشخص شده‌اند.
پسر با انتخاب ۷ نقطه حداکثر چند ناحیه‌ی بسته می‌تواند ایجاد کند؟
- ۱۰
- ۱۲
- ۱۵
- ۱۸
- ۲۰
پاسخ
گزینه (۳) درست است.
خطوط افقی و عمودی مربوط به نقطه $i$ حداکثر یکی از خطوط افقی و یا عمودی مربوط به نقطه $j$ را قطع می‌کنند. بنابراین با اضافه شدن نقطه $k$ام حداکثر $(k-1)$ نقطه تلاقی جدید پدید می‌آید که به ازای حداقل یکی از نقاط تلاقی ناحیه باز و به ازای حداکثر $(k-2)$ نقطه تلاقی دیگر ناحیه بسته ایجاد می‌شود. بنابراین اگر حداکثر تعداد ناحیه‌های بسته برای $k$ نقطه را با $D(k)$ نشان می‌دهیم رابطه $D(k)=D(k-1)+k-2$ برقرار خواهد بود. از طرف دیگر چون $D(2)=0$ بنابراین:
$$D(3)=D(2)+1=1$$
$$D(4)=D(3)+2=3$$
$$D(5)=D(4)+3=6$$
$$D(6)=D(5)+4=10$$
$$D(7)=D(2)+5=15$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
