ماراتن ترکیبیات(پیشرفته)
پاسخ : ماراتن ترکیبیات(پیشرفته)
میانگین دوست مشترکهای هر دو نفر رو حساب میکنیم.یه ماتریس میکشیم رو عرض
A1A2,...,A99A100(دوتایی ها!) و رو طول
Aiها رو(تکی!!) مینویسیم .جمع هر ستون میشه
2 از 70و میانگین سطرا میشه
[سقف (2( از 70 ضرب در 100) تقسیم بر 2 از 100)]=48پس حتما سطری وجود داره که از 48 بیشتره یعنی دو نفر هستن که دوست مشترکاشون حداقل 49 تاس
معذرت .LaTeX ارر(error!!!)میده
میانگین دوست مشترکهای هر دو نفر رو حساب میکنیم.یه ماتریس میکشیم رو عرض
معذرت .LaTeX ارر(error!!!)میده
آخرین ویرایش توسط مدیر
پاسخ : ماراتن ترکیبیات(پیشرفته)
من متوجه نشدم...یکم بیشتر میشه توضیح بدین؟
میانگین دوست مشترکهای هر دو نفر رو حساب میکنیم.یه ماتریس میکشیم رو عرض
A1A2,...,A99A100(دوتایی ها!) و رو طول
Aiها رو(تکی!!) مینویسیم .جمع هر ستون میشه
2 از 70و میانگین سطرا میشه
[سقف (2( از 70 ضرب در 100) تقسیم بر 2 از 100)]=48پس حتما سطری وجود داره که از 48 بیشتره یعنی دو نفر هستن که دوست مشترکاشون حداقل 49 تاس
معذرت .LaTeX ارر(error!!!)میده
معذرت .LaTeX ارر(error!!!)میده
پاسخ : ماراتن ترکیبیات(پیشرفته)
شرمنده...نمیدونم چرا اینجوری شده...
میانگین دوست مشترکهای هر دو نفر رو حساب میکنیم.یه ماتریس میکشیم رو عرض Aiها رو(تکی!!) مینویسیم و رو طولA1A2,...,A99A100(دوتایی ها!!)
جمع هر ستون میشه2 از 70
و میانگین سطرا میشه سقف (2( از 70 ضرب در 100) تقسیم بر 2 از 100)= 48
پس حتما سطری وجود داره که از 48 بیشتره
یعنی دو نفر هستن که دوست مشترکاشون حداقل 49 تاس...
شرمنده...نمیدونم چرا اینجوری شده...
میانگین دوست مشترکهای هر دو نفر رو حساب میکنیم.یه ماتریس میکشیم رو عرض Aiها رو(تکی!!) مینویسیم و رو طولA1A2,...,A99A100(دوتایی ها!!)
جمع هر ستون میشه2 از 70
و میانگین سطرا میشه سقف (2( از 70 ضرب در 100) تقسیم بر 2 از 100)= 48
پس حتما سطری وجود داره که از 48 بیشتره
یعنی دو نفر هستن که دوست مشترکاشون حداقل 49 تاس...
پاسخ : ماراتن ترکیبیات(پیشرفته)
ساختمان روشنایی تعدادی زیادی چراغ و کلید دارد.هر کلید به بعضی از چراغ ها متصل است و با زدن آن وضعیت همه ی آن چراغ ها تغییر میکند(یعنی اگر خاموش بودند،روشن و بلعکس میشوند)در ضمن میدانیم که هر چراغ حداقل به یک کلید متصل است.نشان دهید اگر در ابتدا همه ی چراغ ها خاموش باشند،میتوان با زدن بعی از کلید ها به حالتی رسید که بیش از نیمی از چراغ ها روشن باشند.(مرحله دوم المپیاد کامپیوتر 88)
ساختمان روشنایی تعدادی زیادی چراغ و کلید دارد.هر کلید به بعضی از چراغ ها متصل است و با زدن آن وضعیت همه ی آن چراغ ها تغییر میکند(یعنی اگر خاموش بودند،روشن و بلعکس میشوند)در ضمن میدانیم که هر چراغ حداقل به یک کلید متصل است.نشان دهید اگر در ابتدا همه ی چراغ ها خاموش باشند،میتوان با زدن بعی از کلید ها به حالتی رسید که بیش از نیمی از چراغ ها روشن باشند.(مرحله دوم المپیاد کامپیوتر 88)
پاسخ : ماراتن ترکیبیات(پیشرفته)
سوال لامپ ها وکلید ها
اگه تعداد لامپ ها n و تعداد کلید ها m باشه
دوگونه شماری می کنیم
یه جدول دو به توان ام در ان در نظر می گیریم
که هر سطری از اون یه حالت از روشن و خاموش بود ن کلید هاست
و هر ستونی هم یکی از لامپا رو نشون میده
خونه ی i,jیک است اگرو تنها اگر تو وضعیت i لامپ j روشن باشه در غیر این صورت صفره
خب حالا تعداد یک ها رو می شماریم
هر لامپی دست کم تو دو به توان ام منهای یک وضعیت روشنه(ثابت کنین)
و خب ان تا لامپ داریم پس تعداد یک ها دست کم میشه ان ضربدر دو به توان ام منهای یک
پس طبق لانه سطری(وضعیتی) هست که توش نصف لامپاروشنن
سوال لامپ ها وکلید ها
اگه تعداد لامپ ها n و تعداد کلید ها m باشه
دوگونه شماری می کنیم
یه جدول دو به توان ام در ان در نظر می گیریم
که هر سطری از اون یه حالت از روشن و خاموش بود ن کلید هاست
و هر ستونی هم یکی از لامپا رو نشون میده
خونه ی i,jیک است اگرو تنها اگر تو وضعیت i لامپ j روشن باشه در غیر این صورت صفره
خب حالا تعداد یک ها رو می شماریم
هر لامپی دست کم تو دو به توان ام منهای یک وضعیت روشنه(ثابت کنین)
و خب ان تا لامپ داریم پس تعداد یک ها دست کم میشه ان ضربدر دو به توان ام منهای یک
پس طبق لانه سطری(وضعیتی) هست که توش نصف لامپاروشنن
پاسخ : ماراتن ترکیبیات(پیشرفته)
دوستان یه سری سوال گراف هم هست بد نیست به اونام یه نگاهی بندازین
http://www.irysc.com/forum/t15840/#post194999
دوستان یه سری سوال گراف هم هست بد نیست به اونام یه نگاهی بندازین
http://www.irysc.com/forum/t15840/#post194999
پاسخ : ماراتن ترکیبیات(پیشرفته)
یه استقرا ساده روی تعداد کلید ها میخواد.
فرض کنید برای kکلید برقرار باشه
برای K+1 هم ، کلیدK+1رو بگیرید و همه لامپ های متصل به اون رو تو یه دسته کنید
طبق فرض استقرا با بقیه کلید ها میتونیم نصف بقیه لامپها رو روشن کنیم
حالا اگه نصف لامپهای دسته ی ما روشن بود که حله اگه نبود این کلید K+1رو یه بار بزنید.
سوال بعدی:
دایره ای با محیط 1393 داریم. که روی آن 1393 نقطه را با رنگ آبی رنگ میکنیم.
دایره ای مشابه با همان دایره داریم با این تفاوت که به جای نقاط، تعدادی کمان از محیط دایره را با رنگ آبی رنگ میکنیم بدین صورت که مجموع طول کمان ها از یک کمتر شود.
ثابت کنید دایره دوم را میتوانیم طوری روی دایره اول قرار دهیم تا هیچ نقطه ای از دایره اول زیر کمانی از دایره ی دوم نباشد
یه استقرا ساده روی تعداد کلید ها میخواد.
فرض کنید برای kکلید برقرار باشه
برای K+1 هم ، کلیدK+1رو بگیرید و همه لامپ های متصل به اون رو تو یه دسته کنید
طبق فرض استقرا با بقیه کلید ها میتونیم نصف بقیه لامپها رو روشن کنیم
حالا اگه نصف لامپهای دسته ی ما روشن بود که حله اگه نبود این کلید K+1رو یه بار بزنید.
سوال بعدی:
دایره ای با محیط 1393 داریم. که روی آن 1393 نقطه را با رنگ آبی رنگ میکنیم.
دایره ای مشابه با همان دایره داریم با این تفاوت که به جای نقاط، تعدادی کمان از محیط دایره را با رنگ آبی رنگ میکنیم بدین صورت که مجموع طول کمان ها از یک کمتر شود.
ثابت کنید دایره دوم را میتوانیم طوری روی دایره اول قرار دهیم تا هیچ نقطه ای از دایره اول زیر کمانی از دایره ی دوم نباشد
پاسخ : ماراتن ترکیبیات(پیشرفته)
خب داداش دقیق ننوشتیا( به این اشاره نکردی)
ببین اگه با بقیه تغییرات ایجاد کنیم ممکنه لامپای کلید K+1 یه سری شون روشن بشن
باید بگی که میشه تو دسته k+1 میشه نصفی رو لا اقل روشن کردو اون طرف هم نصفی روشنه پس در کل نصفی روشنه
---- دو نوشته به هم متصل شده است ----
بیا و دایره دومیه رو بنداز رو دایره اولیه و یه دور کامل بچرخونش
در حین این چرخوندن بعضی وختا بعضی نقطه ها از دایره اول زیر یه کمان می افتادن
حالا بیا رو هر نقطه بنویس چن بار زیر یه کمان افتاده
از یه طرف چون مجموع کمان ها کوچک تر از 1393 است و هر نقطه ای از کمان ها هم حداکثر 1393 بار روی نقه ی دایره زیریش افتاده پس این مجموع میشه کم تر از 1393
از طرف دیگه هر نقطه از کمانای دایره دوم دقیقا 1393 بار روی یه نقطه از دایره زیریش افتاده پس این مجموع میشه دقیقن 1393
و تناقض.
خب داداش دقیق ننوشتیا( به این اشاره نکردی)
ببین اگه با بقیه تغییرات ایجاد کنیم ممکنه لامپای کلید K+1 یه سری شون روشن بشن
باید بگی که میشه تو دسته k+1 میشه نصفی رو لا اقل روشن کردو اون طرف هم نصفی روشنه پس در کل نصفی روشنه
---- دو نوشته به هم متصل شده است ----
بیا و دایره دومیه رو بنداز رو دایره اولیه و یه دور کامل بچرخونش
در حین این چرخوندن بعضی وختا بعضی نقطه ها از دایره اول زیر یه کمان می افتادن
حالا بیا رو هر نقطه بنویس چن بار زیر یه کمان افتاده
از یه طرف چون مجموع کمان ها کوچک تر از 1393 است و هر نقطه ای از کمان ها هم حداکثر 1393 بار روی نقه ی دایره زیریش افتاده پس این مجموع میشه کم تر از 1393
از طرف دیگه هر نقطه از کمانای دایره دوم دقیقا 1393 بار روی یه نقطه از دایره زیریش افتاده پس این مجموع میشه دقیقن 1393
و تناقض.
- ارسال ها
- 152
- لایک ها
- 61
- امتیاز
- 0
پاسخ : ماراتن ترکیبیات(پیشرفته)
اولا بر اساس اصل لانه کبوتری میدانیم قطاعی وجود دارد که روی آن قطاع حداقل دو قورباغه هستند
هر گاه در خانه ای در قطاع های مذکور 1 قورباغه باشد آن خانه
اگر خالی شود حتما باید در یکی از خانه های مجاورش دو قورباغه باشند که مشخصا پس از یک حرکت خانه پر میشود
پس میتوان گفت هیچگاه خانه ای پرخالی نمیشود!
حال نشان میدهیم که پس از تعدادی حرکت حداقل یک خانه خالی پر میشود
با توجه به اینکه میدانیم برای تغییر در تعداد غورباقه (!) های یک قطاع حتما باید در یکی از قطاع های مجاور بیش از یک قورباغه موجود باشد
همچنین میدانیم حتما قطاعی پر وجود دارد که در کنار آن قطاعی خالی است (در غیر این صورن حکم بدیهی است)
نزدیکترین قطاعی را که به مجموعه i از قطاع های پر مجاور که خود قطاع مذکور خالی است در نظر میگیریم
مجموعه i:مجموعه ای از قطاع ها که تعداد غورباقه ها در آن بیشتر از خود قطاع ها باشدو هیچ قطاعی خالی نیسن (چنین مجموعه ای حتما وجود دارد) این مجموعه ممکن است تک عضوی باشد
قطاع مذکور در دو سطر بالا حتما پس از تعدادی حرکت پر میشود زیرا با هر حرکت به تعداد غورباقه های یکی از خانه های پر مجموعه اضافه میشود و سپس دوباره به وضعیت قبلی بر میگردد
به جز قطاع پری که در کنار یکی از قطاع های خالی قرار دارد
این قطاع پس از اضافه شدن قورباغه یکی از آنها را به قطاع خالی میدهد و بدین ترتیب قطاع خالی پر میشود
با توجه به این که میدانیم هر قطاع پر خالی نمیشود پس تعداد قطاع های پر افزایش میابد تا به بیش از نصف برسد
و بدین ترتیب حکم ثابت میشود
:157::224:
اولا بر اساس اصل لانه کبوتری میدانیم قطاعی وجود دارد که روی آن قطاع حداقل دو قورباغه هستند
هر گاه در خانه ای در قطاع های مذکور 1 قورباغه باشد آن خانه
اگر خالی شود حتما باید در یکی از خانه های مجاورش دو قورباغه باشند که مشخصا پس از یک حرکت خانه پر میشود
پس میتوان گفت هیچگاه خانه ای پرخالی نمیشود!
حال نشان میدهیم که پس از تعدادی حرکت حداقل یک خانه خالی پر میشود
با توجه به اینکه میدانیم برای تغییر در تعداد غورباقه (!) های یک قطاع حتما باید در یکی از قطاع های مجاور بیش از یک قورباغه موجود باشد
همچنین میدانیم حتما قطاعی پر وجود دارد که در کنار آن قطاعی خالی است (در غیر این صورن حکم بدیهی است)
نزدیکترین قطاعی را که به مجموعه i از قطاع های پر مجاور که خود قطاع مذکور خالی است در نظر میگیریم
مجموعه i:مجموعه ای از قطاع ها که تعداد غورباقه ها در آن بیشتر از خود قطاع ها باشدو هیچ قطاعی خالی نیسن (چنین مجموعه ای حتما وجود دارد) این مجموعه ممکن است تک عضوی باشد
قطاع مذکور در دو سطر بالا حتما پس از تعدادی حرکت پر میشود زیرا با هر حرکت به تعداد غورباقه های یکی از خانه های پر مجموعه اضافه میشود و سپس دوباره به وضعیت قبلی بر میگردد
به جز قطاع پری که در کنار یکی از قطاع های خالی قرار دارد
این قطاع پس از اضافه شدن قورباغه یکی از آنها را به قطاع خالی میدهد و بدین ترتیب قطاع خالی پر میشود
با توجه به این که میدانیم هر قطاع پر خالی نمیشود پس تعداد قطاع های پر افزایش میابد تا به بیش از نصف برسد
و بدین ترتیب حکم ثابت میشود
:157::224: