مبانی ترکیبیات. هفتهٔ سوم. اصل لانه کبوتری

اصل لانه کبوتری (قسمت اول)

اصل لانه کبوتری (قسمت دوم)

اصل لانه کبوتری (قسمت سوم)

تمرین‌های هفتهٔ سوم

۱. توپ فوتبال از قطعات چرمی سیاه و سفید ساخته شده است. قطعات سیاه، پنج‌ضلعی منتظم و قطعات سفید، شش‌‌ضلعی منتظم‌اند. هر پنج‌ضلعی با \(5\)تا شش ضلعی و هر شش‌ضلعی با \(3\)تا پنج‌ضلعی و \(3\)تا شش‌ضلعی احاطه شده است. \(12\) قطعۀ سیاه در توپ به‌کار رفته است. توپ چند قطعۀ سفید دارد؟

۲. برنامهٔ تمرین ماهانهٔ یک تیم بسکتبال تنظیم شده است. این تیم در یک ماه \(30\) روزه‌ که در پیش است، هر روز قرار است حداقل یک بازی انجام دهد و همچنین در کل ماه حداکثر \(45\) بازی انجام می‌دهد. ثابت کنید این برنامه با رعایت شرایط مذکور، به هر صورتی که چیده شود، چند روز متوالی وجود دارد که در آن روزها، تیم دقیقاً \(14\) بازی انجام می‌دهد. بررسی کنید اگر به جای \(14\) بازی، \(15\) بازی باشد، پاسخ سؤال چه تغییری می‌کند.

۳. فرض کنید \(n\geq3\) عددی فرد باشد. نشان دهید عددی در مجموعهٔ
\[\{1,3,7,\dots,2^{(n-1)}-1\}\]وجود دارد که بر \(n\) بخش‌پذیر است.

۴. هرکدام از پاره‌خط‌هایی که \(\) نقطهٔ مجزا روی محیط دایره را به هم وصل کرده‌اند، با قرمز یا آبی رنگ‌آمیزی می‌کنیم. هر مثلثی که از \(3\) نقطه از این \(9\) نقطه تشکیل شده است، حداقل شامل یک ضلع قرمز است. ثابت کنید \(4\) نقطه وجود دارد که تمام \(6\) پاره‌خطی که آنها را به هم وصل کرده است، قرمز باشد.

۵. هر یک از اتحادهای ترکیبیاتی زیر را با استفاده از استدلالی ترکیبیاتی ثابت کنید.
\[\begin{aligned}a)\;&\binom{n+1}{m}=\binom{n}{m-1}+\binom{n-1}{m}+\binom{n-1}{m-1}\\[7pt]b)\;&\sum_{r=1}^{n}r\binom{n}{r}=n\cdot2^{n-1}\\[7pt]c)\;&1^3+2^3+\dots+n^3=(1+2+\dots+n)^2\end{aligned}\]