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

[ftmhg]

دقیقا اثباتی که گفتی رو به جای اینکه یک دایره اضافه کنی ( که پوشایی از بین بره ) بیا بالاترین دایره رو حذف کن اسقرا بزن دایره رو اضافه کن و حتی دقیقا تعویض هایی که باید انجام داد رو هم پاسخنامه ای که کتاب داشت و نوشتیش لازم نیست دست بزنیم . تنها دو تا مشکل داریم یکی اینکه پایه یک کل عملیات هارو پوشش نمیده که پایه رو میگذاریم ۲
یکی اینکه بالاترین دایره تعریف میشه؟ چون فضا نامتناهیه . راه اینه که دایره با بالاترین مرکز رو در نظر بگیریم و این چرا قابل تعریفه ؟ چون با فضا مقایسه نمیشه با دایره هامون مقایسه میشه و همین :)

با استفاده از استقرا اثبات می‌کنیم و ابتدا به ازای n=1 بررسی می‌کنیم، یک صفحه خالی رو تصور می‌کنیم و یک دایره بهش اضافه می‌کنیم و یکی از وتر های دایره رو می‌کشیم در نتیجه دو تا ناحیه مجاور ایجاد می‌شه که از دو رنگ برای رنگ آمیزی استفاده می‌کنیم، اما نکته اصلی رو از اینجا به بعد داریم؛ بیاید n=2 در نظر بگیریم یعنی دو دایره داریم، اینجا مهمه که دو دایره نسبت به هم چه وضعیتی دارن؟ چند تا برخورد دارن؟ بدترین حالت اینه که دایره ها متقاطع باشند یعنی دو نقطه برخورد هم داشته باشیم و نکته بعدی اینه که وتر ها باید به صورتی باشند؟ طبق فرض داریم که هیچ دو وتری نباید روی یک باشه و وتر ها کاملا بی ربط باشند به همدیگه
با این وجود اگر وضعیت تقاطع رو متصور بشیم، در صورتی که وتر هر دایره به گونه ای باشد که از منطقه اشتراک عبور کنه که ۷ ناحیه ایجاد میشه که با ۳ رنگ مختلف قابل رنگ آمیزی هست و این رو به ازای n برابر ۳ و ۴ و ... بررسی کنیم نتیجه بالا به دست میاد
اما این استدلال به ازای n گفته شده و بنا به گام استقرایی حالت n+1 رو هم بررسی می‌کنیم
اگر دایره n+1 ام رو رسم کنیم وتر n+1 ام هم بکشیم، وتر رسم شده نواحی قبلی رو قطع می‌کنه که در این صورت نواحی مجاور هم‌رنگ خواهند بود و از اینجا به بعد از تکنیک معکوس کردن استفاده کنیم یعنی جای رنگ ها رو نسبت به وضعیت قبلی برعکس می‌کنیم و نهایتاً می‌بینیم که تعداد رنگ های مورد استفاده ۳ تا هست

سلام آقا این چقدر درسته؟

 

[⭐️Setareh⭐️]

دقیقا اثباتی که گفتی رو به جای اینکه یک دایره اضافه کنی ( که پوشایی از بین بره ) بیا بالاترین دایره رو حذف کن اسقرا بزن دایره رو اضافه کن و حتی دقیقا تعویض هایی که باید انجام داد رو هم پاسخنامه ای که کتاب داشت و نوشتیش لازم نیست دست بزنیم . تنها دو تا مشکل داریم یکی اینکه پایه یک کل عملیات هارو پوشش نمیده که پایه رو میگذاریم ۲
یکی اینکه بالاترین دایره تعریف میشه؟ چون فضا نامتناهیه . راه اینه که دایره با بالاترین مرکز رو در نظر بگیریم و این چرا قابل تعریفه ؟ چون با فضا مقایسه نمیشه با دایره هامون مقایسه میشه و همین :)

اهاون. خب ببین ی چند تا سوال و فرض دارم در مورد این جوابی که کتاب داده.
اول اینکه بنظرم منظورش این نبوده که مثلا ی حالت n ایی داریم که براش جواب وجود داره حالا ی دایره دیگه بکشیم. راست میگی اینو بد گفته چون برگشده در ادامه گفته که حالت سوم رو تغییر نمیدیم.
ولی میدونی برای من که مثلا سر کلاسش میشستم اینو فهمیدم منظورش چی بوده. ینی میگی کلا غلطه روشش؟

 

[ایلیا منظم]

اهاون. خب ببین ی چند تا سوال و فرض دارم در مورد این جوابی که کتاب داده.
اول اینکه بنظرم منظورش این نبوده که مثلا ی حالت n ایی داریم که براش جواب وجود داره حالا ی دایره دیگه بکشیم. راست میگی اینو بد گفته چون برگشده در ادامه گفته که حالت سوم رو تغییر نمیدیم.
ولی میدونی برای من که مثلا سر کلاسش میشستم اینو فهمیدم منظورش چی بوده. ینی میگی کلا غلطه روشش؟

ببین اگر بخوایم بگیم این روش به عنوان یک روش مطلقا کافی و درست چیز درستیه خب نه غلطه
ولی اونقدر پرت و پلا هم نیست . صرفا باید استقرا رو به جای پیش رونده بازگشتی میزد و برای هندل کردن اون حالت سوم که گفته تغییر نمیدم باید میگفت ناحیه هایی که بعد عملیات های I,II رنگشون درست مونده و مشکلی ندارن رو کاری نداریم ( چون دوباره خود تعریف اینکه چه ناحیه ای میره توی III و چه حالتی نه هم کار سختیه )
و خط آخر جالبه . با خود علیپور کلاس داشتی؟

 

[ایلیا منظم]

با استفاده از استقرا اثبات می‌کنیم و ابتدا به ازای n=1 بررسی می‌کنیم، یک صفحه خالی رو تصور می‌کنیم و یک دایره بهش اضافه می‌کنیم و یکی از وتر های دایره رو می‌کشیم در نتیجه دو تا ناحیه مجاور ایجاد می‌شه که از دو رنگ برای رنگ آمیزی استفاده می‌کنیم، اما نکته اصلی رو از اینجا به بعد داریم؛ بیاید n=2 در نظر بگیریم یعنی دو دایره داریم، اینجا مهمه که دو دایره نسبت به هم چه وضعیتی دارن؟ چند تا برخورد دارن؟ بدترین حالت اینه که دایره ها متقاطع باشند یعنی دو نقطه برخورد هم داشته باشیم و نکته بعدی اینه که وتر ها باید به صورتی باشند؟ طبق فرض داریم که هیچ دو وتری نباید روی یک باشه و وتر ها کاملا بی ربط باشند به همدیگه
با این وجود اگر وضعیت تقاطع رو متصور بشیم، در صورتی که وتر هر دایره به گونه ای باشد که از منطقه اشتراک عبور کنه که ۷ ناحیه ایجاد میشه که با ۳ رنگ مختلف قابل رنگ آمیزی هست و این رو به ازای n برابر ۳ و ۴ و ... بررسی کنیم نتیجه بالا به دست میاد
اما این استدلال به ازای n گفته شده و بنا به گام استقرایی حالت n+1 رو هم بررسی می‌کنیم
اگر دایره n+1 ام رو رسم کنیم وتر n+1 ام هم بکشیم، وتر رسم شده نواحی قبلی رو قطع می‌کنه که در این صورت نواحی مجاور هم‌رنگ خواهند بود و از اینجا به بعد از تکنیک معکوس کردن استفاده کنیم یعنی جای رنگ ها رو نسبت به وضعیت قبلی برعکس می‌کنیم و نهایتاً می‌بینیم که تعداد رنگ های مورد استفاده ۳ تا هست

سلام آقا این چقدر درسته؟

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

 

[⭐️Setareh⭐️]

ببین اگر بخوایم بگیم این روش به عنوان یک روش مطلقا کافی و درست چیز درستیه خب نه غلطه
ولی اونقدر پرت و پلا هم نیست . صرفا باید استقرا رو به جای پیش رونده بازگشتی میزد و برای هندل کردن اون حالت سوم که گفته تغییر نمیدم باید میگفت ناحیه هایی که بعد عملیات های I,II رنگشون درست مونده و مشکلی ندارن رو کاری نداریم ( چون دوباره خود تعریف اینکه چه ناحیه ای میره توی III و چه حالتی نه هم کار سختیه )
و خط آخر جالبه . با خود علیپور کلاس داشتی؟

اوهوم. من فکر میکنم منظورش همونه که اون ناحیه ی سه طبق فرض استقرا درست رنگ شده و اگه بقیه رو هم اینطوری رنگ کنیم برای n+1 درست درمیاد.

اره سال اول دوم باهاش کلاس داشتم ولی دیگه ادامه ندادم. اتفاقا سر ما روشهای ترکیبیات ۲ رو داشت مینوشت!! ادم خسته ایه وگرنه منظورش همون راه درست استقراست😅😄

 

[ایلیا منظم]

اوهوم. من فکر میکنم منظورش همونه که اون ناحیه ی سه طبق فرض استقرا درست رنگ شده و اگه بقیه رو هم اینطوری رنگ کنیم برای n+1 درست درمیاد.

اره سال اول دوم باهاش کلاس داشتم ولی دیگه ادامه ندادم. اتفاقا سر ما روشهای ترکیبیات ۲ رو داشت مینوشت!! ادم خسته ایه وگرنه منظورش همون راه درست استقراست😅😄

خیلیم عالی
فکر کنم خیلی بزرگتر از من حساب میشید با این حساب :)

اگر تونستید و وقت داشتید ایده سوال گذاشتن روزانه رو انجام بدید واقعا حرکت ارزشمندیه ( چه برای بچه های جدید که سوال ببینن دستشون گرم میشه چه برای پیرا که یه مرور خاطراتی بکنن )

 

[⭐️Setareh⭐️]

خیلیم عالی
فکر کنم خیلی بزرگتر از من حساب میشید با این حساب :)

اگر تونستید و وقت داشتید ایده سوال گذاشتن روزانه رو انجام بدید واقعا حرکت ارزشمندیه ( چه برای بچه های جدید که سوال ببینن دستشون گرم میشه چه برای پیرا که یه مرور خاطراتی بکنن )

بله خیلی بزرگترم 😄

مرسی که اینطور فکر میکنی! باشه اگر حوصله اجازه بده پیش میبرم تاپیکو. شما هم اگر تونستید باشید خیلی خوب میشه مطالب تو ذهنتون فرش تره و بیشتر هم کار کردید :)

 

[⭐️Setareh⭐️]

 

[-𝑨𝒎𝒊𝒓𝒂𝒍𝒊-]

جعبه متن مخفی: یه راه ساده

همم مطمین نیستم ولی اول میای برای حالت n=3 بررسی میکنیم . اگه شطرنجی رنگ کنیم (ینی بالا ترین سفید بعد تناوبی یه دنباله از خونه ها که از راست به جپ میره و موقع رسیدن به سطر بعدی ازچپ ترین خونه شرو میکنه ) حالت بندی میکنی که اون خونه سیاه تو رنگ شده های جدید سیاه مون هست یا نه اگه نبودم یه شیفت 120 درجه بدیم بدیهیه که میفته توش . پس بدون کم شدن از کلیت فرض میکنیم هست حالا بدیهتا میشه دید زوجیت تعداد رنگ شده های سیاه مون با عملی که سوال گفته ناورداعه و همیشه فرده پس به حالت زوجی که میگه نمیرسه و تناقض حکمو نتیجه میده . برای حالت n های بزرگترم میتونیم بدون کم شدن از کلیت اون 9 تا خونه ای که خونه مشکی اولیه توش میفته رو جوری بگیریم که شرایط اولیه سوال رعایت باشه و بقیه خونه هارو حذف کنیم پس ناورداعه حفظ میشه و اوکیه.

 

[سوفی]

خیلی طولانیه دیگه
من هنوزم هواپیمایی مینویسم😔

 

[Vertigo]

اسپم: همیشه برام سوال بوده اونایی که المپیاد ریاضی میخونن چطوری این سوالای عجیب غریبو حل میکنن

 

[ایلیا منظم]

جعبه متن مخفی: یه راه ساده

همم مطمین نیستم ولی اول میای برای حالت n=3 بررسی میکنیم . اگه شطرنجی رنگ کنیم (ینی بالا ترین سفید بعد تناوبی یه دنباله از خونه ها که از راست به جپ میره و موقع رسیدن به سطر بعدی ازچپ ترین خونه شرو میکنه ) حالت بندی میکنی که اون خونه سیاه تو رنگ شده های جدید سیاه مون هست یا نه اگه نبودم یه شیفت 120 درجه بدیم بدیهیه که میفته توش . پس بدون کم شدن از کلیت فرض میکنیم هست حالا بدیهتا میشه دید زوجیت تعداد رنگ شده های سیاه مون با عملی که سوال گفته ناورداعه و همیشه فرده پس به حالت زوجی که میگه نمیرسه و تناقض حکمو نتیجه میده . برای حالت n های بزرگترم میتونیم بدون کم شدن از کلیت اون 9 تا خونه ای که خونه مشکی اولیه توش میفته رو جوری بگیریم که شرایط اولیه سوال رعایت باشه و بقیه خونه هارو حذف کنیم پس ناورداعه حفظ میشه و اوکیه.

سلام سوپر ناقص توضیح دادی که چرا کلیت کم نمیشه وقتی مشکی رو جابجا میکنیم ولی درسته راهت

 

[ایلیا منظم]

خیلی طولانیه دیگه
من هنوزم هواپیمایی مینویسم😔

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

 

[⭐️Setareh⭐️]

 

[⭐️Setareh⭐️]

 

[ftmhg]

جواب بنده

 

[ایلیا منظم]

جواب بنده

سلام دیدت به سوال دید جالبیه ولی گام حلت نه
یه راهنمایی ای بخوام بکنم بیا برای توان های کوچیک بررسی کن
مثلا ۱ رو کی میبره ۲۰۱۱ رو کی میبره ۲۰۱۲ ۲۰۱۳ رو کی میبره
۲۰۱۱*۲۰۱۱ رو کی میبره و ...
اگر فکر کردی بهش و حلی داشتی بفرست میخونم حتما

 

[⭐️Setareh⭐️]

سلام دیدت به سوال دید جالبیه ولی گام حلت نه
یه راهنمایی ای بخوام بکنم بیا برای توان های کوچیک بررسی کن
مثلا ۱ رو کی میبره ۲۰۱۱ رو کی میبره ۲۰۱۲ ۲۰۱۳ رو کی میبره
۲۰۱۱*۲۰۱۱ رو کی میبره و ...
اگر فکر کردی بهش و حلی داشتی بفرست میخونم حتما

مرسی ایلیا از وقتی که میگذاری ☺️

 

[⭐️Setareh⭐️]

جواب سوال قبلی که مربوط به تاپیک بازی ها بود

میتواند عدد صفر را روی تخته بنویسد و برنده ی بازی شود.

 

[⭐️Setareh⭐️]