به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
1,645 بازدید
سوال شده در دبیرستان و دانشگاه توسط

ثابت کنید در هر گراف کامل $K_p$ تعداد دور با طول $m=p-1$ از همه بیشتر است.

1 پاسخ

+2 امتیاز
پاسخ داده شده توسط
ویرایش شده توسط

تعداد دورها به طول $m $ در گراف کامل از رابطه ی ${p \choose{m} } \frac{(m-1)!}{2} $ بدست می آید کافیست ثابت کنیم که وقتی این عبارت بیشترین مقدار می شود که $m=p-1$

اولا دقت کنید که برای $ m $ و $p-m $ مقدار ${p \choose{m} }$ یکی است لذا وقتی بیشترین دور را می خواهیم باید روی $ m $ای بحث کنیم که بزرگتر یا مساوی است با $ \frac{p}{2} $

برای هر $ \frac{p}{2} \leq k < p $ داریم: $$ \frac{p-1}{k} \leq (p-k) $$ (کافیست قرار دهید $p=k+x$ و توجه کنید که $x \neq 0$) با ضرب طرفین در عبارت مناسب داریم:

$$ \frac{p-1}{k} \leq (p-k)! \Rightarrow $$ $$ \frac{(p-1)(p-2)...(p-k+1)}{k} \leq (p-2)! \Rightarrow $$ $$ \frac{p(p-1)(p-2)...(p-k+1)}{k} \frac{(k-1)! }{(k-1)! } \leq p.(p-2)! \Rightarrow $$ $$ \frac{(p-1)(p-2)...(p-k+1)(k-1)!}{k!} \leq p.(p-2)! \Rightarrow $$ $${p \choose{k} } \frac{(k-1)!}{2} \leq {p \choose{p-1} } \frac{(p-2)!}{2}$$

به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...