جدول‌های پیچ‌پیچ

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

جدولی را که پینگو بتواند با محدودیت‌های فوق از گوشه‌ی بالا و چپ آن به گوشه‌ی پایین و راست آن برسد، جدول پیچ‌پیچ می‌نامیم. در این مسئله می‌خواهیم تعداد جدول‌های پیچ‌پیچ را از بین همه‌ی $2^{n\times n}$ جدول ممکن به‌دست آوریم. دقت کنید که خانه‌ی بالا و چپ و خانه‌ی پایین و راست جدول پیچ‌پیچ باید قابل عبور باشند.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10289$ محاسبه شده‌اند.

$1$- الف ($7$ نمره) : باقی‌مانده‌ی تعداد جدول‌های پیچ‌پیچ به ازای $n=5$ بر $\Delta$ چند است؟

$1$- ب ($8$ نمره) : باقی‌مانده‌ی تعداد جدول‌های پیچ‌پیچ به ازای $n=20$ بر $\Delta$ چند است؟

$1$- ج ($9$ نمره) : باقی‌مانده‌ی تعداد جدول‌های پیچ‌پیچ به ازای $n=100$ بر $\Delta$ چند است؟

$1$- د ($7$ نمره) : باقی‌مانده‌ی تعداد جدول‌های پیچ‌پیچ به ازای $n=10^6$ بر $\Delta$ چند است؟

• سوال بعد