به چند روش تعداد r اسب به خط پایان می رسند؟

Question

تعداد$ r$ اسب در يك مسابقه ي اسب سواري شركت كرده اند .به چند روش ممكن است اين اسب ها به خط پايان برسند؟ توجه كنيد كه ممكن است چند اسب به طور هم زمان به خط پايان برسند.

Answer 1

فرض کنیم که تعداد حالت هایی که $n$ اسب می تونن از خط پایان عبور کنند را با $A(n)$ نمایش دهیم و فرض کنیم $A(0)=1$ . در اینصورت واضح است که $A(1)=1$ و همچنین $A(2)=3$ زیرا برای دو اسب $a,b$ سه حالت اول اسب $a$ و دوم اسب $b$ یا اول اسب $b$ و بعد اسب $a$ و یا هر دو با هم به پایان برسند.

حالا برای $3$ تا اسب یا یکیشون اول میشه و اون دو تای دیگه بنابر $A(2)$ حالت از خط پایان عبور می کنند یا دو تاشون به طور مشترک برنده میشن و اون نفر باقیمانده به $A(1)$ حالت عبور میکنه و یا هر سه با هم از خط پایان عبور می کنند یعنی $A(3)={3\choose 1}A(2)+{3\choose 2}A(1)+{3\choose 3}A(0)$

و اگه به همین ترتیب ادامه دهیم برای $r$ تا اسب داریم $$A(r)=\sum_{i=1}^r{r\choose i}A(r-i)$$

Comments

سلام ممنون از پاسختون. فقط یه سوال دلشتم شما در پاسختون حالتی که هیچکدوم از اسبها با هم به خط پایان نرسند راکه همون r فاکتوریل باشه رو در نظر گرفتین؟ اگه گرفتین کجای فرمول رو شامل میشه؟

---

@زری
مثلا برای حالتی که $3$ تا اسب $a,b,c$داریم وقتی میگیم یکی از آنها برنده می شوند و دو تای دیگه به $A(2)$ حالت عبور می کنند در اینصورت تمام حالت های زیر را شامل می شود:
a و b و c
a و c و b
b و a و c
b و c و a
c و a و b
c و b و a
(که تا اینجا $3!$ است و جواب سوال شما) و حالت های باقیمانده
اول a و b,c با هم
اول b و a,c با هم
اول c و a,b با هم

Answer 2

برای حل این مسئله آن را به حالت‌های زیر دسته بندی می‌کنیم:

1) فرض کنیم تعداد $r$ با هم به خط پایان برسند:

$\quad $ 1-1)تعداد حالت ممکن در این حالت برابر $1$ است.

2)فرض کنیم تعداد $r-1$ با هم به خط پایان برسند:

$\quad $ 1-2) تعداد حالت ممکن ادر این حالت برابر است با انتخاب $r-1$ تا اسب از $r$ تا یعنی برابر است با ${r \choose r-1} $

3)فرض کنیم تعداد $r-2$ با هم به خط پایان برسند:

$\quad $ 1-3) ااگر آن دو تای باقیمانده با هم مشترکا دوم برسنددر این نمونه تعداد حالت برابر است با $ {r \choose r-2} \times 1$ است.

$\quad $ 2-3) ااگر آن دو تای باقیمانده پشت سر هم بیایند در این نمونه تعداد حالت برابر است با $ {r \choose r-2} \times 2!$ است.

$\quad $ پس تعداد کل حالات در این مرحله برابر است با $ {r \choose r-2} \times (1+2!) $

4)فرض کنیم تعداد $r-3$ با هم به خط پایان برسند:

$\quad $ 1-4) ااگر آن سه تای باقیمانده با هم مشترکا دوم برسنددر این نمونه تعداد حالت برابر است با $ {r \choose r-3} \times 1$ است.

$\quad $ 2-4) ااگر از آن سه تای باقیمانده دو تا شون با هم مشترکا دوم برسند در این نمونه تعداد حالت برابر است با $ { r \choose r-3} \times {3 \choose2 } $ است.

$\quad $ 3-4) ااگر از آن سه تای باقیمانده یکیشون دوم شود:

$\qquad $ 1-3-4) تعداد حالتی که دو تای باقیمانده مشترکا سوم شوند برابر است با $ { r \choose r-3} \times {3 \choose1 } \times 1$

$\qquad $ 2-3-4) حالتی که دو تای باقیمانده پشت سر هم بیایند یعنی سوم و چهارم شوند برابر است با $ { r \choose r-3} \times {3 \choose1 } \times 2!$

$\qquad \qquad $ پس تعداد کل حالت برای 4 برابر است با ${r \choose r-3 } (1 + {3 \choose 2} + {3 \choose 1} [1 + 2!])$

$ . \qquad $

$ . \qquad $

$ . \qquad $

و آخرین حالت این است که اصلا هیچکدوم با هم به خط پایان نرسند در اینجا تعداد حالات ممکن برای این، برابر است با $r!$

حال با جمع کردن تعداد حالت‌های به دست آمده در بالا جواب مسئله به دست می‌آید. .

توجه :مسئله بالا با این فرض که فرقی نکند کدام اسب در کدام لاین به پایان برسد حل شده است یعنی اگر اسب شماره $1$ و $2 $ با هم به پایان رسیدند فرقی نکند که $1$ سمت چپ باشد یا $2$. .

Comments

در حالت 3)
قسمت 3-1) اگر (r-2) تا با هم به خط پایان برسند و اون دو تای باقیمانده هم مشترک برسن ممکنه این (r-2) تا همه اول بشن و اون تا مشترکا دوم. یا اون دو تا مشترکن اول بشن و اون (r-2) تا مشترکن دوم.
نمیدونم من اشتباه میکنم یا این حالت رو در جای دیگه حساب کردید؟

---

@fardina
 امیدوارم خوب سوالتون را متوجه شده باشم؛ در یک حالت ممکن است (r-2) تا با هم اول بشوند و  آن دو تای باقیمانده همزمان با هم و بعد (r-2)تای قبل به خط پایان می‌رسند و در یک حالت دیگر ممکن است 2 تا اول برسند و (r-2)تای باقیمانده همزمان با هم و بعد از آن 2تا برسند.
پس می‌توان گفت که این دو حالت متفاوت هستند و جدا اتفاق می‌افتند.