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

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

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : مسابقه ترکیبیات

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

mhjh

کاربر فوق‌فعال
ارسال‌ها
158
امتیاز
207
نام مرکز سمپاد
شهید قدوسی قم
شهر
قم
پاسخ : مسابقه ترکیبیات

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


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

مهدی

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,112
امتیاز
7,379
نام مرکز سمپاد
علامه‌حلی
شهر
تهران
مدال المپیاد
کامپیوتر
دانشگاه
دانشگاه تهران. :دی
رشته دانشگاه
آمار. :دی
پاسخ : مسابقه ترکیبیات

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

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
657
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : مسابقه ترکیبیات

به نقل از mhjh :
من سوالو نمیفهمم ، خوب هر پلکان n تایی رو میشه با یک مربع n*n پوشاند که یک سری از خونه هاش نیست . :-?
مربع هایی که میزارید نباید از پلکان بزنه بیرون ...
هدف ما افراز پلکان به یه تعداد مربع هستش در نتیجه خونه های خارج از پلکان حساب نیستن ...

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

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

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

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

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

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

mhjh

کاربر فوق‌فعال
ارسال‌ها
158
امتیاز
207
نام مرکز سمپاد
شهید قدوسی قم
شهر
قم
پاسخ : مسابقه ترکیبیات

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

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

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

به نقل از mhjh :
من چون خودم سوالو تازه فهمیدم ، الآن برات توضیح میدم . سوال میگه یه شکلی که شبیه پله است رو چجوری میشه به مربع هایی افراز کرد . (کمترین مربع )
یعنی این مربع ها فقط 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 پر میکنیم
+ببخشید اگه بد توضیح دادم چون اولا اینی که گفتم واسه خودم اثبات شده نیست احساس میکنم دارم چرت میگم کمتر ازین هم میشه
دوما سوالش ی جورییه
 
  • لایک
امتیازات: m.m.r

mhjh

کاربر فوق‌فعال
ارسال‌ها
158
امتیاز
207
نام مرکز سمپاد
شهید قدوسی قم
شهر
قم
پاسخ : مسابقه ترکیبیات

من یه تابع بازگشتی برای حل سوال میگم اگه درسته میرم دنبال اثباتش.
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

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

به نقل از 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
و ........
اگه جوابش اینه من ثابتش میکنم

ی سوال یک پله ی 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 تا مربع این کار رو کنی (طبق حالت بندی ها تونستیم حداقل رو بفهمیم) :-" :-" :-"
 
  • لایک
امتیازات: m.m.r

mhjh

کاربر فوق‌فعال
ارسال‌ها
158
امتیاز
207
نام مرکز سمپاد
شهید قدوسی قم
شهر
قم
پاسخ : مسابقه ترکیبیات

به نقل از senator77 :
ی سوال یک پله ی 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 تا مربع این کار رو کنی (طبق حالت بندی ها تونستیم حداقل رو بفهمیم) :-" :-" :-"

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

* * *
* *
*

یه همچین شکلی البته دوران یافتش .
 

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

آها خو من کلا این سوالو نفهمیده بودم فکر کنم رابطه ی بازگشتیت درسته میتونی اثباتش کنی؟
 
  • لایک
امتیازات: m.m.r

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

الآن فرض کنیم سوال رو حل کردیم
چه طوری باید ثابت کنیم عددمون کم ترین مقداره؟؟
 

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

به نقل از amoo.majid :
الآن فرض کنیم سوال رو حل کردیم
چه طوری باید ثابت کنیم عددمون کم ترین مقداره؟؟
اینم سوال خوبیه کلا سوالش به دلم نمیشه نمیدونم چرا ولی باهاش حال نکردم :D :D
 
  • لایک
امتیازات: m.m.r

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

به نقل از senator77 :
اینم سوال خوبیه کلا سوالش به دلم نمیشه نمیدونم چرا ولی باهاش حال نکردم :D :D
دستت درد نکنه :|
خب تو مرحله 2 باید بنویسی
اگر با این حال نکنی با مرحله 2 هم نباید حال کنی دیگه ;;)
 

علیمپو

بچّه سنّی
ارسال‌ها
670
امتیاز
4,857
نام مرکز سمپاد
حلی۲
شهر
تهران
سال فارغ التحصیلی
1396
پاسخ : مسابقه ترکیبیات

به نقل از amoo.majid :
دستت درد نکنه :|
خب تو مرحله 2 باید بنویسی
اگر با این حال نکنی با مرحله 2 هم نباید حال کنی دیگه ;;)

مجید جان دلبندم خون خودتو کثیف نکن ! یه کاریش می کنه دیگه !
 

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

به نقل از amoo.majid :
دستت درد نکنه :|
خب تو مرحله 2 باید بنویسی
اگر با این حال نکنی با مرحله 2 هم نباید حال کنی دیگه ;;)
آره اینو که میدونم بخاطر همین از همین الان دست به دعا زدم که تو مرحله دو سال بعد و بعدش ازین سوالا ندن که خوشم نیاد اگه بدن عمرا بتونم حل کنم :(( :(( :(( :((
 
  • لایک
امتیازات: m.m.r

senator77

کاربر نیمه‌حرفه‌ای
ارسال‌ها
194
امتیاز
302
نام مرکز سمپاد
علامه حلی 2
شهر
تهران
مدال المپیاد
ایشالا سال بعد طلا
دانشگاه
شریف دیگه
رشته دانشگاه
نرم افزار دیگه
پاسخ : مسابقه ترکیبیات

:-/
به نقل از am-_-ma :
مجید جان دلبندم خون خودتو کثیف نکن ! یه کاریش می کنه دیگه !
علی رفتید گیم؟
 
  • لایک
امتیازات: m.m.r

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

به نقل از senator77 :
:-/علی رفتید گیم؟
این جا رو با wecaht اشتباه گرفتی؟
پ خ رو واسه همین موقعا گذاشتن
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : مسابقه ترکیبیات

به نقل از 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
و ........
اگه جوابش اینه من ثابتش میکنم
F(8)=12
:-??
 
بالا