مربع های مساوی و موازی در صفحه

[mzoroufchi]

فرض کنید P خانواده ای متناهی از مربع های مساوی و موازی در صفحه باشند بطوریکه هر نقطه از صفحه متعلق به حداکثر k مربع از P باشد.ثابت کنید اعضای P را می توان به 2k-1 دسته افراز کرد بطوریکه هیچ دو مربعی از یک دسته با هم اشتراک نداشته باشند.

 

[mntjmath]

پاسخ : مربع های مساوی و موازی در صفحه

با استقرا مسئله رو حل كن .چپ ترين مربع رو حذف كن بازم شرط مسئله باقي مي مونه طبق فرض استقرا مي تونيم مربع ها رو به 2k-1 دسته طوري افراز كنيم كه هيچ دو تا در يك دسته با هم اشتراك

نداشته باشند حالا چون چپ ترين مربع حداكثر با 2k-2 تا مربع اشتراك دارد پس اين مربع رو مي تونيم تو يكي از دسته ها بگذاريم ....مسئله حل شد.

با الگوريتم حريسانه در رنگ اميزي هم مسئله رو حل كن