کمک در حل سوال المپیاد کامپیوتر و ریاضی

[rezabagheri]

دوستان خواهش می کنم منو در حل این سوالات راهنمایی کنید
سوال شماره 1(المپیاد کامپیوتر)
پدرام و هوشنگ در حال انجام یک بازی دونفره هستند.بازی به این صورت است که n سنگریزه در یک کیسه قرار دارد. بدیهی است که n باید بزرگتر از یک باشد!! نفر اول در شروع بازی بین 1 تا n-1 سنگریزه از کیسه خارج می کند. سپس هر نفر در نوبت خود بین 1 تا k^2-3k+3 سنگریزه از کیسه خارج میکند. در واقع k تعداد سنگریزه هایی است که فرد دیگر در نوبت قبل از کیسه خارج کرده است.برنده بازی فردی است که آخرین سنگریزه را از کیسه خارج کند.در صورتی که همواره پدرام شروع کننده بازی باشد مشخص کنید که به ازای چه n هایی پدرام و به ازای چه n هایی هوشنگ برنده بازی است؟
سوال شماره 2 (المپیاد ریاضی)
مادر ستایش و ملودی برای آن ها یک بازی فکری در نظر گرفته است تا آنهارا سرگرم کند و خودش به کار های منزل برسد. او از آنها خواسته تا یک 45 ضلعی منتظم را در ذهن خود تصور نمایند. سپس از ستایش و ملودی می خواهد که راس های این 45 ضلعی منتظم را با عدد های صفر تا 9 طوری شماره گذاری کنند که برای هر دو عدد مختلف ضلعی وجود داشته باشد که دو راس انتهایی انتهایی آن با این دو عدد شماره گذاری شده باشند.
یه نظر شما این بازی قابل اجراست یا مادر ستایش و ملودی آن هارا مشغول یک معمای بی پاسخ نموده است؟!!
در صورت قابل اجرا بودن بازی مثالی برای ساخت این 45 ضلعی ارائه دهید ودر صورت بی پاسخ بود این معما اثبات خود را ارائه نمایید.

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی(تورو خدا کمممممک!!!)

سوال اول باید دست به قلم بشی و معادله تشکیل بدی و ... پس بی خیال بریم سراغ سوال دوم
تعداد حالاتی که اعداد صفر تا 9 کنار هم قرار میگیرند میشه 9ضربدر 10 تقسیم بر 2 یعنی 45 حالت داریم که دو عدد متفاوت صفر تا 9 کنار هم قرار بگیرند بدون ترتیب یعنی 1و 0 با 0 و 1 هر دو یک حالت یکسانه.
هر عدد چند همسایه داره دو همسایه. حال با توجه به اینکه هر عدد باید باید با نه عدد متمایز دیگه همسایه بشه باید 5 بار تکرار بشه ( 4 بار کم میاد و 4.5 بار هم نداریم) پس حل شد دیگه ما چون 10 عدد متمایز داریم باید حداقل 50 راس داشته باشیم و با توجه به اینکه شکل ما 45 ضلعیه ما فقط 46 راس داریم. و بنابراین معما پاسخی نخواهد داشت.

[rezabagheri]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی(تورو خدا کمممممک!!!)

سوال اول باید دست به قلم بشی و معادله تشکیل بدی و ... پس بی خیال بریم سراغ سوال دوم
تعداد حالاتی که اعداد صفر تا 9 کنار هم قرار میگیرند میشه 9ضربدر 10 تقسیم بر 2 یعنی 45 حالت داریم که دو عدد متفاوت صفر تا 9 کنار هم قرار بگیرند بدون ترتیب یعنی 1و 0 با 0 و 1 هر دو یک حالت یکسانه.
هر عدد چند همسایه داره دو همسایه. حال با توجه به اینکه هر عدد باید باید با نه عدد متمایز دیگه همسایه بشه باید 5 بار تکرار بشه ( 4 بار کم میاد و 4.5 بار هم نداریم) پس حل شد دیگه ما چون 10 عدد متمایز داریم باید حداقل 50 راس داشته باشیم و با توجه به اینکه شکل ما 45 ضلعیه ما فقط 46 راس داریم. و بنابراین معما پاسخی نخواهد داشت.

دمت گرم :surprised:
حلش کردی؟!!! :wow: :wow:(ایول)
آقا ولی من نفهمیدم چجوری حل شد!!!
میشه یکم بیشتر توضیح بدید؟؟؟
خیلی خیلی ممنون

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی(تورو خدا کمممممک!!!)

یادش بخیر، المپیاد
ممنون از میثم بخاطر پاسخی که داد
در مورد سوال اول:
به نظر میرسه جواب اینه: پدارم میتونه همیشه برنده باشه!
یک سری بازی هایی هست که در اون ها استاتژی برد مطرح میشه
و در برخی بازیها یشه اثبات کرد که اگه نفر A بازی رو شروع کنه
"میتونه" طوری بازی کنه که "حتما" برنده باشه!
و در این جا پدرام میتونه طوری بازی کنه که حتما برنده باشه! :eek:
اما چطور؟ :read:
به فرمولی که داده شده دقت کنید:
"k^2-3k+3 در واقع k تعداد سنگریزه هایی است که فرد دیگر در نوبت قبل از کیسه خارج کرده است"
خب حالا بیایم و مقادیر 1 و 2 و 3 و 4 و ... را در فرمول جاگذاری کنیم:
k=1 : 1
k=2 : 1
k=3 : 3
k=4 : 7
و ...
حالا من با دو تا عدد اول کار دارم!
یعنی k=2 و k=1
بیایم وضعیت های مختلف رو بررسی کنیم:

- اگه تعداد سنگریزه ها فرد باشه
پدرام اگه در حرکت اول 1 سنگریزه برداره
هوشنگ مجبوره در حرکت دوم یکی برداره
حرکت سوم پدرام مجبوره یکی برداره
الی آخر!
پس اگه تعداد فرد باشه و پدرام با یکی شروع کنه
همواره سنگریزه آخر برای پدرام میمونه
(در اینجا N>=3 باید باشه)

- اگه تعداد سنگریزه ها زوج باشه
کافیه در حرکت اول پدرام 2 تا سنگریزه برداره
در حرکت دوم هوشنگ باید 1 ای برداره
در حرکت سوم پدرام باید 1 ای برداره الی آخر ...
مجموع دو مرحله ی اول میشه 3، بعد در هر 2 مرحله، 2 سنگریزه خارج میشه
یعنی مجبوره خارج بشه!
بنابراین همیشه در نهایت سنگریزه ی آخر رو پدرام برخواهد داشت
( در اینجا N>=4 باید باشه)

فقط در حالت n=2 هوشنگ همواره برنده ست.

...

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

ممنون از اقای رستمی
مرحله به مرحله توضیح میدم که اگر هر مرحله مبهم بود مشخص باشه
1- مساله از ما خواسته اعداد 0 تا 9 رو روی رئوس چند ضلعی بگذاریم که تعداد رئوس در اینجا 45 هستش (نمیدونم چرا در پست قبلا 46 گفتم :eek: بهر حال حواسم نبوده)
2- طبق شرط مساله باید هر ترکیبی از اعداد صفر تا 9 مثلا 0و1 -- 1و2 -- 2و5 و ... که در نظر بگیریم یک ضلعی وجود داشته باشد که اعداد رئوس ان، عدد مورد نظر باشد، 3- برای رسیدن به شرط دو هر کدام از اعداد صفر تا 9 باید با تمام اعداد دیگر غیر از خودش یک راس همسایه داشته باشد. یعنی هر عدد با 9 عدد همسایه باشد
4- هر عددی که در هر راس وجود دارد تنها دو همسایه می تواند داشته باشد.
5- اگر در 45 راس این چند ظلعی هر عدد 4 بار تکرار شود در نتیجه حداکثر میتواند با 8 عدد متمایز دیگر همسایه شود
6- بنابراین برای همسایگی با تمام 9 عدد دیگر حداقل هر عدد باید 5 بار در رئوس مختلف چند ضلعی قرار گیرد.
7- اگر شرط 6 را برای هر 10 عدد در نظر بگیریم هر عدد به 5 راس و نهایت به 50 راس برای کل اعداد نیاز داریم
8- در حالی که ما تنها 45 راس داریم پس حل مساله غیر ممکن خواهد بود.

[rezabagheri]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

بسییییییار ممنون :applause:
هم پاسخ جناب رستمی رو متوجه شدم هم آقای عزیزی عزیز :mrgreen:
اگه در حل این سوال هم بتونید منو یاری کنید دیگه عالی میشه :redface:
سوال شماره 3
پس از بازدید دانش آموزان مدرسه ایمان اینا (!!!) از کارخانه ی تولید جغجغه معلم از آنها خواست گزارشی تهیه کنند و جالب ترین نکته بازدید از دید خود را در آن شرح دهند. گزارش ایمان به این شرح بود:
در مدت زمانی که ما در این کارخانه حضور داشتیم !n جغجغه تولید شد. در قسمت بسته بندی این !n جغجغه به n کارتون هر کدام حاوی !(n-1) جغجغه تقسیم شدند و هر کارتون به n-1 کارتون حاوی !(n-2) جغجغه تقسیم شد و هریک از این کارتون ها هم به n-2 کارتون تقسیم شدند که هریک شامل !(n-3) جغجغه بودند و الی آخر....
(تا کارتون حاوی یک جغجغه)
پس از ارائه گزارش معلم که از دقت نظر ایمان خوشش آمده بود برای محک زدن ایمان از او پرسید : به نظر تو این کارخانه به چند طریق می تواند این کار را انجام دهد؟!!!
ایمان پس از کمی فکر کردن به این سوال از هوش رفت! شما با یافتن پاسخ سوال معلم به ایمان کمک کنید تا شاید بهوش بیاید!

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

من یه مقدار منظور از چند طریق رو متوجه نشدم ولی بر اساس درکی که از مساله کردم جواب زیر ارائه میگردد
اگر تمام محصولات تولیدی که !n است را در یک ردیف مستقیم بچینیم تعداد حالت ها میشود تعداد چینشهای این !n محصول در یک ردیف که ردیف اول !n حالت ردیف دوم !(n-1) و همینطور در ردیف !n ام 1 حالت خواهیم داشت و تعداد حالات که ضرب اینها میشه
خواهد شد: n فاکتوریل فاکتوریل یا !!n که اگر مثلا n برابر با 1000 باشد که هیچ برابر 10 هم باشد ماشین حساب مهندسی ویندوز بینهایت میزنه !!!!!!!!!!!!!!

[rezabagheri]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

من یه مقدار منظور از چند طریق رو متوجه نشدم ولی بر اساس درکی که از مساله کردم جواب زیر ارائه میگردد
اگر تمام محصولات تولیدی که !n است را در یک ردیف مستقیم بچینیم تعداد حالت ها میشود تعداد چینشهای این !n محصول در یک ردیف که ردیف اول !n حالت ردیف دوم !(n-1) و همینطور در ردیف !n ام 1 حالت خواهیم داشت و تعداد حالات که ضرب اینها میشه
خواهد شد: n فاکتوریل فاکتوریل یا !!n که اگر مثلا n برابر با 1000 باشد که هیچ برابر 10 هم باشد ماشین حساب مهندسی ویندوز بینهایت میزنه !!!!!!!!!!!!!!

من متجه نشدم!!!
آیا به جواب خودتون مطمئنید؟
در ضمن یه سوال در مورد پاسخ آقا رستمی (فعلا که خودشون نیستن از شما می پرسم!!)
خلاصه برای اینکه پدرام برنده شود n باید مساوی چند باشد؟؟؟؟

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

یه مساله جایگشتیه در عین سر راست بودن اینجور سوالاتی نکات ریز زیاد دارند به نظر خودم که درسته حالا دوستای دیگه بیان نظر بدن بهتره

در مورد سوالی که آقای رستمی زحمت کشیدن هم اگر خودشون جواب بدن بهتره ولی فکر کنم برای n های بزرگتر از سه پدرام همیشه برندس

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

در مورد سوالی که آقای رستمی زحمت کشیدن هم اگر خودشون جواب بدن بهتره ولی فکر کنم برای n های بزرگتر از سه پدرام همیشه برندس

فقط در حالت n=2 هوشنگ همواره برنده ست.

بستگی داره که n فرد باشه یا زوج
چون پدرام باید از دو استراتژی مختلف استفاده کنه برای هر حالت!

در موردسوال 3:
با توجه به پاسخ میثم عزیز (گفتم میثم عزیز نه میثم عزیزی )
منم موافقم که این سوال کمی ابهام داره
و یکی از جوابها همونیه که میثم گفت!
(برای درک بزرگیه عددی که میثم گفت !!4 و !!5 رو حساب کنید! )

از دید دیگه ای هم میشه به قضیه نگاه کرد:
فرض کن در مرحله ی اول n تا جعبه داری که داخل هر کدومش ! n-1 جغجغه هست
(خداییش من با نحوه ی موضوعات سوالات المپیاد مشکل دارم!
آخه کارخونه ی جغجغه؟؟؟ :eek:
از هر 10 تا سوالش 2-3 تا درست حسابین بقیه تخیلی
بعد حالا شما برو سوالات المپیاد آمریکا یا روسیه رو ببین! بماند... :read
خب در مرحله ی اول که n تا جعبه داریم پس میشه با !n حالت، اینا رو چید
(یعنی جعبه های ! n-1 ای را در اونا چید)
باز هر جعبه خودش همین وضعیت رو داره
یعنی در مرحله دوم ! n-1 حالت میشه چید.
در مرحله سوم ! n-2 حالت الی آخر ...
اما یک نکته ی دیگه داره!
زمانی که در مرحله ی اول میگیم n جعبه داریم
و باید جعبه های !n-1 را در اونا بذاریم
باز در اینکه هر جعبه کدوم جغجغه قرار بگیر حالتهای زیادی پیش میاد
یعنی !n حالت دوباره پیش میاد!
و اگه تا آخر همینطر در نظر بگیریم
تعداد کل حالات میشه:

n! * n! * ... * n!

یعنی !n به توان !n :eek: :eek: :eek:
چی میگه؟ :angry:
...
:read:

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

با توجه به پاسخ میثم عزیز (گفتم میثم عزیز نه میثم عزیزی )

من که نمیتونم شناسنامم رو عوض کنم ولی باید یک واژه معادل کلمه عزیز پیدا کنم تا مشکل حل بشه

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

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

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

به المپیاد و سوالای المپیاد خیلی علاقه داشتم
یکی از تفریحات سالم دوران دبیرستان حل کردن این سوالا
به صورت گروهی بود! بعدشم کل کل
اتفاقا کتابهای المپیاد در زمان ما هم همینطور بود
کلی باید میگشتیم تا بتونیم سوالاشو پیدا کنیم
استاد شهریاری هم که دیگه از بزرگان بود:
پرویز شهریاری
...
:read:

[rezabagheri]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

آقا اصلا من مفهوم این سوال 3 رو به کلی نمیفهمم :cry:(اصلا هیچی)
سوال 3 رو وللش بیاین رو این یکی سوال فکر کنیم:
سوال 4:
پادشاه سرزمین اوتابا یک دفتر 1024 صفحه ای به اوتک داده است که در هر صفحه از آن یک عدد نوشته شده است. اوتک یک دفتر چرک نویس با N برگ نیز در اختیار دارد. به اوتک مدتی وقت داده شده است. در این مدت می تواند به هر میزان که دوست دارد در دفتر چرک نویس خود بنویسد با این شرط که در هر یک از صفحات دفتر چرک نویس فقط می تواند حداکثر یکی از اعدادی که در دفتر اصلی نوشته شده بود را بنویسد. پس از پایان وقت داده شده توسط پادشاه اوتک دیگر نمی تواند چیزی بنویسد. سپس پادشاه از او سوالاتی به شکل و سیاق زیر می پرسد:
ای اوتک!! بزرگترین عدد بین اعداد دفتر من از صفحه i ام تا صفحه j ام (i و j بین 1تا 1024 و j>=i ) چه عددی است؟
اوتک برای پاسخ گویی به هر کدام از این سوالات حق دارد حداکثر m صفحه از دفتر چرک نویس خود را دیده و سپس به سوال پاسخ دهد. به اوتک کمک کنید که با استفاده از دفتر خود به سوالات پادشاه پاسخ دهد
حالت اول)اگر پادشاه به اوتک اجازه دهد فقط یک صفحه از دفتر چرک نویس خود را ببیند و دفتر اوتک نیز 524800 صفحه داشته باشد به نظر شما اوتک چه کار خواهد کرد؟
حالت دوم)اگر پادشاه به اوتک اجازه دهد فقط دو صفحه از دفتر چرک نویس خود را ببیند و دفتر اوتک نیز 10240 صفحه داشته باشد :به نظر شما اوتک چه کار خواهد کرد؟
ممنون

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

سوالش کمی ابهام داره!
من نقش اون m رو نفهمیدم چیه این وسط! :eek:

[epec.empror]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاض

سوالش کمی ابهام داره!
من نقش اون m رو نفهمیدم چیه این وسط! :eek:

دوستان حالت اول که خیلی راحته p=تعداد صفحات دفتر پادشاه مرتبه حل سوال 2/(1+p(p هستش
صفحه اول چرک نویس میشه بزرگترین عدد بین صفحات 1 تا 1024 دفتر پادشاه
صفحه دوم چرک نویس میشه بزرگترین عدد بین صفحات 1 تا 1023 دفتر پادشاه
صفحه سوم چرک نویس میشه بزرگترین عدد بین صفحات 1 تا 1022 دفتر پادشاه
و همینطور تا صفحه 1024 چرک نویس میشه بزرگترین عدد بین صفحه 1 تا 1 دفتر پادشاه
صفحه 1025 میشه بزرگترین عدد بین صفحات 2 تا 1024 دفتر پادشاه
صفحه 1026 میشه بزرگترین عدد بین صفحات 2 تا 1023 دفتر پادشاه
و ...
و همیطور که پیش بریم می بینیم که با داشتن 524800 صفحه چرک نویس میشه با یک بار نگاه کردن به چرک نویس جواب پادشاه را داد
نمیدونم از مرتبه اجرای الگوریتم چیزی می دونید یا نه ولی اگر میدونید بهتره که بدونید مرتبه اجرایی این الگوریم O(nهستش