darrande

Well-Known Member
ارسال ها
592
لایک ها
808
امتیاز
93
#41
پاسخ : ترکیبیات مرحله دویی

میشه مثالتون رو هم بگید؟! چون من هر جور حساب میکنم، 99 میشه...
اینم برای نود و هفت تا!

گفتم که برای نود وهشت نمیشه چون باید یک یا نود و نه وزنه پیدا شن که وزنشون Sباشه که اون موقع دیگه هیچ دو تا یا سه تا یا ... وجود ندارن که وزنشون sبشه
 

AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#42
پاسخ : ترکیبیات مرحله دویی

خب یه سوال هم من میذارم :
یک چدول 2002 در 2002 داریم که با اعداد یک تا 2^2002 پر شده است . آیا به ازای هر خانه از این جدول میتوان سه عدد a,b,c که هم سطر و یا هم ستون آن هستند (خود عدد آن جدول هم میتواند انتخاب شود) انتخاب کرد بطوریکه ab=c ؟؟
 

nima-1376

New Member
ارسال ها
63
لایک ها
53
امتیاز
0
#43
پاسخ : ترکیبیات مرحله دویی

خب یه سوال هم من میذارم :
یک چدول 2002 در 2002 داریم که با اعداد یک تا 2^2002 پر شده است . آیا به ازای هر خانه از این جدول میتوان سه عدد a,b,c که هم سطر و یا هم ستون آن هستند (خود عدد آن جدول هم میتواند انتخاب شود) انتخاب کرد بطوریکه ab=c ؟؟
AoPS Forum - 2002*2002 • Art of Problem Solving
 

AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#44
پاسخ : ترکیبیات مرحله دویی

این هست اما من یه راه حل دیگه دارم که تو mathlinks مذمونی ازش ندیدم:
جایگاه اعداد 1 تا 2001 را در نظر میگیریم چون 2002 ستون و سطر داریم پس حداقل یک سطر و یک ستون داریم که از اعدادی بجز اعداد 1 تا 2001 تشکیل شده است.
یعنی از اعداد 2002 تا 2002*2002 تشکیل شده است.
چون حداقل مقدار ab برابر 2002*2003 است و حداکثر مقدار c برابر 2002*2002 است پس این کار امکان پذیر نیست چون در آن به ازای خانه تقاطع آن سطر و ستون اعداد a,b,c وجود ندارند که ab=c
 

AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#45
پاسخ : ترکیبیات مرحله دویی

رفقا !
دیگه سوال نمیذارید ؟؟؟
 

ash1374

New Member
ارسال ها
253
لایک ها
421
امتیاز
0
#46
پاسخ : ترکیبیات مرحله دویی

اینم یه سوال جدید. اگر استقبال بشه بازم سوال میگذاریم ان شا الله:
5 خط و 5 نقطه در صفحه داریم. ثابت کنید دو نقطه و دو خط از آن ها وجود دارند که نقاط روی خطوط نیستند.
 

AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#47
پاسخ : ترکیبیات مرحله دویی

اینم یه سوال جدید. اگر استقبال بشه بازم سوال میگذاریم ان شا الله:
5 خط و 5 نقطه در صفحه داریم. ثابت کنید دو نقطه و دو خط از آن ها وجود دارند که نقاط روی خطوط نیستند.
خط ها رو به ترتیب
می نامیم .
میایم نقطه ها رو برمیداریم و خودمون میچینیم . بدترین حالت حالتی هستش که نقاط رو نقطه همرسی دو خط باشند و بدتر از اون حالت حالتی هستش که همه خطوط همرس باشند و یکی از نقاط ما همون نقطه همرسی باشه
پس 4 تا نقطه داریم الان و پنج خط همرس.در واقع اگه همه همرس نباشند ما باید بیش از یه نقطه مصرف کنیم برای پر کردن نقطه همرسی ها.
. دو خطی رو که از همه کمتر نقطه هست روشون رو انتخاب میکنیم که مجموع نقاط روی اونها حداکثر سه هستش ( یکی نقطه همرسی هستش و اگر هم روی هر خط یه نقطه باشه اونوقت حالت حداکثر هر خط هستش که میشه سه تا ) . حالا این دو تا خط رو انتخاب میکنیم و چون حداکثر سه تا نقطه روشون بود پس حداقل دو تا نقطه داریم که روی این دوتا نیست پس اون دو تا نقطه رو انتخاب میکنیم.
البته میدونم راه حلم یه جوریه !!!
 
آخرین ویرایش توسط مدیر

math1998

New Member
ارسال ها
336
لایک ها
224
امتیاز
0
#48
پاسخ : ترکیبیات مرحله دویی

فرض کنید a زیرمجموعه ای 16 عضوی از {2,1...,106} باشد به طوری که تفاضل هیچ دو عضوی برابر 6,9,12,15,18,21 نباشد . ثابت کنید تفاضل 2 عضو از a برابر 3 است .
 

ash1374

New Member
ارسال ها
253
لایک ها
421
امتیاز
0
#49
پاسخ : ترکیبیات مرحله دویی

خط ها رو به ترتیب
می نامیم .
میایم نقطه ها رو برمیداریم و خودمون میچینیم . بدترین حالت حالتی هستش که نقاط رو نقطه همرسی دو خط باشند و بدتر از اون حالت حالتی هستش که همه خطوط همرس باشند و یکی از نقاط ما همون نقطه همرسی باشه
پس 4 تا نقطه داریم الان و پنج خط همرس.در واقع اگه همه همرس نباشند ما باید بیش از یه نقطه مصرف کنیم برای پر کردن نقطه همرسی ها.
. دو خطی رو که از همه کمتر نقطه هست روشون رو انتخاب میکنیم که مجموع نقاط روی اونها حداکثر سه هستش ( یکی نقطه همرسی هستش و اگر هم روی هر خط یه نقطه باشه اونوقت حالت حداکثر هر خط هستش که میشه سه تا ) . حالا این دو تا خط رو انتخاب میکنیم و چون حداکثر سه تا نقطه روشون بود پس حداقل دو تا نقطه داریم که روی این دوتا نیست پس اون دو تا نقطه رو انتخاب میکنیم.
البته میدونم راه حلم یه جوریه !!!
اصلا بدیهی نیست که این بدترین حالته. این که برای پر کردن همرسی ها کمترین نقاط تو این حالت بدست میاد دلیل نمیشه. شاید مثلا تو حالتی که سه تا توی یه نقطه همرس باشن و دو تا توی یه نقطه دیگه اتفاقات دیگه ای بیفته و ... . خلاصه سعی کنید هیچ وقت این جور راه حل ها رو بکار نبرید. معمولا تو مرحله دو نمره ای نمیگیرین. هر ادعایی باید دقیق ثابت بشه مگر اینکه جز دانسته های قبلیمون باشه. پس بیشتر دقت کنید:3:
 

AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#50
پاسخ : ترکیبیات مرحله دویی

اصلا بدیهی نیست که این بدترین حالته. این که برای پر کردن همرسی ها کمترین نقاط تو این حالت بدست میاد دلیل نمیشه. شاید مثلا تو حالتی که سه تا توی یه نقطه همرس باشن و دو تا توی یه نقطه دیگه اتفاقات دیگه ای بیفته و ... . خلاصه سعی کنید هیچ وقت این جور راه حل ها رو بکار نبرید. معمولا تو مرحله دو نمره ای نمیگیرین. هر ادعایی باید دقیق ثابت بشه مگر اینکه جز دانسته های قبلیمون باشه. پس بیشتر دقت کنید:3:
خب بله حرف شما کاملا متین هستش . خودمم هم همین طوری فکر میکردم . بخاطر همین گفتم که یه جوریه !!
خب حالا میایم اون دو تا خطی رو انتخاب می کنیم که از همه کمتر نقطه رو شون هست.
اگه نشون بدیم مجموع نقاط روی این دوتا حداکثر 3 تاست مساله حل میشه چون حداقل دو نقطه هست که روی این دوتا خط نیست.
پس فرض خلف می زنیم میگیم حداقل 4 تا نقطه رو این دو خط وجود داشته باشه.اگه یکی از این چهار تا نقطه همرسی باشه پس هر کدوم یکی نقطه دارند و یه نقطه هم همرسی هست ( همرسی رو دو بار شمردیم.)اینطوری دقیقا دو نقطه وجود داره که بیرون از این خطوط هستش پس مساله حل شد
اما اگه نقطه همرسی این دو خط نقطه ما نباشه پس یا هرکدوم به تنهایی دو تا دارند یا یکی سه تا داره اون یکی یکی یا یکی چهار تا داره اون یکی هیچی
حالت آخر به راحتی تناقض داره چون اول گفتیم خطوطی رو انتخاب کردیم که از همه کمتر نقطه دارند پس بقیه سه تاخط دیگه حداقل چهار تا نقطه رو دارند پس باید روی اون خطی که چهارتا نقطه داره منطبق شوند که تناقضه
حالت دیگه اینه که یکی سه تا باشه اون یکی یکی،پس بقیه سه تا خط دیگه حداقل سه تا نقطه دارند.این هم تناقض داره . اگه شکلشو بکشید خیلی بدیهیه.
حالا اگه دوتا دوتا باشه . پس بقیه حداقل دو تا دارند.
حالا اون نقطه ای که بیرون هستش رو در نظر میگیریم و اسمشو میذاریم p
حالا الان سه تا خط دیگه باید باشه که حداقل از دو تا نقطه بگذره پس ما الان 8 تا خط میتونیم داشته باشیم که سه تاش مراد هست (اینم اگه شکل بکشید متوجه منظورم میشید)
این رو هم با حالت بندی رو تعداد خطوطی که از p میگذره بشه حل کرد مثلا یکی ، دوتا یا سه تا.
 

ash1374

New Member
ارسال ها
253
لایک ها
421
امتیاز
0
#51
پاسخ : ترکیبیات مرحله دویی

خب بله حرف شما کاملا متین هستش . خودمم هم همین طوری فکر میکردم . بخاطر همین گفتم که یه جوریه !!
خب حالا میایم اون دو تا خطی رو انتخاب می کنیم که از همه کمتر نقطه رو شون هست.
اگه نشون بدیم مجموع نقاط روی این دوتا حداکثر 3 تاست مساله حل میشه چون حداقل دو نقطه هست که روی این دوتا خط نیست.
پس فرض خلف می زنیم میگیم حداقل 4 تا نقطه رو این دو خط وجود داشته باشه.اگه یکی از این چهار تا نقطه همرسی باشه پس هر کدوم یکی نقطه دارند و یه نقطه هم همرسی هست ( همرسی رو دو بار شمردیم.)اینطوری دقیقا دو نقطه وجود داره که بیرون از این خطوط هستش پس مساله حل شد
اما اگه نقطه همرسی این دو خط نقطه ما نباشه پس یا هرکدوم به تنهایی دو تا دارند یا یکی سه تا داره اون یکی یکی یا یکی چهار تا داره اون یکی هیچی
حالت آخر به راحتی تناقض داره چون اول گفتیم خطوطی رو انتخاب کردیم که از همه کمتر نقطه دارند پس بقیه سه تاخط دیگه حداقل چهار تا نقطه رو دارند پس باید روی اون خطی که چهارتا نقطه داره منطبق شوند که تناقضه
حالت دیگه اینه که یکی سه تا باشه اون یکی یکی،پس بقیه سه تا خط دیگه حداقل سه تا نقطه دارند.این هم تناقض داره . اگه شکلشو بکشید خیلی بدیهیه.
حالا اگه دوتا دوتا باشه . پس بقیه حداقل دو تا دارند.
حالا اون نقطه ای که بیرون هستش رو در نظر میگیریم و اسمشو میذاریم p
حالا الان سه تا خط دیگه باید باشه که حداقل از دو تا نقطه بگذره پس ما الان 8 تا خط میتونیم داشته باشیم که سه تاش مراد هست (اینم اگه شکل بکشید متوجه منظورم میشید)
این رو هم با حالت بندی رو تعداد خطوطی که از p میگذره بشه حل کرد مثلا یکی ، دوتا یا سه تا.
هنوز مشکلاتی داره که میشه درست کرد البته.

سوال بعدی : 8 رخ در صفحه ی شطرنج 8 در 8 قرار دارند که همدیگر را تهدید نمی کنند. ثابت کنید تعداد رخ هایی که در خانه های سیاه جدول قرار دارند زوج است.
 

AHZolfaghari

Well-Known Member
ارسال ها
935
لایک ها
1,654
امتیاز
93
#52
پاسخ : ترکیبیات مرحله دویی

هنوز مشکلاتی داره که میشه درست کرد البته.

سوال بعدی : 8 رخ در صفحه ی شطرنج 8 در 8 قرار دارند که همدیگر را تهدید نمی کنند. ثابت کنید تعداد رخ هایی که در خانه های سیاه جدول قرار دارند زوج است.
هر ستون و ردیف را شماره گذاری میکنیم و در خانه ای که در ستون i و سطر j هست عدد i+j را مینویسیم بدین ترتیب مجموع اعداد خانه ی این رخ ها میشه 72.
حالا میدونیم اعداد خانه سیاه فرد هستند و سفید ها زوج هستند پس اگه تعداد رخ های سفید فرد باشه مجموع اعداد رخ ها فرد میشه که تناقضه پس باید زوج باشه
 

nima-1376

New Member
ارسال ها
63
لایک ها
53
امتیاز
0
#53
پاسخ : ترکیبیات مرحله دویی

حسن و حسین میخواند 25 سکه به ارزش 1,2,...,25 را بین خود تقسیم کنند.در هر مرحله یکی از آنها یک سکه انتخاب میکند و نفر دیگر تصمیم میگیرد که سکه را چه کسی بردارد.اولین انتخاب را حسن انجام میدهد و پس از آن در هر مرحله کسی سکه انتخاب میکند که در آن لحظه پول بیشتری داشته باشد.اگر در مرحله ای هر دو نفر به یک اندازه پول داشته باشند،کسی که در مرحله قبل سکه انتخاب کره بود،سکه انتخاب میکند.در پایان کسی که پول بیشتری داشته باشد،سکه انتخاب میکند.چه کسی استراتژی برد دارد؟
راهنمایی:به ذسته های روبه رو تقسیم کنید
)1و25()2و24(و...)12و14)و دسته 13
 

aminanvari

New Member
ارسال ها
2
لایک ها
0
امتیاز
0
#54
حسن و حسین

نفر دوم (حسن) استراتژی برد دارد:

فرض کنید در اولین حرکت نفر اول (حسین) سکه ی x را انتخاب می کند.
اگر نفر دوم (حسن) این سکه را برای خود برداشت و در ادامه ی بازی نتوانست راهی برای بردن پیدا کند،
این سکه را به نفر اول (حسین) می دهد. در این صورت از مرحله ی بعد جای حسن و حسین عوض می شود و نفر اول (حسین) نمی تواند ببرد.

------- سوال جدید --------

گرافی همبند و 1000 راسی داریم ثابت کنید می توان 90 راس از این گراف را می توان رنگ کرد ، به طوری که فاصله ی هر راس دیگر تا یکی از رئوس رنگی حداکثر برابر 10 باشد.
مثالی ارائه دهید که نشان بدهد 90 بهترین کران است.
 
آخرین ویرایش توسط مدیر
بالا