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

ثابت کنید که در گراف کاملِ $K_p$، بین دو رأسِ دلخواه، به تعدادِ $[(p-2)!e]$ مسیر وجود دارد.

ویرایشگر: پرسش‌کننده به تلاش خود اشاره‌ای نکرده‌است.

1 پاسخ

+5 امتیاز
توسط erfanm (13,825 امتیاز)
ویرایش شده توسط AmirHosein

در سوال باید داشته باشیم که $p \geq 3 $ چون اگر$ p=2 $ فقط $1$ مسیر داریم اما حاصل جز صحیح برابر $2$ می‌شود.

ابتدا تعداد مسیرهای موجود به طول $k$ برابر است با اینکه ما غیر از دو راس دلخواه انتخاب شده $ k-1 $ راس دیگر را در بین رئوس باقیمانده انتخاب کنیم و به هر ترتیبی که این رئوس را بین دو راس اولیه قرار دهیم یک مسیر بین دو راس اولیه بدست می‌آید لذا تعداد حالات برابر است با ${p-2 \choose{k-1} }(k-1)! $

پس تعداد کل مسیرها با طولهای دلخواه بین دو راس دلخواه اولیه برابر است با: $ \sum_{k=1}^{p-1} {p-2 \choose{k-1} }(k-1)! $ یا با لغزاندن اندیس‌ها داریم $ \sum_{k=0}^{p-2} {p-2 \choose{k} }(k)! $ که داریم:

\begin{align} \sum_{k=0}^{p-2} {p-2 \choose{k} }(k)! &= \sum_{k=0}^{p-2} \frac{(p-2)!}{(p-2-k)!}\\ &= (p-2)! \sum_{k=0}^{p-2} \frac{1}{(p-2-k)!}\\ &= (p-2)! \sum_{j=0}^{p-2} \frac{1}{j!} \end{align}

دقت کنید $(p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}$ همان $\sum_{k=0}^{p-2} {p-2 \choose{k} }(k)! $ است پس یک عدد صحیح است (بعدا که با جز صحیح کار داریم از این نکته استفاده می‌شود)

توجه کنید $ e^{x} = \sum_{j=0}^ \infty \frac{ x^{k} }{j!} $ پس اگر قرار دهیم $x=1$ آنگاه $ e = \sum_{j=0}^ \infty \frac{ 1 }{j!} $

پس

$$(p-2)!e= (p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}+(p-2)! \sum_{j=p-1}^ \infty \frac{ 1 }{j!} $$

که اگر نشان دهیم $(p-2)! \sum_{j=p-1}^ \infty \frac{ 1 }{j!} < 1 $ آنگاه $[(p-2)!e]=(p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}$ و حکم ثابت می‌شود

\begin{align} (p-2)! \sum_{j=p-1}^ \infty \frac{ 1 }{j!} &< \frac{1}{p-1} + \frac{1}{(p-1)p} + \frac{1}{(p-1)p(p+1)}+\dots\\ &< \frac{1}{p-1} + \frac{1}{(p-1)p} + \frac{1}{(p-1)p^2} +\dots \end{align}

که آخری دنباله‌ای هندسی با جمله اول $ \frac{1}{p-1} $ و قدر نسبت $\frac{1}{p}$ است که حد مجموع آن برابر است با

$$ \frac{ \frac{1}{p-1}}{1- \frac{1}{p}} = \frac{p}{ (p-1)^{2} } $$

که برای $p \geq 3 $ عبارت کمتر از $1$ است.(به کمک معادله و تعیین علامت)


حمایت مالی

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