پر کردن جدول (۲۲ نمره)

یک جدول $2025 \times 2025$ داریم. یک خانه از این جدول را خانه‌ای «در حاشیه‌ی جدول» می‌گوییم اگر در سطر اول، سطر آخر، ستون اول یا ستون آخر جدول باشد. دو خانه از جدول «مجاور» هستند اگر و تنها اگر در دقیقا یک ضلع مشترک باشند. به دنباله‌ای از خانه‌های جدول که عضو ابتدا و انتهای آن به ترتیب $A$ و $B$ است و هر دو عضو متوالی آن مجاور هم هستند نیز یک «مسیر» بین دو خانه‌ی $A$ و $B$ می‌گوییم. می‌خواهیم در هر یک از خانه‌های جدول، یکی از اعداد $1$ تا $k$ را قرار دهیم به‌ طوری که همه‌ی شرایط زیر رعایت شوند:

• از هر عدد حداکثر دو بار استفاده شده باشد.
• اگر دو خانه دارای عدد یکسان $x$ باشند، هر کوتاه‌ترین مسیر بین آن دو خانه، شامل حداقل یک خانه با عددی اکیداً بزرگ‌تر از $x$ باشد. طبیعتاً در این صورت دو خانه‌ی مجاور هم نباید عدد یکسانی داشته باشند.
• عدد هر خانه در حاشیه‌ی جدول اکیداً بزر‌گ‌تر از عدد هر خانه‌ای باشد که در حاشیه‌ی جدول نیست.

کم‌ترین مقدار ممکن برای $k$ را بیابد.

برای پاسخ کامل این سوال، لازم است یک عدد $q$ ارائه دهید و به‌ازای آن، هر دو کار زیر را انجام دهید. طبیعتاً اگر موفق به انجام فقط یکی از دو مورد شوید، بخشی از امتیاز سوال به شما تعلق می‌گیرد.

1. برای پر کردن جدول، شیوه‌ای ارائه دهید که در آن، ${ k = q }$ باشد.
2. ثابت کنید شیوه‌ای برای پر کردن جدول وجود ندارد که در آن، ${ k < q }$ باشد.