Processing math: 33%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:ترکیبیات:سوال ۲

سوال ۲

یک کج-مسیر به طول ‎n‎ شامل ‎n‎ خانه از یک جدول است با مختصات ‎(x_i‎, ‎y_i)‎ که به ازای ‎1\leq i\leq n-1‎ داشته باشیم ‎|y_i‎ -‎y_{i+1}|=1‎ و ‎|x_i‎ -‎x_{i+1}| =1‎. ثابت کنید نمی‌توان با تعدادی کج-مسیر به طول ‎۹‎ و تعدادی کج-مسیر به طول ‎۱۵‎ تمام خانه‌های یک جدول مستطیلی با تعداد فردی خانه را پوشاند به طوری که هر خانه دقیقا با یک خانه از یک کج-مسیر پوشانده‌ شده‌ باشد. توجه کنید که یک کج-مسیر نمی‌تواند خانه‌ی تکراری از جدول را بپوشاند.


ابزار صفحه