به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
3,090 بازدید
در دبیرستان و دانشگاه توسط OXIDE (653 امتیاز)
ویرایش شده توسط AmirHosein

یک گراف کامل با $p$ گره را در نظر بگیرید که با $K_p$ نمایش می‌دهیم. برای هر عدد طبیعیِ $m$، تعداد دورهای موجود در این گراف با طولِ $m$ را در نظر بگیرید. ثابت کنید این عدد زمانی بیشترین مقدار ممکن را می‌گیرد که $m$ برابر باشد با $p-1$.

1 پاسخ

+2 امتیاز
توسط erfanm (12,742 امتیاز)
ویرایش شده توسط erfanm

تعداد دورها به طول $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}$$


حمایت مالی

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