Question

بر روی صفحه‌ای تعداد $3n$ نقطه وجود دارد که هیچ سه تایی آن‌ها بر روی یک خط راست قرار ندارند. ثابت کنید که می‌توان با این نقاط تعداد $n$ مثلث ساخت که کاملاً جدا از هم باشند.

دو مثلث را جدا از هم می‌گوییم اگر هر یک در بیرون دیگری قرار گرفته‌باشد و رئوس و اضلاع آن‌ها هیچ برخوردی با یکدیگر نداشته‌باشند.

Answer 1

به نام خدا.

یک خط در صفحه درنظر می گیریم به طوری که تمامی نقاط در یک طرف آن باشد. حال نزدیک ترین نقطه به این خط را در نظر می گیریم. از این نقطه به نقطه ای وصل می کنیم طوری که بقیه نقاطی که هنوز خطی بر آن ها وارد نشده در یک طرف این خط باشند. حال نزدیک ترین نقطه به خط جدید را درنظر می گیریم و از این نقطه به دو نقطه قبل وصل می کنیم. حال دومین نقطه نزدیک به خط را درنظر می گیریم و دوباره کار های قبل را تکرار می کنیم.

Comments

Elyas1@در این شیوه هر بار ممکنه دو نقطه به خط نزدیکترین باشه این حالت را بررسی نکردید

---

@amir7788 در زمانی که دو نقطه نزدیک ترین باشند، آنگاه خط واصل آنها آن خطی است که بقیه نقاط در یک طرف آن است. دلیلش هم این است که خطی که این دو نقطه را به هم وصل می کند، با خط قبلی موازی است پس هیچ نقطه ای نباید پایین این خط باشد.

و اگر هم یکی از این دو نقطه با خط قبلی مثلث تشکیل داده باشد می توانید با آن نقطه ی نزدیک دیگر، خطی را بیابید که بقیه نقاطی که به آنها خط وارد نشده در یک طرف آن باشد.