اثبات‌های ترکیبیاتی
شمارش مضاعف (قسمت اول)
شمارش مضاعف (قسمت دوم)
تمرین‌های هفتهٔ چهارم
۱. یک گراف کامل \(n\)رأسی داریم که یالهای آن را با دو رنگ، رنگ‌آمیزی کرده‌ایم. اگر تعداد مثلث‌های تک‌رنگ برابر \(\Delta\) باشد، نشان دهید:
\[\Delta\geq\binom{n}{3}-\Bigg\lfloor\frac{n}{2}\Big\lfloor\Big(\frac{n-1}{2}\Big)^2\Big\rfloor\Bigg\rfloor.\]
۲. برنامهٔ تمرین ماهانهٔ یک تیم بسکتبال تنظیم شده است. این تیم در یک ماه \(30\) روزه که در پیش است، قرار است هر روز حداقل یک بازی انجام دهد و در کل ماه حداکثر \(45\) بازی انجام دهد.
الف) بررسی کنید با رعایت شرایط مذکور، آیا می‌توان ثابت کرد تیم به هر صورتی که چیده شود، چند روز متوالی وجود دارد که در آن روزها، تیم دقیقاً \(16\) بازی انجام دهد؟
ب) به ازای چه \(m\)هایی، تعداد روزهای متوالی وجود دارد که تیم در این روزها دقیقاً \(m\) بازی انجام دهد؟
۳. \(12\) دانش‌آموز در کلاس علوم سال هشتم یک مدرسه حضور دارند. ابتدای هر هفته، معلم پروژه‌هایی را به دانش‌آموزان اختصاص می‌دهد و آنها نیز آزادانه گروههایی را تشکیل می‌دهند. هر گروه، مستقلاً روی پروژه‌اش کار می‌کند و نتیجه را انتهای هفته ارائه می‌دهد. این مراحل هفته‌های بعد نیز تکرار میشود. ثابت کنید صرف نظر از تشکیل گروهها، همیشه \(2\) دانش‌آموز وجود دارند به‌طوری که \(5\) دانش‌آموز دیگر همگی با آنها کار کرده یا همگی با هیچ یک از آنها کار نکرده‌اند.
۴. فرض کنید \((P,L)\) که \(P\) مجموعه نقاط و \(L\) مجموعه خطوط، یک پیکربندی هندسی باشد که در آن، هر دو نقطه دقیقاً روی یک خط و همه نقاط روی یک خط قرار ندارند. ثابت کنید: \(|L|\geq|P|\).
۵. مثلث‌های غیرتکرنگ در گراف کامل \(n\)رأسی که یالهای آن با رنگهای قرمز و آبی رنگ‌آمیزی شده‌اند را در نظر بگیرید. ثابت کنید تعداد آنها برابر است با:
\[\frac{1}{2}∑_{i=1}^nr_i b_i \] که برای هر رأس، \(r_i\) تعداد یالهای قرمز مجاورش و \(b_i\) تعداد یالهای آبی مجاورش است.
