مرحله ۲ نزدیکه ...

۱- بزرگترین مجموعه مستقل گراف شهر‌ها رو در نظر می‌گیریم، اندازه‌ی این مجموعه مستقل حداکثر می‌تونه ۱۰ باشه. چون این مجموعه مستقل بیشینه هستش، پس هر راس خارج از اون، حداقل ۱ یال به مجموعه مسقل داره. پس حداقل ۹۰ یال به مجموعه مستقل وارد شده. حالا اگه این مجموعه مستقل رو از گراف حذف کنیم،یه گراف ۹۰ راسی باقی می‌مونه که بازم خواص گراف اولیه رو داره. پس اگه مجموعه مستقلش رو در نظر بگیریم، حداقل ۸۰ یال بهش وارد شده. اگه همین کارو ادامه بدیم، بدست می‌یاد که گراف حداقل

90+80+70+...+10=450

یال داره. می‌شه یه گراف ساخت یه دقیقا همین قدر یال داشته باشه، مثلا اگه ۱۰ تا K10( گراف کامل ۱۰ راسی) کنار هم بزاریم، یه گراف ساخته می‌شه که خواص گفته شده تو مسئله رو داره و ۴۵۰ تا یال داره.

۲- اعداد ۱،۲،۴،۸،۱۶ رو کنار می‌گزاریم. حالا واسه‌ی هر انتخاب از ۹۵ عدد باقی مونده، بود یا نبود این ۵ عدد با توجه به باقی‌مانده‌ی آن بر ۳۲ به طور یکتا تعیین می‌شه( چرا؟) پس جواب مسئله می‌شه ۹۵^۲.

۳- حکم رو با استقرا بر روی i+j اثبات می‌کنیم. پایه به ازای i+j=0 طبق گفته‌ی مسئله درسته! حالا فرض کنید، می‌خوایم حکم رو واسه خونه‌ی (i,j) ثابت کنیم و می‌دونیم به ازای هر خونه‌ی (x,y) که x+y

i xor k = i xor j -> k = j (چرا؟؟)

حالا فقط لازمه بگیم که تمام اعداد کوچیکتر از i xor j، توی سطر یا ستونش اومدن
برای این‌کار فرض کنید، می‌خوایم عدد 

k

رو بسازیم، برای این می‌یایم رقم های i و j رو در مبنای ۲ از سمت چپ پیمایش می‌کنیم. اولین خونه‌ی رو در نظر بگیرید که xor اون رقم توی i و j برابر k نمی‌شه،حتما یکی از بیت های دو عدد، تو این رقم ۱ هستش( چرا؟) بعد می‌یام یکی از اون یک هارو انتخاب می‌کنیم و ۰ اش می‌کنیم و توی رقم های بعد، هر وقت مشکلی پیش اومد، رقم این عدد رو تغییر می‌دیم تا درست بشه. توی راهی که گفته شد، دقیقا یکی از اعداد تغییر می‌کنه و عدد تغییر کرده حتما کوچیک‌تر از مقدار اولیش می‌شه(چرا؟). پس متناظر با یکی از خونه‌های هم سطر یا ستونشه. پس حکم اثبات شد.

۴- یک گراف ۱۰۰ راسی درست می‌کنیم که در آن هر راس نشان‌گر یک عدد است. حالا واسه هر دو عدد که جمعشون گویا می‌شه، یک یال بین رئوسشون می زاریم.حال ادعا می‌کنیم که گراف درست شده، دور فرد ندارد. فرض کنید یک دور فرد شامل راس‌های

x1,x2,....,x(2k+1)

در آن پیدا کردیم. طبق نحوه‌ی ساخت گراف، می‌دونیم که تمام جمع‌های زیر گویاست:
x1+x2
x2+x3
.
.
.
x(2k+1)+x1
پس عبارت زیر نیز گویاست:
(x1+x2)-(x2+x3)+(x3+x4)-.....-(x(2k)+x(2k+1))-(x(2k+1)+x1)
از طرفی مقدار این عبارت برابر 

-2x(2k+1)

می‌شه، که گویا بود اون نتیجه می‌ده که خود (x(2k+1 گویاست، که تناقضه. چون گراف مورد نظر دور فرد نداره، پس ۲ بخشی هستش. پس حداقل یک بخش آن وجود داره که شامل ۵۰ راس باشه.

سوال

سلام!

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

1- به تازگی قراره که تو شاززز آباد جاده کشی شه. میدونیم که شاززز آباد 100 تا شهر داره و یک نوع جاده کشی مطلوبه اگه هر 11 تا شهرو که در نظر بگیریم حداقل 2 تا باشن که بینشون یه جاده هست ، حالا ثابت کنید َیک جاده کشی مطلوب حداقل 450 تا جاده دارد. یک مثال هم بزنید که شامل دقیقا 450 جاده است.

2- علی کلید که متخصص باز کردن گاوصندوقه ، جدیدا به یه گاوصندوق برخورده که زیاد عادی نیست. رمز این گاوصندوق یک عدد ه (خب این که عادیه :) ) ولی نکته ای که هست اینه که این رمز ، جواب این مساله است که روی گاوصندوق حک شده : « تعداد زیرمجموعه های {100,...,1,2,3} را بیابید که مجموع اعضای آن بر 32 بخشپذیر باشد. » حالا شما به علی آقا کمک کنید تا بتونه کاوصندوق رو بازکنه و به پاداشش برسه ، یه بخشیش رو هم میده به شما.

3- علی کلید باز به یه گاوصندوق عجیب رسیده. این گاوصندوق این طوریه که 100 تا سوال به این شکل میپرسه. « بیتینگ جفت (i , j) چند است ؟ » میدانیم بیتینگ (0,0) مساوی 0 است. و برای سایر جفت ها به این شکل محاسبه می شود : کوچکترین عددی که در بیتینگ هیچ کدام از جفت های (i,0) , (i,1) , ... , (i,j-1) و  (i-1,j) ، .... ، (1,j) ، (0,j) نیامده است. به دلیل زمانبر بودن محاسبه ی این کار علی آقا حدس میزند که بیتینگ (i , j) مساوی است با i xor j است. اما این تنها یک حدس است به او کمک کنید که درستی یا نا درستی حدسش را بفهمد.

4- تقی و نقی دوقلو ان. تقی المپیاد ریاضی و نقی المپیاد کامپیوتر. یه روز که نقی دنباله سوال بوده از تقی یه سوال ترکیبیات میخواد. تقی هم این سوال رو میده :

« 100 تا عدد گنگ داریم. ثابت کنید 50 تاشون هستند که جمع دو به دو ی آنها گنگ ست. »

نقی وقتی سوال رو میشنوه میگه من گفتم ترکیبیات نه جبر و تِنظریه اعداد که! تقی هم بلافاصله جواب سوال رو میگه و معلوم میشه که سوال واقعا ترکیبیاته. حال شما مثل نقی عمل نکنید و رو سوال بدون این که فکر کنید  ریاضویه فکر کنید.

---

رور اول مرحله دوم ، تشریحیه ، میتونید خوشحال باشید!منبع خبر  هم کاملا موثقه.

بالاخره اومد !

سلا م

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

۱. ببینین بچه ها ، هر سال ۱ سری از بچه هایی که طلا گرفته بودن میومدن می گفتن مهم نیست قبول نشدن و این حرفا و خوب شما [و ما] هم می گفتیم خوب اینا که دیگه طلا شونو گرفتن و از این حرفا ... !
اما من الان به عنوان ۱ آدمی که نزدیک کنکوره دارم حرف میزنم .

اول از همه بدونین که اگه هدفتون صرفا دانشگاه رفتنه و به المپیاد به دید ۱ پل نگاه می کنین ، مطمئن باشین که کنکور خیلی خیلی راه ساده تریه .

اما المپیاد ۱ سری چیز خیلی خوب داره که زیاد هم ربطی به مدال اوردن و قبول شدن و ایناش نداره .
کلی دوست خوب ، ۱ عالمه خاطره ی خوب و از همه مهم تر این که تفکر رو به آدم یاد میده ( البته نه این که کسایی که المپیادی نیستن تفکر بلد نیستن ، اما المپیاد کمک زیادی می کنه ) .
و اینا هیچ کدوم ربطی به مدال گرفتن یا نگرفتن و این حرفا نداره ، به نظر من چیزی که باارزشه المپیادی بودنه .

پس مثل بچه آدم برین مرحله ۲ و ۳ و ... بدین ، فارق از اینکه قبول می شین یا نمی شین .

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

پس مطمئن باشین سوالای مرحله ۲ در حدیه که می تونین حلشون کنین و هیچ وقت سوالای فضایی نمیدن ! (-;

۳. دید آدم به امتحان و سوالا خیلی مهمه ،
اگه ۱ سوال خیلی ساده رو بزارن جلوی آدم و بگن این سوال open ه ، به احتمال خیلی زیاد حلش نمی کنه .
این چیزیه که باعث میشه سر امتحان آدم سوالایی که بلده رو هم حل نکنه .
چون ۱ غول از مرحله ۲ ساخته برای خودش .
اما اگه دید این باشه که همه ی سوالای مرحله ۲ رو من می تونم حل کنم ، مطمئنا خیلی نتیجه بهتری گرفته میشه .
به نظر من اهمیت این دید و اعتماد به نفس از چیز بلد بودن خییلی بیشتره .

پس سعی کنین از امروز قبول کنین که هیچ سوالی نیست که نتونین حل کنین و با این دید به سوالا نگاه کنین .

***
با وجود همه ی این حرفایی که من زدم بازم همون آشه و همون کاسه ،‌ فکر نکنین خوب حالا همه همینطور نگاه می کنن به مرحله ۲ ، نه ! D:

در ضمن از مراحل بعدی و کد زدن و اینام غافل نشین .

سوالای مرحله ۲ های سالای قبل رو هم حتما از خودتون امتحان بگیرین . (لینک سوالای سالای قبل)

همچنین قراره ۱ سری سوال هم به زودی گذاشته بشه که آمادس !

موفق و سربلند و پیروز و از این حرفا باشین و تعطیلات خوش بگذره

---

راستی سایتinoiیه پست جدید گذاشته ، اگه ببینیدش بد نیست