المپیاد سوالات ترکیبیات و مباحث ویژه !

[rezaezio]

پاسخ : مسابقه ترکیبیات

نیما ببین این مثال نقض برا حُکمت نیست ؟!
نقاط آبی : (1000, 0) ؛ (2000, 0) ؛ (3000, 0) ؛ (4000, 0) !
مهره ها : (1000, 1) ؛ (2000, 1) ؛ (3000, 1) ؛ (4000, 2) !
البته اگه حکم رو درست فهمیده باشم !

 

[mhjh]

پاسخ : مسابقه ترکیبیات

ه پلکان رو با حداقل چند مربع میشه افراز کرد که هیچ 2 مربعی هم پوشانی نداشته باشند ...
(پلکان 2 تایی میشه یه مربع 2*2 که خونه ی سمت راست, بالاش نیس)

من سوالو نمیفهمم ، خوب هر پلکان n تایی رو میشه با یک مربع n*n پوشاند که یک سری از خونه هاش نیست .

 

[مهدی]

پاسخ : مسابقه ترکیبیات

سوال ۴ روز دو رو توضیح بدید (سوال جدید .دی )
تو inoi پاسخنامه روز دوم هم هستش؟

 

[Dark Eagle]

پاسخ : مسابقه ترکیبیات

من سوالو نمیفهمم ، خوب هر پلکان n تایی رو میشه با یک مربع n*n پوشاند که یک سری از خونه هاش نیست .

مربع هایی که میزارید نباید از پلکان بزنه بیرون ...
هدف ما افراز پلکان به یه تعداد مربع هستش در نتیجه خونه های خارج از پلکان حساب نیستن ...

سوال ۴ روز دو رو توضیح بدید (سوال جدید .دی )

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

ولی در کل سوالا تو inoi هست کی حال داره این جا بنویسه

 

[senator77]

پاسخ : مسابقه ترکیبیات

ی چیز جالب
این سوالو من نفهمیدم یعنی چی که میخوای یک مربع n*n که گوشه سمت راست بالاش نیست رو با مربع های 2*2 پر کنی به طوری که هم پوشانی هم نداشته باشه و مربع های کوچک بیرون نزنن؟؟
خب آخه مربع n*n(اگه n زوج باشه)به چهار خودش بخش پذیر است و وقتی یک خونه رو میحذفی 100 درصد به 4 بخش پذیر نیست اونوقت ما میخواییم با مربع های 2*2 که هر مربع 4 تا از مجموع خونه ها کم میکنه کل مربع بزرگرو بپوشونیم؟
+خودمم نفهمیدم چی گفتم

 

[senator77]

پاسخ : مسابقه ترکیبیات

بعد ی سوال دیگه ازینا که زیر همه ی پست ها میاد کم رنگ هست؟فهمیدید کدوما رو میگم؟
خب چجوری ازونا رو مینویسید؟
منم ازونا میخوام :) :) :)
ویرایش:آخییییش فهمیدم بالاخره # # # # #

 

[mhjh]

پاسخ : مسابقه ترکیبیات

ی چیز جالب
این سوالو من نفهمیدم یعنی چی که میخوای یک مربع n*n که گوشه سمت راست بالاش نیست رو با مربع های 2*2 پر کنی به طوری که هم پوشانی هم نداشته باشه و مربع های کوچک بیرون نزنن؟؟
خب آخه مربع n*n(اگه n زوج باشه)به چهار خودش بخش پذیر است و وقتی یک خونه رو میحذفی 100 درصد به 4 بخش پذیر نیست اونوقت ما میخواییم با مربع های 2*2 که هر مربع 4 تا از مجموع خونه ها کم میکنه کل مربع بزرگرو بپوشونیم؟
+خودمم نفهمیدم چی گفتم

من چون خودم سوالو تازه فهمیدم ، الآن برات توضیح میدم . سوال میگه یه شکلی که شبیه پله است رو چجوری میشه به مربع هایی افراز کرد . (کمترین مربع )
یعنی این مربع ها فقط 2*2 نیستند ، 1*1 و 3*3 و ... هم میتونن باشن .
[]

 

[senator77]

پاسخ : مسابقه ترکیبیات

من چون خودم سوالو تازه فهمیدم ، الآن برات توضیح میدم . سوال میگه یه شکلی که شبیه پله است رو چجوری میشه به مربع هایی افراز کرد . (کمترین مربع )
یعنی این مربع ها فقط 2*2 نیستند ، 1*1 و 3*3 و ... هم میتونن باشن .
[]

خب الان به نظر شما جواب 2n-1 نیست؟یا من اشتباه میکنم؟
آخه اگه دقت کنید هر مربع اندازه ی یک عدد مربع کامل جا میگیره مثلا یک مربع 3*3 اندازه 9 تا جا میگیره که 9 هم مربع کامل هست از اونجایی که اون پله ای که تو سوال گفته یک مربع کامل هست که یدونه از مربع های کوچیکش نیست یعنی مربع کامل -1 خب اندازه ی 2n-2 تا باید از اون عدد کم کنیم تا به یک مربع کامل برسیم حالا اون مربع کاملو با یدونه پر میکنیم بقیه رو هم مجبوریم که با مربع های 1*1 پر کنیم خب حالا روش کلیش میشه که هر پله ای که n*n رو اول سمت چپ پایینش یک مربع n-1*n-1 میزاریم(یعنی الان فقط ردیف ستون آخر سمت راست میمونه و ردیف آخر سمت بالا) بعد بقیرو هم با 1*1 پر میکنیم
+ببخشید اگه بد توضیح دادم چون اولا اینی که گفتم واسه خودم اثبات شده نیست احساس میکنم دارم چرت میگم کمتر ازین هم میشه
دوما سوالش ی جورییه

 

[mhjh]

پاسخ : مسابقه ترکیبیات

من یه تابع بازگشتی برای حل سوال میگم اگه درسته میرم دنبال اثباتش.
F(X) D رو میگیرم تعداد کمترین مربع ایکس تایی :
اگر ایکس یک باشه :
F(X)=1
اگر ایکس بر دو بخش پذیر باشد :
F(X)=2*F(X/2)+1
اگر ایکس بر چهار بشه یک :
F(X)=2*F((X+1)/2)+1
اگر ایکس بر چهار بشه سه:
F(X)=2*F((X-1)/2)

یعنی
F(1)=1
F(2)=3
F(3)=3
F(4)=7
F(5)=6
F(6)=7
F(7)=7
F(8)=15
و ........
اگه جوابش اینه من ثابتش میکنم

 

[senator77]

پاسخ : مسابقه ترکیبیات

من یه تابع بازگشتی برای حل سوال میگم اگه درسته میرم دنبال اثباتش.
F(X) D رو میگیرم تعداد کمترین مربع ایکس تایی :
اگر ایکس یک باشه :
F(X)=1
اگر ایکس بر دو بخش پذیر باشد :
F(X)=2*F(X/2)+1
اگر ایکس بر چهار بشه یک :
F(X)=2*F((X+1)/2)+1
اگر ایکس بر چهار بشه سه:
F(X)=2*F((X-1)/2)

یعنی
F(1)=1
F(2)=3
F(3)=3
F(4)=7
F(5)=6
F(6)=7
F(7)=7
F(8)=15
و ........
اگه جوابش اینه من ثابتش میکنم

ی سوال یک پله ی 3 تایی رو چجوری با 3 تا مربع افراز میکنی؟
تازه فکر کنم بتونم اثبات کنم که همچین چیزی نمیشه همون پله ی 3 تایی رو در نظر بگیر خب تو اون رو که با مربع های 3*3 که نمیتونی بپوشونی قبول داری؟خب حالا ما باید از مربع های 2*2 و 1*1 استفاده کنیم حالا اگه از ی دونه 2*2 استفاده کنیم مجبوریم از 4 تا 1*1 استفاده کنیم که میشه 5 تا اگه بخوایم هم از 2 تا 2*2 استفاده کنیم که نمیشه(کلا برای گذاشتن مربع 2*2 اول سه تا راه داریم که توی هیچ کدوم ازین راه ها نمیتونیم مربع 2*2 بعدی رو جاگذاری کنیم)خب از 2 تا بیشتر 2*2 هم که نمیتونیم بزاریم یک چیز بدیهی است خب حالا فقط یک حالت میمونه اونم اینه که همش مربع های 1*1 بزاریم که میشه 8 تا
دیدی با 3 تا نشد
حداقل باید با استفاده از 5 تا مربع این کار رو کنی (طبق حالت بندی ها تونستیم حداقل رو بفهمیم)