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

[احسان]

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

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

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

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 بار هر کدوم رو فشار دهیم به جز آخری که باید یک بار آن را فشار دهیم.