صفحه ۸

شب ۶

سلام شاز.

اول راه سوال شب 5 رو میگم. اگه نمیخواین اسپویل شه این قسمتو اسکیپ کنین.

فرض کنین میز 2n+1 نفری باشه. با استقرا ثابت میکنیم به ازای هر k بین 1 تا n+1، بعد از گذشت یه تعداد حرکت، یا 2k تا کارت با شماره 1 تا k هیچ کدوم دوتاشون دست یه نفر نیست (دقیقن 2k تا جا اشغال کردن) یا اینکه حکم سوال (دوتا کارت با شماره برابر دست یه نفر باشن) نتیحه شده. به ازای k=1 حکم درسته، چون یا دوتا کارت 1 دست یه نفرن، یا اینکه دست دو نفرن :3

حالا برای k ثابت میکنیم. طبق فرض استقرا روی k-1، بعد از یه تعداد حرکت یا حکم نتیجه شده که حله یا اینکه تمام کارت های 1 تا k-1 دست آدمای مختلفه. این کارتای 1 تا k-1 هر مرحله دقیقن یکی شیفت سمت راست میخورن؛ چون از بقیه کارتا اکیدن کوچیکترن و به هم دیگه هم برخورد نمیکنن چون فاصله هاشون حفظ میشه. حالا یه کارت k رو در نظر بگیرید. آدمی که این کارته رو داره اول یه تعداد کارت 1 تا k-1 میان پیشش و میرن و بالاخره یا کارت k دیگه میاد پیشش که حله، یا اینکه یه کارت بزرگتر از k میاد پیشش. در اینصورت آدمه کارت k اشو میده بغلی و این کارت k عه هر دفعه به بغلی داده میشه؛ چون آدم کناری طبق فرض استقرا نهایتن یه دونه کارت کمتر از k داره که توی اون حرکت پاسش میده به بغلی خودش و اون یکی کارتش حتمن یا k عه که حله یا بزرگتر از k عه و بازم این پاس دادن ادامه پیدا میکنه. به این ترتیب اون همه 2k تا کارت 1 تا 2k هم دقیقن 2k تا آدم اشغال میکنن و گام استقرا ثابت میشه.

حالا طبق چیزی که اثبات کردیم به ازای k=n+1، چون نمیشه همه 2n+2 تا کارت دست آدمای مختلف باشه، پس حالت دیگه درسته که یعنی حکم مسئله ثابت شده :#

حالا سوال امشب :

G یه گراف دوبخشی کامله که هر بخشش n تا راس دارن. F یه گراف دو بخشیه که بخش بالا n تا راس داره بخش پایین 2n-1 راس که راس i ام از بخش بالا به راس های 1 تا 2i-1 از پایین وصله. ثابت کنید به ازای هر x از 1 تا n، تعداد تطابق های x یالی تو G و F برابره.

نویسنده : امید آزادی (سوال امشب از کلباسه)

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۳ · ۱۲:۵۲

از مرحله یک شاز تا مرحله یک اصلی

سلام دوستان.

خب ازمون مرحله یک ما هم بالاخره تموم شد (البته هنوز می تونید تو ازمون شرکت کنید ولی دیگه توی رنکینگ حساب نمیشه). انتقادات شما عزیزان مورد بررسی قرار گرفت و خیلیاشون درست بودن. متاسفانه ازمون ما علی رغم زمان زیادی که روش گذاشتیم مشکلات زیادی داشتش. بذاریدش رو حساب کم تجربگیمون :)

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

در مورد سطح آزمون هم باید بگم همون جوری که از نمرات ۲۰ نفر اول آزمون معلومه واقعا ازمون راحتی نبودش و فراتر از سطح مرحله یک طراحی شده بود. این امر کاملا عامدانه بود و ما می خواستیم شما دوستان با ایده های مختلف و سخت دست و پنجه نرم کنید. حقیقت امر اینه که مرحله یک قطعا این قدر سخت نیست و پر از ایده های تکراریه پس هر چه قدرم که این ازمونو خراب کردید امیدتون را از دست ندید و بدونید هیچ اتفاق خاصی نیفتاده. در ضمن حل کردن سوالای ازمونمون تا مرحله یک را به شدت توصیه می کنم چون پر از ایده های مختلفه. این هم از صورت سوالات و کلید آزمون. از گذاشتن پاسخنامه تشریحی اجتناب می کنیم چون دوست داریم که خودتون سوالا را حل کنید و راه حل هاتونو با هم به اشتراک بذارید و راجع بهشون بحث و گفت و گو کنید. اگر ما راه حل هامونو بذاریم صرفا به راه حل ما بسنده می کنید و بی خیال راه حل ها و ایده های جدیدتر می شید.

حالا در هر صورت هر چی که بودش تموم شد و گذشت. امیدوارم استفاده لازم را ازش برده باشید :)

بچه ها در این واپسین روزهای مونده به مرحله یک بهترین کار برای امادگی, دادن مرحله یک های دوره های گذشته و حل کردن سوالاتشونه. ما هم می خواهیم این کار را برای شما اسون تر کنیم. به زودی پستی در این رابطه خواهیم گذاشت و طرحمون رو به طور کامل توضیح خواهیم داد.

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

آپدیت ۱:

لینکا اصلاح شدن. ممنون از اطلاعتون!

آپدیت ۲:

لینکا رو مجددا اصلاح کردیم. دیگه واقعا درست شدن :)

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۲ · ۱۹:۱۹

سوال شب ۵

سلام بر همه گی

اول راه سوال دیشب

برهانه خلف بگیرید که تعداده اندیس هایی مثل k که a_k>k متناهی باشد حال بزرگ ترین اندیسی رو که خاصیت قبل رو داره رو k بنامید بعد فرض کنید بزرگ ترین عدد بین k عضو اول دنباله y باشد حال اگر y عضو اول دنباله رو در نظر بگیرید همهی انها از y کمترمساوی هستند چون k عوض اول که تبق تعریفه y از y کمتر مساوی هستن باقی هم چون از اندیسشان کوچکترند از y کمترند

و همچنین همهی انها از ۱ بزرگترند یعنی بین ۲ و y هستند (y-1 حالت) و چون y تا هستند پس طبق اصل لانه کبوتری ۲ تا از انها با هم برابرند و این با فرض متمایز بودن انها تناقض دارد پس برهان خلف رد میشود و مسعله ثابت میشود🥳

و اما سوال شب ۵

دور میز گردی ‎25‎ نفر نشسته اند.هر کدام از آنها دو کارت در دست دارند. روی هر کارت یکی از عدد های ‎1‎ تا ‎25‎ نوشته شده است(هر عدد روی ۲ کارت نوشته شده) . در هر لحظه با علامت داور هر نفر از دو کارت خود ، کارتی را که عدد آن کوچکتر است را به نفر سمت راست خود میدهد .ثابت کنید لحظه ای وجود دارد که یک نفر دو کارت هم شماره داشته باشد.

نویسنده : ارشیا سلطانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۱ · ۲۳:۱۶

شب ۴

سلام ملت.

میریم واسه سوال شب 4.

اول راه سوال شب 3 رو میگم. کسایی که میخوان اسپویل نشه این قسمتو اسکیپ کنن :8

اول ثابت میکنیم اعداد هر سطری از جدول رو اگه روی محور اعداد ضربدر بزنیم به جاشون، یه بازه تشکیل میشه (در واقع یعنی همه اعداد بین مینیمم سطر و ماکسیمم سطر هم توی سطر اومده)

اثبات این قسمتش اینجوریه که شما مینیمم رو بگیر بذار x، ماکسیمم رو بگیر بذار y، بعد حالا یه x و یه y رو بگیر، بین این دوتا همه اعداد بازه [x , y] اومدن؛ چرا، چون ما از عدد x با یه دونه یه دونه حرکت کردن رسیدیم به y، پس اولین عددی که نیومده این بینو اگه بگیریم مثل z، میبینیم که یهو از z-1 پریدیم به یه عدد غیر از z که تناقضه. پس این ثابت شد. حالا بازه سطر i رو [Li , Ri] بذارید. حالا دوتا حالت داره :

1. اشتراک [Li , Ri] ها ناتهی باشه. در این صورت اگه اشتراکشون عدد x رو داشته باشه، عدد x تو همه سطرا اومده و ما بردیم.

2. اشتراکشون تهی باشه. یعنی دوتا سطر هستن که بازه هاشون مجزا عه. فرض کنید بازه هاشون [L , R] و [X , Y] باشه که X>R. حالا از سطر [L , R] شروع به حرکت میکنیم تا به سطر [X , Y] برسیم. تو هر مرحله هر عدد از سطر [L , R] مثبت منفی 1 میشن و در آخر هر عدد بین [X , Y] عه. در اینصورت، همه اعداد بازه از X رد شدن، پس یعنی در هر ستون حداقل یه X داریم. پس بازم بردیم.

پس در کل عم میبریم.

حالا سوال شب 4 :

یه دنباله نامتناهی از اعداد متمایز و صحیح A داریم که Ai>1. ثابت کنید نامتناهی جایگاه مانند k وجود داره که Ak>k باشه.

نویسنده : امید آزادی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۱ · ۰۱:۱۵

آمادگی برای مرحله یک

سلام به همه شازیای دوست داشتنیمون :)

خب بچه ها امروز می خواهیم یه ذره در مورد آزمون شبه مرحله یکمون بگیم و بعدش هم در مورد استراتژی های بهتر مرحله یک دادن براتون حرف بزنیم. امیدوارم که حرفامون براتون مفید باشه. منتها قبل از شروع حرفامون می خواهیم یه تشکر ویژه بکنیم از ابوالفضل سلطانی عزیز که به ما در آماده سازی آزمون خیلی کمک کرد. دمش گرم :>

نکاتی پیرامون آزمون فردا:

آزمون روز جمعه مورخ ۲۱ / ۱۰ / ۱۳۹۷ به صورت انلاین برگزار می شود و شامل ۲۵ سوال است که شما عزیزان ۳:۳۰ ساعت برای پاسخ دادن به آن ها زمان خواهید داشت. برای راحتی شما عزیزان ساعت شروع آزمون بر عهده خود شما خواهد بود و شما می توانید در هر بازه ۲۱۰ دقیقه ای از جمعه که خواستید توی این آزمون شرکت کنید.
برای شرکت در آزمون به لینک /http://judge.cf:1234 مراجعه کنید و پس از ثبت نام وارد آزمون شوید. دقت کنید که صورت سوالات از ساعت ۱۲ بامداد جمعه بر روی سایت قرار خواهد گرفت.
نام کاربری و رمز خود رو فراموش نکنید. چرا که پاسخ عملکرد شما در روز شنبه (فردای آزمون) در همان جایی که آزمون را شرکت کردید به شما ابلاغ می شود.
برای تشویق نفرات برتر رتبه و نمره ۲۰ نفر اول آزمون روز شنبه در اختیار عموم قرار خواهد گرفت.
این آزمون صرفا برای مهارت سنجی شما عزیزان توسط خودتان آماده شده و جایزه ای هم برای آن در نظر گرفته نشده است. لذا تقلب در آن بی مورد است و به غیر از ضرر هیچ چیزی برای شما نخواهد داشت.
صورت سوالات کاملا واضح نوشته شده است و گزینه ها و پاسخ های آزمون بارها بررسی شده است. لذا از پاسخ به سوالات و ابهامات شما عزیزان در حین آزمون اجتناب خواهد شد. اگر اعتراضی به سوالات دارید پس از آزمون خود, آن را به اطلاع ما برسانید. اعتراضات وارده بررسی و نتیجه آن ها شنبه صبح اعلام خواهد شد.

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

حال نکاتی در مورد بهتر آزمون دادن خواهیم گفت که امیدوارم مورد توجه شما دوستان قرار گیرد.

نکاتی برای بهتر آزمون دادن:

بدون توجه به آزمون های گذشته آزمون خود را بدهید. بدانید اگر سوالات برای شما راحت است برای دیگران نیز راحت است و اگر برای شما سخت است برای دیگران نیز سخت است. پس دلیلی برای استرس و یا غرور وجود ندارد. مهم این است که شما از فکر کردن به مسائل متفرقه اجتناب کنید و با تمام تمرکز به ادامه آزمون خود بپردازید.
وقت خود را مدیریت کنید. اول از همه زمان خود را تقسیم بر تعداد سوالات کنید تا ببینید برای هر سوال به طور میانگین چه قدر زمان دارید. سپس طوری ازمون را پیش ببرید که مطمئن باشید برای هر سوال حل نشده خود می توانید حداقل به اندازه نصف زمان آن سوال بر روی آن وقت بگذارید. متاسفانه خیلی از بچه ها گاهی اوقات بر روی تعدادی مسئله زمان زیادی می گذارند و این باعث می شود که نتوانند بر روی همه مسائل به اندازه لازم وقت بگذارند و این گونه ممکن است تعداد زیادی سوال راحت را از دست بدهند. پس مراقب زمان خود باشید.
بی دقتی هم یکی دیگر از عواملی است که که گریبان گیر بچه ها در حین آزمون می شود و حسرت های زیادی برای آن ها در پی خواهد داشت. رمز بی دقتی نکردن در حفظ آرامش و منظم فکر کردن است. اگر برای حل هر سوال مسیر درستی را در نظر بگیریم و با آرامش به ترتیب مسیر را طی کنیم هیچ بی دقتی در این بین نخواهد شد. اغلب بی دقتی ها در اثر استرس و یا گیج شدن بچه ها در مسائل است.
وقت خود را بر روی راه حل های اشتباه تلف نکنیم. خیلی اوقات المپیادی ها نه تنها در آزمون تستی بلکه در آزمون تشریحی نیز راه حل اشتباهی را برای حل سوال در نظر گرفته و زمان زیادی را بر روی آن تلف می کنند و حتی در آزمون های تستی نمره منفی نیز دریافت می کنند. حال چه کنیم که از این اشتباهات نداشته باشیم؟! باید یاد بگیریم که چراهای درستی برای خود طرح کنیم و پاسخ درستی هم به آن ها بدهیم. خیلی اوقات ما یک سری حالات مسئله را در نظر نگرفته و یا از اثبات یک گزاره به سادگی عبور می کنیم و تو ذهن خود می گوییم اینکه بدیهی است در صورتی که واقعا ممکن است آن گزاره اشتباه باشد. باید به ذهن خود آموزش دهیم که از زوایای مختلف به مسئله نگاه کند و خیلی راحت از کنار گزاره های کوچک که در کنار هم قرار گرفتن آن ها مسئله را حل می کند نگذرد و برای تک تک آن ها اثباتی ارائه دهد. این کار با حل مسئله میسر می شود البته به شرط اینکه در حین حل مسائل تمامی این نکات را در نظر بگیریم. هر چه مسئله ای که حل می کنم سخت تر باشد قطعا میزان پیشرفت ما نیز بیشتر خواهد بود.
در آزمون تستی سرعت عمل بسیار تاثیرگذار است و حفظ آرامش که در نکات قبلی به آن اشاره کردیم دلیلی بر فدا کردن سرعت عمل نخواهد بود. باید یاد بگیریم که وقت خود را بیهوده تلف نکنیم و در عین آرامش مسیر حل مسئله را سریع تر بپیماییم. این کار با حل مسئله زیاد میسر خواهد شد. پس توصیه می شود مرحله یک دوره های قبل را که بهترین نمونه برای مرحله یک واقعی هستند به صورت آزمون از خود بگیرید و پس از آزمون به حل سوالات حل نشده آن بپردازید.
اگر برای حل سوالی هیچ ایده ای نداشتید سعی کنید با مثال های کوچک و یا بررسی تعدادی از حالات مسئله برای خود شهود ایجاد کنید تا بتوانید بهتر به مسئله فکر کنید.

اگر دقت کرده باشید مطالب گفته شده در جهت بهبود مرحله یک اصلی شما می باشد. لذا از همین فردا اجرای این نکات را آغاز کنید تا عملکردتان روز به روز بهبود یابد.

امیدوارم هر جا که هستید موفق باشید. خداحافظ :)

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۰ · ۱۱:۳۱

سوال شب ۳

سلام ! دونقطه دی

مثل دیروز اول راه شب گذشته رو می گیم ( اگر به سوال به مقدار کافی فکر نکردین، نخونین که براتون لوث نشه !=) ) :

اول از همه, اگر دو تا زیر مجموعه ی متمایز پیدا بشه که در شرایط سوال صدق کنه, دو زیرمجموعه ی مجزا هم پیدا میشه. کافیه اشتراکشون رو از هر دو حذف کنیم.

حالا در کل 2^Mزیرمجموعه داریم. هر کدوم از زیرمجموعه ها مثل S رو متناظر با یک n+1 تایی مرتب (a₀, a₁ , ... , a_n) می کنیم, که a_i برابر sigma (S_j) ⁱ هست.

a_i حداقل 0 و حداکثر M * M ⁱ = M ^{i + 1}هست, پس حداکثر M ^{i + 1} + 1 <= M ^{n + 2} حالت دارد ( M > 1 ). در نتیجه تعداد n + 1 تایی های معتبر از M^{n*n + 3*n + 2} بیستر نیست.

پس کافیه 2^M > M^{n*n + 3*n + 2}تا طبق اصل لانه کبوتری 2 تا زیرمجموعه درست پیدا بشن. تابع 2^Mنمایی هست ولی تابع M^{n*n + 3*n + 2} چندجمله ای, پس پیدا می شه M که نا مساوی گفته شده برقرار بشه !

خب , بالاخره می رسیم به سوال امشب دونقطه دی :

خانه های یک جدول مربعی n_xn رو با اعداد صحیح پر کرده ایم , به طوری که اختلاف عدد هر دو خانه ی مجاور ضلعی , از 1 بیشتر نشود.

الف ) اثبات کنین عددی وحود داره که حداقل کف n/2 بار در جدول ظاهر شده.

ب ) اثبات کنین عددی وحود داره که حداقل n بار در جدول ظاهر شده.

نویسنده: مهرشاد =) (راه سوال دیشب هم از میکائیل )

شااززز منگولیا ۱۳۹۷/۱۰/۱۹ · ۲۱:۵۰

آزمون شبیه ساز مرحله یک

سلام به همه شازیای عزیزمون. بازم ما اومدیم با کلی خبرای داغ و باحال :)

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

آزمون رو میتونید هر ساعتی از روز که خواستید بدید و بعدش باید جواب هاش رو توی سایت ما وارد کنید که این اطلاعات ر بعدن دقیق تر بهتون میگیم.

تا جای ممکن تلاش شده که شکل برگزاری ازمون تناقضی با استانداردهای مرحله یک نداشته باشه. پس لطفا شما هم همون جوری که قراره مرحله یک واقعی را بدید تو این ازمون هم شرکت کنید.

از تمامی دوستانم صمیمانه خواهشمندم که با اسم خودشون توی ازمون ثبت نام کنند تا کاملا آزمونمون رنگ و بوی مرحله یک به خودش بگیره.

امیدوارم آزمون مفیدی براتون باشه.

یادتون نره که ما بعد از جمعه منتظر انتقادات و پیشنهادات محترمانه شما خواهیم بود :)

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۱۹ · ۱۰:۰۰

شب ۲

سلاااااااام

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

اول از همه راه سوال دیروزو میگم، کسایی که فکر نکردن بهش نخونن که براشون لوث نشه!

میخوایم ثابت کنیم یه پمپ بنزینی هست که بشه با شروع ازش، ساعتگرد کل دایره رو طی کرد. میخوایم با استقرا روی n، تعداد پمپ بنزین ها، مسئله رو ثابت کنیم. به ازای n=1، حکم بدیهیه خدایی. به ازای n>1 ها، اول نشون میدیم پمپ بنزینی مثل X وجود داره که با شروع از اون و با باک خالی، بتونیم خودمونو به پمپ بنزین بعدی X در جهت ساعتگرد برسونیم. فرض خلف میکنیم همچین پمپ بنزینی نباشه، اونوقت مقدار بنزین هر پمپ بنزین اکیدن از مقدار فاصلش تا پمپ بنزین بعدیش در جهت ساعتگرد کمتره، اونشکلی جمع بنزین ها از محیط دایره کمتر میشه که تناقضه. پس پمپ بنزین X طبق خواسته ما وجود داره. حالا پمپ بنزین بعدی X در جهت ساعتگرد رو Y بگیرید. میگیم بیا بنزین Y رو بگیر و تو X بریز، بعدش Y رو حذف کن. شرایط مسئله هنوز برقراره و تعداد پمپ بنزینا یکی کم شده؛ پس طبق فرض استقرا، یه پمپ بنزینی هست که با شروع از اون در جهت ساعتگرد بشه دایره رو طی کرد. اگه اسم اون پمپ بنزین Z باشه، ما اینجا هم با شروع از Z کل دایره رو طی میکنیم. چرا؟ چون تا وقتی به X نرسیده که همه چی مثل شرایط n-1 پمپ بنزینمونه. وقتی هم به X رسید، چون باکش بیشتر مساوی 0 بنزین داره، با بنزینی که از X میگیره میتونه به Y برسه (طبق شرایط X) و از اونجا هم به پمپ بنزین بعدی میره. بعدش دوباره طبق شرایط n-1 پیش میره. اینشکلی گام استقرا ثابت میشه و حکم ثابت میشه.

راه های دیگه ای هم مثل اکسترمال داره این سوال اگه خواستید فک کنید بهش %__%

و حالا سوال جدید:))

ثابت کنین عدد طبیعی M وجود دارد به طوری که از مجموعه ی اعداد طبیعی 1 تا M

بتوان دو زیر مجموعه مجزا مثل A و B انتخاب کرد به طوری که:

Sigma ai^k=sigma bi^k

برقرار باشه به ازای هر 0=<n>=k

(یعنی تعداد اعضاشون برابر باشه, مجموع اعضاشون برابر باشه, مجموع توان دو اعضاشون برابر باشه و ... مجموع توان n اعضاشون هم برابر باشن)

نویسنده: میکائیل (راه حل سوال دیروز از امید)

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۱۸ · ۲۲:۳۳

۱ ۷ ۸ ۹ ۳۸