انتخاب 5 سرباز از 12 سرباز یک صف، به گونه ای که هیچ 2 سربازی کنار هم نباشند

Question

12 سرباز با قدهای متفاوت داریم که در یک صف ایستاده اند. می خواهیم 5 سرباز را به گونه ای انتخاب کنیم که هیچ دو سربازی در صف کنار هم ایستاده نباشند.

Answer 1

با فرض اینکه جایگاه هر سرباز ثابت و مشخص بوده، انتخاب 5 سرباز به شکلی که هیچ کدام در کنار یکدیگر نباشند، درست مثل چیدن این 5 سرباز است به طوری که هیچ کدام کنار یکدیگر نباشند. البته با این تفاوت که نباید جایگشت های مختلف رو تاثیر بدیم.

فرض می کنیم 7 سرباز دیگر به طور زیر چیده شده باشند(خط های افقی رو سرباز های چیده شده در نظر می گیریم): $$-|-|-|-|-|-|-|-$$

واضح است که 5 سرباز دیگر هرکدام می توانند در یکی از قسمت های خالی ما بین سرباز های چیده شده قرار بگیرند بدون نقض کردن خواسته ی مسئله؛ که این حالات برابر است با: $$ \binom{8}{5} = 56 $$

به این صورت می توانیم تمام حالت های انتخاب 5 سرباز غیر مجاور را بدست بیاوریم.