سوال روسیه 1993کلاس 10ام

[shamsaddini]

ان سوال چطور حل میشه؟:216::216:
یک مربع به ظلع n را به مربع هایی به ظلع واحد تقسیم کرده ایم ؛ بیشینه ی nچیست برای آنکه : بتوان n مربع واحد را نشان دار کرد به طوریکه هر مستطیل که مساحتش از n کمتر نباشد دست کم شامل یک خانه ی نشان دار باشد؟

 

[jei javad]

پاسخ : سوال روسیه 1993کلاس 10ام

راهنمایی
اولا که میدونیم تو هر سطری و هر ستونی دقیقا یک خونه نشون دار بشه . خونه نشاندار شده سطر 2 رو در نظر بگیرید و i ستون متوالیی رو در نظر بگیرید که شامل نقطه نشون دار سطر 2 هس ولی شامل خونه نشون دار سطر 1 نیس.
تو این مستطیل n*i ((جدید))(به ازای i های خاصی) ثابت میکنیم هست مستطیل i*n/i ی که توش همه خونه ها بی نشونن.
تو این مستطیل جیدیمون اختلاف عدد سطر(یا همون عرض) نقطه موجود در مستطیل جدید به نام k که در سطر l واقع است تا نقطه موجود در سطر j که تو مستطیل جدید واقع است( به طوری که j کوچکترین عددی است با این خاصیت به طوری که j>l ) را

بنامید .
حالا

(واضحه که

چون تو مستطیل جدید حداکثر i تا خونه نشون داره) پس طبق اصل لانه کبوتری هست x-{i ای که حداقل برابر

هست کافیه

میتونید i رو طوری انتخاب کنید که اینطوری بشه .