در یک دایره $n\geq 2$ وتر میکشیم به گونه ای که هیچ ۳تایی در دایره همرس نشوند. تعداد پاره خط های ایجاد شده بوسیلهٔ آنها را بیابید.

Question

در یک دایرهٔ داده شده، $n$ وتر که $n\geq 2$ است، کشیده شده است به گونه‌ای که هیچ سه تایی درون دایره همرس نیستند. فرض کنید $m$ تعداد نقاط برخورد وترها درون دایره باشد. $r$ را تعداد پاره‌خط‌های حاصل از تقسیم وترها توسط نقطه‌های برخورد تعریف کنید. $r$ را بر حسب $n$ و $m$ بیابید.

پاسخ آخر $r=n+2m$ داده‌شده‌است، اما چگونه به این پاسخ باید رسید؟

Answer 1

متن اولیه: مختصر و مفید بهت جواب میدم

از هر m نقطه دو خط میگدرد یعنی اگر بر روی یکی از نقطه ها تقاطع زوم کنیم یه ضربدر میبینیم انگار چهار نیم خط . و n2 نقطه ی روی محیط دایره هم فقط یه خط بهشون وارد شده پس ما اگر بر روی تک تک این نقطه ها زوم کنیم به ازای هر کدوم از این m نقطه چهار نیم خط و به ازای هر کدوم از 2n نقطه روی محیط هم یک نیم خط میبینم برای بدست اوردن پاره خط ها کافی است (2n+4m)/2) بکنیم که حکم نتیجه بشود.

متن پس از ویرایش: برای هر وتر دو نقطه بر روی محیط دایره داریم. پس اگر دایره و وترها را بکشیم $2n$ نقطه روی محیط دایره و $m$ نقطه از برخوردهای وترها داریم. شکل حاصل (فقط نقطه‌ها و پاره‌خط‌ها، در نتیجه بدون خود دایره) یک گراف با $2n+m$ گره می‌شود که درجهٔ هر یک از $2n$ گره‌ای که روی محیط بودند برابر با ۱ است و درجهٔ هر گره که از برخورد دو وتر بدست آمده‌است (به دلیل اینکه بیشتر از دو وتر نمی‌توانند در یک نقطه برخورد کرده‌باشند) برابر با ۴ است. اکنون هر وتر که یک یال از این گراف است به دو گره (نقطه) وصل است پس کافی است تعداد یال‌های وصل به گره‌ها را (یعنی درجهٔ گره‌ها را) با هم جمع کنیم تا دوبرابر تعداد یال‌ها (پاره‌خط‌ّ‌ها) بدست آید. پس با نمادگذاری خود پرسش که تعداد پاره‌خط‌ها $r$ نامیده شده‌است داریم:

\begin{align} 2r=\sum_{i=1}^{2n} (1)+\sum_{i=1}^m (4)=2n+4m & \Longrightarrow r=\frac{2n+4m}{2}\\ & \Longrightarrow r=n+2m \end{align}