شاززز

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

برای دسترسی به راه حل های سوالات شب های قبل ما را در پیام رسان دیسکورد دنبال کنید.

و حالا سوال امشب‌ یا بهتره بگم امروز:

سلام بچه ها. بازم ما اومدیم با یه سوال جدید :)

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

حالا میریم سراغ سوال امشب:

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

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

واضحه که تعداد تطابق های x تایی توی گراف G که برابر هستش با c(n, x) ^ 2 (انتخاب x از n به توان دو) ضرب در x فاکتوریل. حالا می خواهیم ثابت کنیم تعداد تطابق های x تایی گراف F هم همین قدره. فرض می کنیم جواب مسئله مون هستش (f(n, x. حالا می خواهیم یه رابطه بازگشتی برای f پیدا کنیم. با کمی تلاش به رابطه بازگشتی زیر می رسیم:

(f(n, x) = f(n - 1, x) + f(n - 1, x - 1) * (2n - x

برای اثبات رابطه بازگشتی بالا میاییم راس n ام را در نظر می گیریم. یا با هیچ کس تطابق داده نمیشه که در این صورت میشه (f(n - 1, x. یا به یه راس دیگه تطابق داده میشه. در این صورت میاییم اول به (f(n - 1, x - 1 طریق یه تطابق x - 1 تایی توی n - 1 نفر اول پیدا می کنیم. حالا چون n به همه 2n - 1 راس قسمت دیگه وصله و از بین اونا دقیقا x - 1 تاشون با راس دیگه تطابق داده شدن, راس n ام 2n - x انتخاب برای تطبیق داره. پس رابطه بازگشتی بالا ثابت میشه. حالا با استفاده از استقرا بر روی n و مقدار کمی جبر می توانید ثابت کنید که (f(n, x برابر است با c(n, x) ^ 2 (انتخاب x از n به توان دو) ضرب در x فاکتوریل. بنابر این مسئله ثابت می شود. 3:

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

در مدرسه ای n دانش آموز وجود دارند. هر دانش آموز در تعدادی گروه عضو است. اگر دو گروه دو دانش آموز مشترک داشته باشند آنگاه تعداد اعضایشان متفاوت است. ثابت کنید تعداد گروه ها از (n-1)*(n-1) کمتر است. ( گروه یک نفره نداریم )

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

از این به بعد سوالای شب و یه سری چیزای دیگه رو اونجا میذاریم. خلاصه که جمع بشید اینجا پرچم شازو ببریم بالا :*

بعد که اپو نصب کردین با این لینکه بیاید تو.

بای بای :)

حمیدرضا کلباسی

سلام شاز.

اول راه سوال شب 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 باشه.

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

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

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

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

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

حالا در کل 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 _x n رو با اعداد صحیح پر کرده ایم , به طوری که اختلاف عدد هر دو خانه ی مجاور ضلعی , از 1 بیشتر نشود.

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

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

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