ویکی‌مدرسه/المپیاد ریاضی/دورهٔ تابستانی المپیاد ریاضی ایران/آزمون خلاقیت ۱۳۸۸/خوشهٔ نامتناهی

صورت مسأله

8. خوشهٔ نامتناهی (90 دقیقه)

فرض کنید برخی از رئوس شبکهٔ دو بعدی مسطح (یعنی $\mathbb {Z} ^{2}$ ) را حذف کرده‌ایم. به این نقاط به شکل یک گراف نگاه کنید؛ دو رأس به هم وصل هستند اگر در یک درایه برابر باشند و در یک درایه یک واحد اختلاف داشته باشند. به هر مؤلفهٔ هم‌بندی این گراف یک خوشه گفته می‌شود.

فرض کنید به ازای هر $n\in \mathbb {N}$ تعداد رئوس حذف‌شدهٔ داخل مربع افقی به مرکز مبدأ و به ضلع $2n+1$ کم‌تر از $n/2$ باشد. ثابت کنید رئوس حذف‌نشده شامل دقیقاً یک خوشهٔ نامتناهی است.

حل مسأله

ناقص است.

پیش‌نهاداتی برای تحقیق بیش‌تر

1. فرض را ضعیف کنید و همان حکم را ثابت کنید: وجود دارد $n_{0}\in \mathbb {N}$ که به ازای هر $n>n_{0}$ تعداد رئوس حذف شدهٔ داخل مربع افقی به مرکز مبدأ و به ضلع $2n+1$ کم‌تر از $n/2$ باشد.

2. در قسمت قبل به جای $n/2$ قرار دهید $\alpha n+\beta$ . به ازای چه ضرایبی باز هم می‌توان نتیجه گرفت که یک خوشهٔ نامتناهی وجود دارد؟ اگر بخواهیم این خوشه یک‌تا باشد آیا باید شرایط بیش‌تری اضافه کنیم؟

3. مسأله را در مورد شبکهٔ مثلثی و شبکه مسدسی بررسی کنید.

4. مسأله را به شبکهٔ صحیح در فضای سه بعدی تعمیم دهید.

نوشته‌هایی در این مورد

شما می‌توانید در این قسمت صفحه‌ای با نام خود باز کنید و تحقیقاتی که در راستای این مسأله کرده‌اید را در معرض دید دیگران قرار دهید. لطفاً صفحهٔ خود را این‌گونه نام‌گذاری کنید: در مورد مسألهٔ «نام مسأله» (نام کامل شما).

در مورد مسألهٔ «خوشهٔ نامتناهی» (مجتبی تفاق)