سوال ۱

یک جدول ‎$n\times n$‎ را در نظر بگیرید که اضلاع آن با چوب­کبریت ساخته شده‌است. یک مسیر خوب در این جدول، مسیر جهت‌داری است که ما را با عبور از چوب‌کبریت‌های افقی و عمودی جدول از پایین‌ترین و چپ‌ترین خانه به بالاترین و راست‌ترین خانه برساند و جهت مسیر همیشه به سمت راست یا بالا باشد. به ازای هر زیرمجموعه از چوب‌کبریت‌ها، این زیرمجموعه را از جدول حذف می کنیم و تعداد مسیرهای خوب را محاسبه و یادداشت می‌کنیم. ثابت کنید تعداد اعداد متمایز یادداشت شده حداقل ‎$2^n$‎ است.