المپیاد آرشیو سوالات از گذشته تا کنون

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

باید جوابامونو همین جا بگیم یا فقط برای خودمون حلشون کنیم؟ خود مطرح کننده ی هر سوال جواب هارو چک می کنه؟

اینم یه سوال از دوره ی تابستونی المپیاد کامپیوتر:

http://www.sampadia.com/forum/index.php/topic,5027.0.html

 

[armita]

پاسخ : آرشیو سوالات از گذشته تا کنون

باید جوابامونو همین جا بگیم یا فقط برای خودمون حلشون کنیم؟ خود مطرح کننده ی هر سوال جواب هارو چک می کنه؟

اینم یه سوال از دوره ی تابستونی المپیاد کامپیوتر:

http://www.sampadia.com/forum/index.php/topic,5027.0.html

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

۲n-۱ عدد جعبه داریم و در هر جعبه تعدادی بلال و هویچ وجود دارد. ثابت کنید می توان n تا از جعبه ها رو به صورتی انتخاب کرد که حداقل نصف بلال ها و هویج ها انتخاب شوند.

اگر هیچ کی نظری نداره می خواین راهنمایی کنم ؟

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

۲n-۱ عدد جعبه داریم و در هر جعبه تعدادی بلال و هویچ وجود دارد. ثابت کنید می توان n تا از جعبه ها رو به صورتی انتخاب کرد که حداقل نصف بلال ها و هویج ها انتخاب شوند.

از استقرا استفاده می کنم: پایه ی استقرا (n = 1) بدیهیه!

گام استقرا:

حالت اول: فرض کنید جعبه ی a و b وجود دارند به گونه ای که بلال های a کمتر یا مساوی b باشه و هویج های a هم کمتر یا مساوی b. در این صورت a و b رو حذف می کنیم! طبق فرض استقرا از بین 2n-3 جعبه ی باقی مونده n-1 جعبه با شرایط مورد نظر پیدا می شه! حالا جعبه ی b رو به اونا اضافه می کنیم تا n جعبه با شرایط مورد نظر داشته باشیم!

حالت دوم: هیچ دو جعبه ای ویژگی گفته شده رو ندارند! (در این حالت تعداد بلال ها در هیچ دو جعبه ای برابر نیست و همین طور هویج ها!) جعبه ها رو با شماره های 1 تا 2n -1 شماره گذاری می کنیم به صورتی که تعداد بلال های جعبه ها اکیداً صعودی باشه! (تعداد هویج ها اکیداً نزولی خواهد شد!) و جعبه های دارای شماره ها ی فرد رو انتخاب می کنیم!

 

[armita]

پاسخ : آرشیو سوالات از گذشته تا کنون

....به صورتی که تعداد بلال های جعبه ها اکیداً صعودی باشه! (تعداد هویج ها اگیداً نزولی خواهد شد!)...

چرا؟

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

یک جدول ۱*n داریم و در آن اعداد ۱ تا n به صورت دلخواه نوشته شده اند. اگر عدد k در خانه ی اول قرار بگیرد اعداد خانه های یک تا k به صورت بر عکس قرار می گیرند .
ثابت کنید این کار تمام می شود .

از استقرا استفاده می کنم! برای n = 1 حکم بدیهیه!

گام: اگه اول بازی n توی خونه ی آخری باشه یا در طول بازی n توی خونه ی اولی قرار بگیره و بره آخر، که می شه حذفش کرد و طبق فرض استقرا بازی تمومه! در غیر این صورت n هرگز در خونه ی اول قرا نمی گیره و عددی هم که توی خونه ی آخری هست همیشه سر جای خودش می مونه! حالا کافیه جای عدد n و عدد آخری عوض بشه! باز هم با حذف خونه ی آخری، بازی طبق فرض استقرا تموم می شه!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

چرا؟

توی حالت دوم هیچ دو جعبه ی a و b وجود ندارند که بلال های a کمتر یا مساوی b باشه و هویج های a هم کمتر یا مساوی b ! پس تعداد بلال ها در هیچ دو جعبه ای برابر نیست و همین طور هویج ها! از طرفی اگه هویج های a بیش تر از b باشه باید بلال هاش کمتر باشه!

 

[tiberium]

پاسخ : آرشیو سوالات از گذشته تا کنون

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

(هر کی باهوشه جوابه اینو البته اگه مطمئنه که درسته بذاره ! من هر چی فکر می کنم غیر از روی سوال چیز دیگه ای در موردش به ذهنم نمی رسه!! )

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

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

3 کلاس درس A,B وC داریم .اول همه در A هرکس حداقل S+T دوست دارد.(دوستی دو طرفه)حالا افراد را در A , B ,C طوری تقسیم می کنیم که آن هایی که در B هستند حداقل S دوست در B و آنهایی که در C هستند حداقل T دوست در C داشته باشند.ثابت کنید افراد A را می توان طوری در B و C تقسیم کرد که در B هر کس همچنان حداقل S دوست و هرکس در C حداقل T دوست داشه باشد.

تعریف : x = تعداد زوج هایی در B که با هم دوست هستند * T + تعداد زوج هایی در C که با هم دوست هستند * S

افراد A رو به طور تصادفی توی دو مجموعه ی B و C تقسیم می کنیم! حالا اگه کسی توی B کمتر از S دوست داشت به C منتقلش می کنیم! (توی C حداقل T دوست داره!) و اگه کسی توی C کمتر از T دوست داشت به B منتقلش می کنیم! (توی B حداقل S دوست داره!) توجه کنید که فقط افرادی که قبلاً توی A بودن ممکنه جابجا بشن! در ضمن با این هر جابجایی ممکنه تعداد دوستای بعضی از کسانی که قبلاً با فرد منتقل شده توی یک دسته بودند (و حالا دیگه نیستند!) از حداقل مورد نیاز کمتر بشه ولی مهم اینه که با هر جابجایی متغیر x زیاد می شه! چون x نمی تونه از یه میزان خاص بیشتر بشه این جابجایی ها بالاخره تموم می شه و به یه حالت مناسب می رسیم!

 

[atefeh]

پاسخ : آرشیو سوالات از گذشته تا کنون

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

راحتون غلطه چون نمی تونیم بگیم بدترین حالت چیه واگه می گیم باید ثابتش کنیم
فکر کنم با استقرا حل می شه روش فکر می کنم

 

[tiberium]

پاسخ : آرشیو سوالات از گذشته تا کنون

راحتون غلطه چون نمی تونیم بگیم بدترین حالت چیه واگه می گیم باید ثابتش کنیم
فکر کنم با استقرا حل می شه روش فکر می کنم

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

 

[pouneh]

پاسخ : آرشیو سوالات از گذشته تا کنون

تعریف : x = تعداد زوج هایی در B که با هم دوست هستند * T + تعداد زوج هایی در C که با هم دوست هستند * S

افراد A رو به طور تصادفی توی دو مجموعه ی B و C تقسیم می کنیم! حالا اگه کسی توی B کمتر از S دوست داشت به C منتقلش می کنیم! (توی C حداقل T دوست داره!) و اگه کسی توی C کمتر از T دوست داشت به B منتقلش می کنیم! (توی B حداقل S دوست داره!) توجه کنید که فقط افرادی که قبلاً توی A بودن ممکنه جابجا بشن! در ضمن با این هر جابجایی ممکنه تعداد دوستای بعضی از کسانی که قبلاً با فرد منتقل شده توی یک دسته بودند (و حالا دیگه نیستند!) از حداقل مورد نیاز کمتر بشه ولی مهم اینه که با هر جابجایی متغیر x زیاد می شه! چون x نمی تونه از یه میزان خاص بیشتر بشه این جابجایی ها بالاخره تموم می شه و به یه حالت مناسب می رسیم!

تا اونجا که من فهمیدم در ست نیست.چون x همیشه زیاد نمیشه.مثلا اگه یکی از c به b بره شاید تعداد زوج های دوستی که به b اضافه میشه کمتر از تعداد زوج هایی باشه که از c کم میشه.در ضمن اگه یکی هم تو s,b تا دوست داشته باشه هم تو t , c تا چی کار می کنبد؟

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

x همیشه زیاد نمیشه.مثلا اگه یکی از c به b بره شاید تعداد زوج های دوستی که به b اضافه میشه کمتر از تعداد زوج هایی باشه که از c کم میشه.

فرض کنیم یکی توی C کم تر از T دوست داره! پس توی B بیش تر از S دوست داره! حالا اگه این از C بره به B مقداری که از x کم می شه کم تر از S * T هست ولی مقداری که به x اضافه می شه بیش تر از S * T هست! (به تعریف x دقت کنید!)

اگه یکی هم تو s,b تا دوست داشته باشه هم تو t , c تا چی کار می کنبد؟

اول کار که اعضای A رو به صورت تصادفی توی B و C تقسیم کردم! حالا اگه کسی توی B باشه و تعداد دوستاش توی B بیش تر یا مساوی S باشه که مشکلی نداره! می تونه توی B بمونه!

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

 

[mathematician]

پاسخ : آرشیو سوالات از گذشته تا کنون

جواب های من هم جز این نبود

ولی جدا" وزن زمین مشخصه... ولی من یادم رفت ببینم!

 

[roya]

پاسخ : آرشیو سوالات از گذشته تا کنون

همشون بستگی دارن به...

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

این هم یه سوال قشنگ دیگه:

یه جدول m * n داریم که توی هر خونه اش یه فلش به یکی از 4 جهت اصلی قرار گرفته! یه توپ هم روی یکی از خونه هاست! این توپ هربار در جهت فلشی که الآن روش قرار داره حرکت می کنه و بعدش جهت اون فلش رو 90 درجه ساعت گرد می چرخونه! (مثلاً اگه توپ روی خونه ای باشه که فلشش به سمت چپ هست، اول توپ یه خونه به سمت چپ می ره و بعدش اون فلش می چرخه به سمت بالا!) ثابت کنید توپ حتماً از جدول خارج می شه!!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

این سوال خیلی سخت نیست:

39 تا عدد طبیعی متوالی‌ رو می‌ ‌نویسیم. ثابت کنید حداقل یکی‌ از این اعداد هست که مجموع ارقامش بر ۱۱ بخش پذیره!

 

[Newton]

پاسخ : آرشیو سوالات از گذشته تا کنون

من قبلا حلش کرده بودم الان یادم نیس
توالفبا نیس سوالش؟:d

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

توجه کنید که کلاً توی این سوال (چه برای 12 سکه و چه برای 14 تا) باید هم سکه ی خرابو پیدا کنیم و هم بفهمیم این سکه ی خراب وزنش از بقیه کمتره با بیشتر!

راه حل:

سکه ها رو به به 3 دسته ی 4 تایی تقسیم می کنیم و دو تا دسته ی اول رو با هم مقایسه می کنیم! [مقایسه ی اول]

- حالت اول: دو دسته با هم برابرند! پس سکه ی خراب توی دسته ی سوم هست! دوتا سکه از دسته ی سوم رو توی کفه شماره ی 1 می ذاریم و یه سکه از همون دسته ی سوم رو با یه سکه ی سالم توی کفه ی 2! (سکه های دسته های اول و دوم سالمن!!) [مقایسه ی دوم]

اگه دو کفه با هم برابر بودند، سکه ی باقیمونده از دسته سوم خرابه و با یه بار وزن کردن می شه فهمید که ار بقیه کمتر هست یا بیش تر!! [مقایسه ی سوم]
اگه در مقایسه ی دوم دو کفه برابر نبودند، دو سکه ای که توی کفه ی 1 بودند با هم مقایسه می شن! با این مقایسه هم سکه ی خراب معلوم می شه و هم این که کم تر از بقیه هست یا بیش تر!! [مقایسه ی سوم]

- حالت دوم: دو دسته با هم برابر نیستند! 2 تا از سکه های دسته ی اول رو به همراه یک سکه از دسته ی دوم توی یه کفه می ذاریم و 2 سکه ی باقی مونده از دسته ی اول رو با یک سکه ی سالم توی یه کفه ی دیگه!! [مقایسه ی دوم]

دیگه خودتون برای ادامه اش حالت گیری کنید ...!

- ثابت کنید اگه تعداد سکه ها 14 تا باشه نمی شه با 3 بار وزن کردن سکه ی خرابو پیدا کرد!

اگه روی این فکر کنید، ایده ی حل سوال اصلی (12 سکه) هم دستتون می آد!!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

این هم یه سوال بسیار سخت و بسیار قشنگ:


یک کیک به شکل دایره داریم! قراره یه جشن برگزار بشه! ما نمی دونیم دقیقاً چند نفر مهمون قراره بیاد! فقط می دونیم تعداد مهمون ها یا m نفره و یا n نفر! به ما گفته شده که توی جشن نمی شه از چاقو استفاده کرد و برای همین مجبوریم کیک رو قبل از جشن ببریم! توجه کنید که توی جشن باید کیک به طور مساوی بین مهمون ها تقسیم بشه!

وظیفه ی ما اینه که قبل از جشن به گونه ای کیک رو برش بزنیم که هم بشه اونو بین m نفر تقسیم کرد و هم بین n نفر! حداقل تعداد برش لازم چندتاست؟!!

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

سوال قشنگیه! ارزش فکر کردن داره!!

 

[tiberium]

پاسخ : آرشیو سوالات از گذشته تا کنون

این هم یه سوال بسیار سخت و بسیار قشنگ:


یک کیک به شکل دایره داریم! قراره یه جشن برگزار بشه! ما نمی دونیم دقیقاً چند نفر مهمون قراره بیاد! فقط می دونیم تعداد مهمون ها یا m نفره و یا n نفر! به ما گفته شده که توی جشن نمی شه از چاقو استفاده کرد و برای همین مجبوریم کیک رو قبل از جشن ببریم! توجه کنید که توی جشن باید کیک به طور مساوی بین مهمون ها تقسیم بشه!

وظیفه ی ما اینه که قبل از جشن به گونه ای کیک رو برش بزنیم که هم بشه اونو بین m نفر تقسیم کرد و هم بین n نفر! حداقل تعداد برش لازم چندتاست؟!!

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

سوال قشنگیه! ارزش فکر کردن داره!!

خب من یه حدسی زدم نمیدونم درسته یا نه :-[
ببینید فرض کنید m>n اون وقت میشه اینطوری برش داد
اول کیک رو به m قسمت برش میدیم.بعد هر کدوم از m-n قسمتش رو به n قسمت برش میدیم.مثلا m=5 و n=3 اعداد هستند.برش ما به این صورت است
اول کیک رابه 5 قسمت برش میدیم.بعد 3-5 قسمت یعنی دوقسمت رو برمیداریم وهرکدوم رو به 3 قسمت تقسیم می کنیم.
حالا اگر 5 نفر بیان که این 5/1 ها رو به هرکدوم میدیم.اگر هم 3 نفر بیاد.از این 5 قسمت به هر نفر یه 5/1 میدیم.بعد دو تا 5/1 میمونه که اول هر کدومش رو به 3 قسمت تقسیم
می کنیم بعد به هر کدوم دو تا از این 3/1 ها میدیم.فهمیدید؟؟؟؟!!!!!
پس به عبارتی تعداد برش ها میشه (اگر n<m)
m+n(m-n)=m+nm-n^2
غلطه نه؟؟؟؟؟!!!