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

[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
غلطه نه؟؟؟؟؟!!!