المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۲:سوال ۲۰

سوال ۲۰

به چند طریق می توان در خانه های یک جدول $۳ \times ۵ $ ستاره گذاشت طوری که در هر خانه حداکثر یک ستاره قرار بگیرد و در هر سطر و ستون ۱ یا ۲ ستاره قرار بگیرد؟

(راهنمایی: ابتدا سعی کنید حداقل و حداکثر تعداد ستاره هایی که می توانیم بگذاریم را بیابید. )

  1. ۲۷۰
  2. ۱۸۰
  3. ۹۰
  4. ۱۵۰
  5. ۲۱۰

پاسخ

گزینه‌ی «۱» درست است.

با توجه به راهنمایی سوال می‌فهمیم که برای این‌که در هر ستونی حداقل یک ستاره باشد باید حداقل 5 ستاره داشته باشیم از طرفی برای این‌که همه سطرها دو ستاره داشته باشند باید 6 ستاره داشته باشیم پس یا 5 ستاره داریم یا 6 ستاره. پس این دو حالت را جدا می‌کنیم و با اصل جمع تعداد کل حالت هارا به‌دست می آوریم.

تعداد حالت‌ها با 5 ستاره: ابتدا سطری را که قرار است در آن یک ستاره باشد را انتخاب می‌کنیم، سپس در آن یک ستاره می‌گذاریم و سپس در اولین سطر باقی‌مانده دو ستاره قرار می‌دهیم طوری که این دو ستاره با ستاره‌ی قبل هم ستون نشوند و در نهایت در تنها سطر باقی‌مانده نیز به طور یکتا باید دو ستاره را قرار دهیم. پس می‌شود:

$\binom{3}{1}\times5\times\binom{4}{2}\times\binom{2}{2}$

حال برای 6 ستاره هم باید یکی از ستون‌ها دو ستاره‌ای شوند، پس ابتدا آن ستون را انتخاب می‌کنیم و در آن دو ستاره قرار می‌دهیم. سپس در سطری که ستاره‌ای ندارد دو ستاره قرار می‌دهیم و در در دو سطر باقی‌مانده هم در هر سطر یک ستاره دیگر قرار می‌دهیم. پس می‌شود:

$\binom{5}{1}\times\binom{3}{2}\times\binom{4}{2}\times\binom{2}{1}\times\binom{1}{1}$

پس در کل 270 حالت می‌شود.


ابزار صفحه