المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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


ابزار صفحه