یک جدول ٣ × ٣ داریم. می‌خواهیم هر خانه از جدول به جز خانه‌ی بالا‐راست را با قرمز یا آبی رنگ کنیم. پس از رنگ آمیزی، متحرکی از خانه ی پایین‐چپ جدول آغاز می‌کند و در هر مرحله، اگر در خانه‌ی آبی باشد یک واحد به راست و در غیر این صورت یک واحد به بالا می‌رود (ممکن است متحرک از جدول خارج شود). به چند طریق می‌توان خانه های جدول را رنگ کرد، طوری که متحرک پس از تعدادی گام به خانه‌ی بالا‐راست برسد؟
راهنمایی
ابتدا مشخص کنید چه مسیری پیمایش خواهد شد. با توجه به آن مسیر، وضعیت خانه‌ها چه حالت‌هایی دارند؟