◄◄ اتــاق تــجــزیــه و تــرکــیــبــات ►►

[m_honarmand_j]

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

[m_honarmand_j]

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

[m_honarmand_j]

دوستان ادامه ی سوالات رو هم می زارم . ولی الان وقت ندارم .

[Ar@m]

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

[kaakaa]

bego kodomaro hal nakarD vasat hallesh konam.

[m_honarmand_j]

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

[m_honarmand_j]

سوال چهارم روز اول مرحله ی دوم المپیاد کامپیوتر امسال : می خواهیم بین n شهر جاده بکشیم . فاصله ی دو شهر را کوتاه ترین مسیر بین آن ها در نظر می گیریم که به ازای فاصله ی هر دوشهر باید آن مقداد عوارض بدهیم . ( به ازای هر یال در مسیر بین آن رو شهر یک واحد) . همچنین احداث هر جاده مخارجی دارد . هزینه ی ساخت یک نقشه ی جاده ها برابر مجموع مخارج جاده ها به همراه مجموع عوارض هر دو شهر می باشد . ( نقشه باید همبند باشد) . کمترین هزینه ی ساخ را بیابید ( در دو حالت برسی کنید . اگر هزینه ی ساخت هر جاده کمتر مساوی 1 باشد و در حالت بعد بیشتر از 1 باشد).
جواب : اگر هزینه ی هر جاده کمتر مساوی 1 باشد باید همه ی جاده ها باشند . یعنی به ازای هر دوشهر یک جاده بینشان باشد .(می توانید برسی کنید که اگر فاصله ی دو شهر بیشتر از 1 باشد هزینه ی ساخت بیشتر می شود) در نتیجه هینه ی ساخت نقشه برابر انخاب 2 از n ( مجموع عوارض ها) بعلاوه ی انتخاب 2 از n ضرب در هزینه ی ساخت یک جاده ( هزینه ی جاده ها) . در نتیجه حاصل برابر است با:
( a هزینه ی ساخت یک جاده) n*(n-1)/2 *( a+1)
در حالت دوم گراف ما باید گراف ستاره ای باشد . یعنی یک شهر در مرکز و دیگر شهر ها تنها به این شهر متصل باشد . در نتیجه هزینه ی ساخت نقشه برابر است با :
a*(n-1) + (n-1)+ 2*((n-1)*(n-2)/2)
(زیرا n-1 جاده داریم و فاصله هر شهر از شهر مرکزی 1 است که n-1 از این فاصله ها است و به تعداد انتخاب 2 از (n-1) تا فاصله ی 2 داریم . )

[m_honarmand_j]

سوال اول روز دوم مرحله ی دوم المپیاد کامپیوتر امسال : فاصله ی دو رشته به طول n را برابر تعداد مکان هایی می گیریم که با هم در آن جا تفاوت دارند . 1386 رشته به طول n داریم که مجموعه ی A را تشکیل می دهند . یک رشته مانند # به طوب n را در نطر می گیریم که در بین همه ی رشته های به طول n کمترین فاصله را از A دارد . ( مجموع فاصله ی # از تک تک اعضای A ) . این مقدار فاصله را a در نظر می گیریم . ثابت کنید که یک رشته به طول n در مجوعه ی A وجود دارد که فاصله اش از A حداکثر 2a است .
جواب : برای این کار باید ابتدا ثابت کنیم که اگر دو رشته از رشته ای دیگر فاصله های x و y را دارا باشند آنگاه این دو رشته از هم فاصله ای حداکثر x+y دارند . برای این کار اگر خلاف آن را فرض کنیم به تناقض می رسیم . بعد رشته ای در مجموعه ی A را در نظر می گیریم که کمترین فاصله با # را دارد . ثابت می کنیم که این رشته از A حداکثر فاصله ای به اندازه ی 2a را دارد . برای این کار می توان بر روی تعداد رشته ها استقرا زد یا روشی دیگر . ولی به سادگی این قسمت اثبات می شود . در این مسئله مهم این بود که باید می فهمیدیم که اگر دورشته از رشته ای فاصله های x و y را داشته باشند از هم دیگر حداکثر فاصله ی x+y را دارند .

[m_honarmand_j]

سوال دوم روز دوم مرحله ی دوم المپیاد کامپیوتر امسال : سه مجموعه A و B و C وجود دارند . مجموعه ی A+B+C اینگونه ساخته می شود که d عضو این مجموعه است اگر و فقط اگر d=a+b+c باشد که a عضو A و b عضو B و c عضو C است . اگر تعداد اعضای سه مجموعه ی اولیه به ترتیب m و n و k باشد ، حداقل مجموعه ی A+B+C چند عضو دارد؟
جواب : m+n+k-2 تا .
اگر اعضای هر مجموعه را یصورت صعودی مرتب کنیم داریم :
a1+b1+c1<a2+b1+c1<…<am+b1+c1<am+b2+c1<am+b3+c1<� ��<am+bn+c1<am+an+c2<am+bn+c3<…<am+bn+ck .
که تعداد آن ها m+n+k-2 تا است . مثلا فرض کنیم m<=n<=k و اعضای مجموعه ی A از x شروع و به x+m-1 ختم شوند و مجموعه ی B از x شروع و به x+n-1 ختم شود و C از x شروع و به x+k-1 ختم شود آنگاه مجموعه ی A+B+C از 3x شروع و به 3x+m+n+k-3 ختم می شود که در نتیجه تعداد آنها m+n+k-2 تا است .

[m_honarmand_j]

سوال سوم روز اول مرحله ی دوم المپیاد کامپیوتر امسال : 2n نفر به مسافرتی رفته اند . آنها با هم مبادلات پول انجام داده اند که در این بین n نفر سود و n نفر ضرر کرده اند . هنگامی که آن ها به خانه هایشان برگشته اند می خواهند کاری کنند که همه بی حساب شوند . هر کس در خانه ی خود پول دارد . در هر مبادله دو نفر شرکت می کنند . کمترین تعداد مبادله که باید انجام شود تا مطمئن باشم همه بی حساب شده اند چقدر است؟
جواب: در هر مبادله می توان یک نفر که سود کرد و یک نفر که ضرر کرده را شرکت دهیم و اگر مقدار ضرر بیشتر باشد کسی که سود کرده همه ی سود خود را به دیگری داده و بی حساب می شود و اگر سور بیشتر باشد کسی که ضرر کرده به اندازه ی ضررش از دیگری پول گرفته و خود را بی حساب می کند . به این سان در هر مبادله حداقل یک نفر بی حساب می شود و در مبادله ی آخر هر دو نفر بی حساب می شوند در نتیجه 2n-1 مبادله انجام می شود .