امتیاز موضوع:
  • 87 رأی - میانگین امتیازات: 3.08
  • 1
  • 2
  • 3
  • 4
  • 5
نمونه سوالات المپیاد کامپیوتر
#1
[تصویر:  me.jpg]
1) ۲n-۱ عدد جعبه داریم و در هر جعبه تعدادی بلال و هویچ وجود دارد. ثابت کنید می توان n تا از جعبه ها رو به صورتی انتخاب کرد که حداقل نصف بلال ها و هویج ها انتخاب شوند.

2) یک شبکه ی ۱۰ * ۱۰ داریم . می تونیم هر نقطه رو آبی یا قرمز کنیم به شرطی که هر نقطه ی آبی هم سمت چپ و هم پایینش حتما آبی باشه . به چند روش می تونیم این کار رو انجام بدیم؟

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

4) در یک صفحه n نفر قرار دارند و فاصله ی هر دو نفر یکتا است. در زمانی مشخص هر فرد به نزدیکترین فرد به خود شلیک می کند ! ثابت کنید در آخر حداقل یک نفر زنده می ماند.
8 ضلعی منتظم ABCDEFGH را در نظر بگیرید.در لحظه ی اول مگسی در نقطه ی A ایستاده است و او در هر حرکت می تواند به سر دیگر ضلعی از 8 ضلعی که اکنون روی آن ایستاده بپرد.وقتی که مگس به نقطه ی E برسد متوقف می شود.رابطه ی بازگشتی برای A n بیابید.
A n=تعداد روش های پرشی که مگس پس از دقیقا 2n حرکت متوقف می شود.

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

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

7) 100 نفر به ترتیب دور یک دایره ایستاده اند.از اولین نفر شروع می کنیم و یکی در میان آدم ها را می کشیم (مثلا از روی نفر اول می گذریم و نفر دوم را می کشیم.)
شماره ی آخرین نفری که زنده می ماند چند است؟

8) در یک فروشگاه شکلات های 1 تا k گرمی به فروش می رسد.یک معلم می خواهد برای هر n دانش آموزش یک شکلات بخرد.به چند روش می تواند این کار را انجام دهد به شرطی که مجموع وزن شکلات ها عددی فرد شود.

9) يه اتاق داريم كه توش 3 تا كليده و يه اتاق ديگه كه توش 3تا لامپ داريم ؛ فقط با يه بار وارد شدن به هريك از اين اتاقا مي خوايم تشخيص بديم كه هر لامپ براي كدوم كليده. ( اين واسه ثبت نام كارمنداي مايكروسافت بوده. جوابش البته ساده س ! فكر كنين )

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

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

توضیح: برش ها روی شعاع کیک هستند! (اگه k برش بزنیم، کیک به k قسمت تقسیم می شه!) لازم نیست که اندازه ی قطعات با هم برابر باشه! در ضمن اشکالی نداره که توی مهمونی به یک نفر بیش تر از یک تکه کیک داده بشه! فقط مهم اینه که مجموع کیکی که به افراد داده می شه با هم برابر باشه!!
می خواهیم یک جدول m * n را با 1 و -1 پر کنیم! (یعنی توی هر خونه یا 1 بذاریم یا -1) به طوری که ضرب اعداد هر سطر و همین طور ضرب اعداد هر ستون برابر -1 بشه!

ثابت کنید:
الف) اگه باقیمانده ی m و n بر 2 یکسان نباشه، این کار ممکن نیست
ب) اگه باقیمانده ی m و n بر 2 یکسان باشه، تعداد حالات پر کردن جدول برابره با 2 به توان (m-1)(n-1)

12) توی یه شهر جادویی، جدیداً نخ های جادویی ساخته شدند! ویژگی جالب نخ جادویی اینه که اگه یه سرش رو آتش بزنیم، دقیقاً یک دقیقه طول می کشه تا آتش به سر دیگه ی نخ برسه! البته این نخ کاملاً یک نواخت نیست! (یعنی بعضی قسمت های نخ نازک تر هستند و بعضی قسمت ها ضخیم تر!) و به همین خاطر سرعت پیشروی آتش در طول نخ ثابت نیست!

با داشتن 2 نخ جادویی (و یک بسته کبریت!!) چه جوری می شه 45 ثانیه رو اندازه گرفت؟!

13) ثابت کنید به ازای هر عدد طبیعی n می شه اعداد 1 تا n رو توی یک صف قرار داد به گونه ای که میانگین هیچ دو عددی، بین خود اون دو عدد قرار نگیره!!
مثلاً اگه n = 4 می شه این دنباله رو ساخت: 2 4 1 3
یا اگه n = 6 باشه: 4 2 6 3 1 5
(مثال ها یه جورایی راهنمایی هستند!!)

14) فرض کنید S مجموعه ی اعداد طبیعی کوچک تر یا مساوی n باشه! یک زیرمجموعه ی ناتهی از S رو در نظر بگیرید! اگه میانگین اعضای این زیرمجموعه، یک عدد طبیعی باشه، به این زیرمجموعه می گیم یه "زیرمجموعه ی خوب"! (و اگه میانگین اعضاش، طبیعی نباشه می گیم "زیر مجموعه ی بد"!!)
ثابت کنید که اگه n فرد باشه، تعداد زیر مجموعه های خوب S فرده و اگه n زوج باشه، تعداد زیرمجموعه های خوب S هم زوجه!!

15) رض کنید به اعدادی که فقط از ارقام 1 و 0 تشکیل شده باشند، می گیم اعداد ایده آل!
ثابت کنید به ازای هر عدد طبیعی n، عدد ایده آلی وجود داره که بر n بخش پذیره!
(مثلاً اگه n = 14 عدد ایده آل 1111110 بر 14 بخش پذیره!!)

16) فرض کنید 10 عدد طبیعی متمایز داریم و همگی این اعداد هم از 107 کوچک ترند! ثابت کنید می شه 2 زیر مجموعه ی مجزا از این اعداد رو انتخاب کرد به گونه ای که مجموع اعضای این دو زیر مجموعه برابر باشند!
(راهنمایی: به اصل لانه ی کبوتری ربط داره!!)

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

18) یه جزیره داریم؛ هر کسی توی این جزیره چشمش ابی باشه انگار که یه مرض مهم داره
و هر کس که متوجه بشه چشمش ابیه فردای روزی که فهمید خودش رو میکشه
ثابت کنید بعد از یه زمانی(چه زمانی) همه ی n تا چشم ابیه جزیره خودشون رو میکشن

19) یه سری نقطه سیاه و سفید داریم توی یه صفحه با این شرایط:
هر 4 تایی رو که انتخاب کنیم میشه با یه خط، سفید ها رو از سیاه ها جدا کرد
ثابت کنین که کلا می شه با یه خط سفید ها رو از سیاه ها جدا کرد!

20) 1000 تا توپ داريم هر كدوم از 000 تا 999 شماره گذاري شده اند! 100 تا جعبه هم داريم كه از 00 تا 99 شماره گذاري شده اند. هر توپ رو ميشه تو جعبه اي گذاشت كه شماره ي اون جعبه از حذف كردن يكي از رقم هاي توپه بدست بياد يعني توپ 123 رو ميشه تو جعبه هاي 12 ، 13 يا 23 گذاشت.
الف) ثابت كنيد ميشه همه ي توپ ها رو تو 50 تا جعبه گذاشت.
ب) ثابت كنيد تو كمتر از 40 تا جعبه نميشه گذاشت.
...I dont know wat to Do... n even if i do... nothin changes
...Im Confused... Scared... So scared of the future ahead of me
!! Ya wat i have never been
!! is it my fault? well maybe ya... because im not Ordinary
پاسخ
 سپاس شده توسط Elham ، LiliaN


موضوعات مرتبط با این موضوع...
موضوع نویسنده پاسخ بازدید آخرین ارسال
  لیست کامل منابع المپیاد کامپیوتر M@h$A 1 5,820 24-02-2014، 03:52 PM
آخرین ارسال: هلنووووو
  آشنایی با مراحل المپیاد کامپیوتر M@h$A 0 2,040 06-01-2012، 12:33 AM
آخرین ارسال: M@h$A
  معرفی المپیاد کامپیوتری های مدال دار M@h$A 0 1,456 13-12-2011، 10:41 PM
آخرین ارسال: M@h$A

پرش به انجمن:


کاربرانِ درحال بازدید از این موضوع: 1 مهمان