ویکیمدرسه/المپیاد ریاضی/دورهٔ تابستانی المپیاد ریاضی ایران/آزمون خلاقیت ۱۳۸۸/خوشهٔ نامتناهی
صورت مسأله
ویرایش8. خوشهٔ نامتناهی (90 دقیقه)
فرض کنید برخی از رئوس شبکهٔ دو بعدی مسطح (یعنی ) را حذف کردهایم. به این نقاط به شکل یک گراف نگاه کنید؛ دو رأس به هم وصل هستند اگر در یک درایه برابر باشند و در یک درایه یک واحد اختلاف داشته باشند. به هر مؤلفهٔ همبندی این گراف یک خوشه گفته میشود.
فرض کنید به ازای هر تعداد رئوس حذفشدهٔ داخل مربع افقی به مرکز مبدأ و به ضلع کمتر از باشد. ثابت کنید رئوس حذفنشده شامل دقیقاً یک خوشهٔ نامتناهی است.
حل مسأله
ویرایشناقص است.
پیشنهاداتی برای تحقیق بیشتر
ویرایش- 1. فرض را ضعیف کنید و همان حکم را ثابت کنید: وجود دارد که به ازای هر تعداد رئوس حذف شدهٔ داخل مربع افقی به مرکز مبدأ و به ضلع کمتر از باشد.
- 2. در قسمت قبل به جای قرار دهید . به ازای چه ضرایبی باز هم میتوان نتیجه گرفت که یک خوشهٔ نامتناهی وجود دارد؟ اگر بخواهیم این خوشه یکتا باشد آیا باید شرایط بیشتری اضافه کنیم؟
- 3. مسأله را در مورد شبکهٔ مثلثی و شبکه مسدسی بررسی کنید.
- 4. مسأله را به شبکهٔ صحیح در فضای سه بعدی تعمیم دهید.
نوشتههایی در این مورد
ویرایششما میتوانید در این قسمت صفحهای با نام خود باز کنید و تحقیقاتی که در راستای این مسأله کردهاید را در معرض دید دیگران قرار دهید. لطفاً صفحهٔ خود را اینگونه نامگذاری کنید: در مورد مسألهٔ «نام مسأله» (نام کامل شما).