اثبات الگوریتمی هوشمندانه

[حالا هرکی]

@مربع های واحد ربع اول دستگاه مختصات دکارتی که روسشان دارای مولفه های صحیح میباشد را در نظر بگیرید آیا میتوان برخی از این مربع ها را رنگ کرد به نحویکه دارای شرایط زیر باشند؟

1-در هر مربع دلخواه که یکی از رئوسش(0و0)باشد وبقیه ی رئوسش صحیح باشند تعاد مربع های رنگ شده از تعداد مربع های رنگ نشده بیشتر باشد

2-هر خط موازی نیمساز ربع اول فقط از تعداد متناهی مربع رنگ شده بگذرد.

ایتالیا سال 97 لطفا به art of لینک ندید

 

[mahanmath]

پاسخ : اثبات الگوریتمی هوشمندانه

جمله دوم رو نمی‌فهمم ، می‌شه بگی‌ یعنی‌ چی‌ ؟ :105:

 

[nybody]

پاسخ : اثبات الگوریتمی هوشمندانه

مربع های واحدی که قطر اونها منطبق بر نیمساز ربع اول هست رو رنگ نمیکنیم، بقیه رو رنگ میکنیم، البته چون باید تعداد مربع های رنگ شده ی داخل هر مربع با راس (0و0) از تعداد رنگ نشده هاش بیشتر باشه، اولین مربع (یعنی مربعی که رئوسش (0و0) و (1و0) و (0و1) و (1و1) هستن) رو هم رنگ میکنیم، پس شرط اول برقراره.
با توجه به اینکه نیمساز فقط از یک مربع رنگ شده میگذره که اون هم متناهیه، شرط دوم هم برقراره.

 

[حالا هرکی]

پاسخ : اثبات الگوریتمی هوشمندانه

جناب شرط دوم بیان میکند همهی خطوط موازی نیمساز ربع اول از تعداد متناهی مربع سیاه میگذرد الگوریتم شما این خطوط از بینهایت خانهی سیاه میگذرد مثلا یه خط موازی این خط که از مربع های سفید میگذرد رسم کنید تا سیاه های پایین را در بینهایت نقطه قطع کند

 

[nybody]

پاسخ : اثبات الگوریتمی هوشمندانه

حواسم به کلمه ی موازی نبود :d شرمنده