نظریه اعداد لازم برای المپیاد کامپیوتری ها
عدد های طبیعی در جدول مربعی x در x
زیر مجموعه و مجموعه ها در ترکیبیات
یال های گراف کامل 6 راسی و مثلث ها
یال های گراف کامل 7راسی و مثلث
مجموعه‌یk-آلوده‌ی ماکسیمم/بیشینه تعداد راس به طوری که حداکثر k یال آلوده(!) شوند.
فلسفه ی وجود و یا عدم وجود جفت اعداد مسخره
ازمون مرحله یک سی و سومین المپیاد ریاضی سوال 25 (کد 2)
دور دایره n لامپ قرار دارد . در هر مرحله میتوان k لامپ متوالی را انتخاب کرد و وضعیت هر کدام را عوض کنیم
توجه کنید این سوال با اون سوال فرق می کنه
ابتذا همه لامپ ها خاموش اند :برای عدد داده شده n تمام k هایی را بیابید که با دنباله ای از حرکات فوق بتوان به هر وضعیتی رسید؟
چرا جواب میفرستم میگه sorry you already gave an answer من که جوابی نفرستادم قبلا
2019-07-21 07:47:07 -0500 مرشدفکر کنم جواب میشه اعداد کوچکتر از n که فرد هستند و نسبت به n اول هستند برای n بزرگتر از 1 میشه جواب که فکر میکنم هم کافیه هم لازم و فکر می کنم درست اثباتش کردم اگه درسته بگین اثباتش بکنم
2019-07-22 04:32:17 -0500 ممممممدددمن اثبات کردم میشه اعداد فرد کم تر از n که n -1 یا 1+n رو عاد میکنن مشکل اینه جوابو میفرستم ارور میده
2019-07-22 06:46:06 -0500 مرشدفکر کنم جواب میشه اعداد کوچکتر از n که فرد هستند و نسبت به n اول هستند برای n بزرگتر از 1 . حالا طرف اولشو میگم یه قضیه ساده داریم که ترکیب خطی از a و b اول داریم که میشه 1 یعنی ax+by=1 .حالا b رو بگیرین 2n.
حالا داریم که k و 2n ب.م.م اشون یکه پس یه ترکیب خطی داریم ازشون پس میشه ترکیب خطی ای داریم که 2nx+ky=1 پس می تونیم قدر مطلق yk تا متوالی رو انتخاب و عوض کنیم و باقیمانده اش بر بر 2n میشه مثبت منفی یک پس می توانیم یک حکم 1 تایی انجامی بدیم پس با 1 می تونیم این کارو بکنیم .
طرف دوم هم به راحتی با ناوردایی ساده حل میشه فرض کنید ب.م.م n و k میشه x. آگه x>1 حالا ما این n تا رو به x قسمت متوالی تقسیم می کنیم و از هر قسمت دو تا رو رنگ می کنیم و هر مرتبه از k تا متوالی که ما انتخاب می کنیم زوج تا از این خانه های رنگ شده انتخاب میشن و ما نمیتوانم به حالتی برسیم که فرد تا از رنگ شده ها روشن باسن .
و حالتی که x مساوی یک باشه یعنی k زوجه چون بمم اش با 2n بیشتر از یک بوده و هر مرتبه زوج تا چراغ انتخاب میشه و مشابها اثبات میشه.
خوب فک کنم جواب میشه اعداد فردی که n+1 یا n - 1 رو عاد میکنن
اول میتونیم با استفاده از سوال قبل بگیم k هایی که این خاصیت رو دارن قطعا توان 2 داخلشون از توان 2 داخل n بیشتر نیست
حالا اگه بشه از حالته همه خاموش به هر حالتی رسید قطعا از هر حالتی به هر حالت دیگه ای میشه رسید پس از حالتی که همه روشن هستن باید به حالتی که فقط یک لامپ روشنه رسید
اگه بشه به حالتی رسید که فقط یکی روشنه قطعا به همه حالت ها میشه رسید
خوب الان کاری که میکنیم اینه میگیم فرض میکنیم میخوایم لامپ 1 روشن بمونه بقیه خاموش و فرض میکنیم تو حالت اولیه همه روشن باشند بدیهیه که لامپ 1 باید تو زوج بار انتخاب شده باشه تو k تای متوالی و اینکه یک انتخاب k تای متوالی بیشتر از 2 بار انتخاب نمیشه چون اگه زوج بار بشه انگار اصلا نشده اگه فرد بار بشه انگار یک بار شده
حالا ادعا میکنیم اگه بخوایم به وضعیتی برسیم که فقط لامپ 1 روشن باشه فقط باید در صورتی انتخاب بشه که
سمت چپ ترین یا سمت راست ترین عضو k تای متوالی باشه
اثبات :
فرض میکنیم نباشه بدیهیه که زوج بار انتخاب شده میایم k - 1 لامپ چپ و راست لامپ 1 رو علامت میزنیم با یه برسی ساده واضحه که هر جوری جز ادعای ما k خونه متوالی انتخاب بشه قطعا یک دسته متوالی از لامپ های علامت زده ما که تعدادشون از k کم تره هست که روشن میمونه و توسط دو لامپ خاموش محاصره شده
حالا از ناوردایی استفاده میکنیم برسی میکنیم میبینیم در صورتی که همچین حالتی گیر کنیم هیچ وقت ازش بیرون نمیایم یعنی هر حرکتی که انجام بدیم بازم یک دسته متوالی هست که تعداد اعضاش از k کم تره و همه روشنن و توسط دو تا خاموش محاصره شده پس این فرضمون اثبات میشه .
حالا میگیم که لامپ 1 یا انتخاب نشده یا دو بار انتخاب شده طوری که یک بار چپ ترین یه بار راست ترینه حالا هر دو تا رو برسی میکنیم
1) لامپ یک اگه انتخاب نشده باشه معلومه در حالتی که k | n - 1 میشه خیلی راحت به حالتی رسید که فقط لامپ یک روشنه حالا میگیم چرا خلافش غیر ممکنه اگه k عاد نکنه n - 1 رو میبینیم برای اینکه بخوایم اون لامپ هارو پر کنیم باید یک لامپ غیر از یک تو چند مجموعه انتخاب شه پس قطعا یک لامپ غیر از لامپ 1 وجود داره که زوج بار انتخاب شده باشه که فرض رو باطل میکنه
2) اگه یک دو بار به اون شکل انتخاب شده باشه میتونیم به شکل مشابه بگیم که اکه k عاد نکنه n - 2k + 1 رو قطعا یک لامپ غیر از لامپ 1 وجود داره که زوج بار انتخاب شده باشه که فرض رو باطل میکنه
بدیهیه که k | n - 2k + 1 میشه نتیچه گرفت 1 + k | n
پس فهمیدیم این دو حالت رو حالا از اونجا که میگیم زوجیت n + 1 و n - 1 با n متفاوته پس باید k قطعا یه عدد فرد باشه چون اثبات کردیم تعداد 2 داخل تجزیه ی k از داخل تجزیه ی n کمتره
پی نوشت : این سوالو از کجا آوردی ؟ من یه 30 دقیقه بیشتر روش فکر نکردم نمیتونم دقیقی نظر بدم ولی عجیب بنظر میومد
