سوالی از آرژانتین 2009 (ترکیبیات)

[Goharshady]

یک صفحه ی 50×50 داریم که به مربعهای واحد تقسیم شده است. می خواهیم تعدادی از این مربعها را سیاه کنیم به طوری که هیچ سه مربع سیاهی تشکیل مثلث قائم الزاویه ندهند. حداکثر چند مربع واحد را می توانیم سیاه کنیم؟ (وقتی سیاه می کنیم ، فقط یک نقطه در وسط مربع مورد نظر می گذاریم.)

 

[seifi_seifi]

98 میشه.

به راحتی با استقرا ثابت میشه در مستطیل m×n حداکثر m+n-2 مربع سیاه را رنگ کنیم (البته m و n بزرگتر از 1 هستند.)

 

[abdi]

سيفي جان مي‌شه لطفاً استقراشو بنويسي

 

[301EC]

ye soale moshabeh:
http://www.mathlinks.ro/viewtopic.php?p=338084#338084

 

[Goharshady]

چرا کسی حل نمی کنه؟
اون فقط مشابه بود!

 

[seifi_seifi]

آقای گوهر شادی چه فرقی داره؟!؟!؟!؟!

اون جا راه حل برای n×n وجود داره که اگر 2n-1 خانه را رنگ کنیم سپس یه مثلث قائم الزاویه وجود داره.

پس حداکثر میتوانیم 2n-2 مربع را رنگ کنیم و حال فقط لازمه یه مثال با 2n-2 مربع رنگ شده بزنیم که این هم ساده است.

مثال: سطر اول و ستون اول را انتخاب میکنیم و تمام این خانه ها را به جز خانه ی تقاطع رنگ میکنیم.