یک شبکه $m\times n$ از نقاط را در نظر بگیرید که در آن هر نقطه توسط پاره‌خط‌هایی به نقاط مجاورش در بالا، پایین، چپ و راست (در صورت وجود) وصل است. (طول هر یک از پاره‌خط‌ها را یک واحد فرض کنید.) یک مسیر دنباله‌ای از پاره‌خط‌های به هم متصل این شبکه است. منظور ازیک مسیر «کوتاه»، مسیری است که ابتدای آن نقطه‌ی «بالا و سمت چپ» شبکه و انتهای آن نقطه‌ی «پایین و سمت راست» شبکه باشد و نیز یکی از کوتاه‌ترین مسیرهای بین این دو نقطه باشد (یعنی کم‌ترین تعداد پاره‌خط را داشته باشد). عدد طبیعی دل‌خواه $k$ داده شده است. می‌خواهیم روی هر یک از این پاره‌خط‌ها عددی صحیح از میان اعداد ۰، ۱، … و $k-1$ بنویسیم با این شرط که مجموع اعداد پاره‌خط‌های هر مسیر کوتاه، باقی‌مانده‌ی ثابتی در تقسیم بر $k$ داشته باشد. برای مثال در جدول زیر $n$، $m$ و $k$ به ترتیب برابر ۴، ۳ و ۵ اند. هم‌چنین مجموع اعداد روی پاره‌خط‌های تمامی مسیرهای کوتاه در تقسیم بر ۵ باقی‌مانده‌ی ۱ را تولید می‌کنند.

برای هر $n$، $m$ و $k$ تعداد حالت‌هایی را که می‌توان پاره‌خط‌ها را با شرایط فوق عددگذاری کرد بیابید و ادعای خود را ثابت کنید.

• سوال بعد
• سوال قبل