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

پاسخ به شبهات (زنگ امتحان سری چهارم)

جمعه, ۵ ارديبهشت ۱۳۹۳، ۱۱:۲۳ ق.ظ

سلام بچه‌ها


یه مساله‌ای رو توی نظرات دیدم که فکر می‌کنم مشکل خیلی از شما باشه. لطفا این پست رو دقیق بخونید و روش فکر کنید تا یکی از مهمترین شبهاتی که مطرحه برطرف شه:

نظری که ارسال شده بود:

آقای عابدی دیفالت اینه که همه میدونیم یه سری آدم فهیم تو دوره هستن، ولی شخص بنده دیدم بخاطر اثبات نکردن n-1 یال بودن درخت، ۱۳ نمره کم شده تو مرحله ۲!


من سعی کردم یک نکته‌ای رو سر همه‌ی کلاسام به بچه‌ها توضیح بدم! این مشکلیه که اکثرا دارن و فکر می‌کنن بخاطر اثبات نکردن قضایای بدیهیه.

مثل چیزی که گفتی قراره از n-1 یال بودن یه درخت استفاده کنیم. فرض مسئله اینه که درخت T داده شده و ما می‌خوایم از n-1 یال بودن گراف‌مون استفاده کنیم. دو جور میشه این کار رو انجام داد:

* در این درخت n-1 یال داریم و ...
مقایسه کنید با
می‌دانیم هر درخت n-1 یال دارد، در نتیجه درخت T نیز n-1 یال خواهد داشت و ...

من اگه مصحح باشم برام مهمه بفهمم از کجا نتیجه گرفتی این گراف n-1 یال داره. همونطور که می‌بینی توی نوشته‌ی دومی هیچگونه ارجاعی به هیچ کتابی داده نشده و همچنین هیچ اثباتی هم مطرح نشده. فقط مصحح متوجه میشه این نتیجه رو از آسمون نیاوردی و یا از حکم سوال حدس نزدی.

به عنوان یه مثال سخت‌تر فرض کنید نیاز داریم بین n و 10n یه عدد اول در نظر بگیریم و ازش استفاده کنیم. به دو روش میشه این کار رو انجام داد:

* یک عدد اول همانند p در نظر بگیرید که n<p<10n و ...
مقایسه کنید با
* می‌دانیم به ازای هر n، حداقل یک عدد اول وجود دارد که n<p<2n. عدد p با این شرایط را در نظر بگیرید و ...

(توی استدلال دوم از این قضیه استفاده شده: به ازای هر n>1، حداقل یک عدد اول وجود دارد که n<p<2n)
فرض کنید من (به عنوان دانش‌آموز) این قضیه رو نمیدونستم. مسلما همون متن اولی رو می‌نوشتم و اصلا حواسم نبود که عدد اولی این بین وجود داره یا نه. خب باید از من بخاطر اینکه بدون استدلال چنین عددی رو در نظر گرفتم نمره کم بشه.
شما خودتون تا حالا این قضیه رو دیده بودید؟ احتمالا مثل من همون متن اولی رو می‌نوشتید، در صورتی که هیچ استدلالی براش نداشتید. به نظرتون باید به استدلال اول نمره کامل داد؟ این استدلال با استدلال دوم که با آگاهی کامل عدد رو انتخاب کرده فرقی نداره؟

نتیجه‌گیری: توی نوشته‌هاتون استدلال‌ها باید کامل باشه. نیازی به اثبات قضایای بدیهی نیست. ولی اینکه از کجا نتایج‌تون رسیدید خیلی مهمه! اگه این پست رو متوجه نشدید دوباره و دوباره بخونید تا شیرفهم بشید.

اگه هنوز متوجه نشدید بگید تا توضیح بیشتر بدم ...
موافقین ۰ مخالفین ۰ ۹۳/۰۲/۰۵
جواد عابدی گزل آباد

سری چهارم

پاسخ به شبهات

زنگ امتحان

نظرات  (۱۸)

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

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

مثالی که آوردی هم بدون اثبات قابل استفاده است، در صورتی که به طور درست و کامل صورت قضیه رو بیان کنی. من به شما این قول رو میدم که قضایای این چنینی قرار نیست که توی مرحله دو یکبار دیگه اثبات بشن!!! (من به شخصه هیچ‌وقت چنین کاری نکردم).
میگم برای مرحله سوم دوره 23 میشه مثل سال قبل جوابارو آماده کنید؟متشکرم.
پاسخ:
خب در پست‌های قبلی تمامی سوال‌های سال قبل حل شده‌اند و قابل بازیابی هستند.

به هر حال تا مرحله سوم باید ببینیم کی زنده است کی مرده!
خیلى خیلى ممنون از پست هاى مفیدتون.
بازم ممنون!
سلام

لطفا دقیقا برای این قضایا بگید که نیاز به اثبات هست یا اینکه صرفا بگیم منبع گراف وست (برای گرافی هاش)، کافیه:
1- هال
2- کونیگ
3- ویزینگ
4- وجود یک مسیر از v به u در صورت وجود یک گشت از v به u
5- وجود یک دور فرد در یک گشت فرد
6- قضیه کوچک فرما
7- لم های بدیهی مثل اینکه اگه S1, S2 پرانتز گذاری معتبر یاشند، S1S2 هم معتبر است.

اگه قضایای پرکاربرد دیگه هم به ذهنتون میرسه، خواهشا بگین که ما یه حضور ذهن سر امتحان داشته باشیم.

خیلی ممنون
موفق باشید!
پاسخ:
علیک سلام

من صورت قضایای کونیگ و ویزینگ رو یادم نیست (معمولا قضایا رو به اسم حفظ نمی‌کنم حتی این قضایای معروف رو).

ولی بقیه مواردی که نوشتی همشون قابل استفاده هستند.
قضایای پرکاربرد دیگه هم خب:
زیر گرافی دو بخشی داریم که درجه هر راس بزرگتر مساوی نصف هست
درجه ریوس زوج باشه و گراف همبند ، گراف اویلریه 
یال برشی است اگر و تنها اگر تو دور نباشه 
گراف بدون دور فرد دو بخشیه 


پاسخ:
اینایی که نوشتی:
1. این قضیه فکر نمی‌کنم جایی به صورت قضیه باشه. من یادمه توی مسائل آورده شده. پس باید ثابت بشه.
بقیه‌شون همه قضایای اثبات شده هستند!

میشه دیگه ادامه ندید به نوشتن قضایا!!! بابا شما خیلی جدی گرفتین استفاده از قضایا رو. اکثر سوالا رو بدون قضیه حل می‌کنن ...
ببخشید فقط برای اینکه اون 2 تا قضیه کونیگ و ویزینگ رو مطمئن بشم.
1- کونیگ : در هر گراف دو بخشی داریم
اندازه ماکسیمم مچینگ = اندازه مینیمم پوشش راسی

2- ویزینگ : در هر گراف G داریم
دلتا + 1 => (عدد رنگی یالی G) => دلتا

ببخشید آخریش بود دیگه!!
خیلی ممنون!
موفق باشید!
پاسخ:
هر دو قابل استفاده‌اند. ولی ویزینگ مطمئنا استفاده نمیشه ...
salam.man ke akharesh nafahmidam ke bayad chia esbat konam chia na. :(
sar emtehan ke raftam age esbatesha balad boodam minevisam vagana hamin joori ke shoma goftin kar mikonam.  :D
پاسخ:
چی رو متوجه نشدی؟ اگه خیلی پیچیده شده بدون که:
توی آزمون‌ها نیازی به اثبات قضایا نداری. ولی باید به مصحح توضیح بدی که چجوری نتیجه‌گیری می‌کنی!
والا من که تاحالا هرچی م2 دادم هیچکدوم از قضیه هایی که تو وست خوندم به کارم نیومده! یعنی شاید بوده سوالی که با اون قضایا هم حل میشده اما بدون اونها ساده تر حل میشدن!
جواب های مرحله سوم ها رو تا 22 گذاشتین!ولی خب درسته. باید ببینیم تا اون موقع کی زندست و کی مرده!
ببخشید میشه برای آزمون تستی هم یک استراتژِی بدید تستی هم برای خودش مشکل بزرگیست 
پاسخ:
توضیحات در طی یک پست داده شد.
سلام. من برای سوال حلزون در آوردم k=98 . اگه میشه یکی بگه جوابم درسته یا نه (البته خودم یه اثباتی کردم ولی ممکنه باگ بخوره ! )

و یه سوال دیگه شکارچیان خرس : من درآوردم همیشه ممکنه و بیشینش کف 4/(n^2) است
@حسین
98 درسته
اثبات برای 98 تا چجوریه؟متشکر. 
آقا حوزه امتحانى ما سالن اجتماعات مدرسمونه بعد صندلى هاش دسته دار نیستن، بهمون تخته چوب میدن بذاریم رو پامون ازش به عنوان میز استفاده کنیم؛ کمر و گردنمونم خشک شه! خدایا عدالتت کجاست؟؟ ...!
الان ما چطور باید با این بحران روانى مقابله کنیم؟!
پاسخ:
حوزه‌ی امتحانی‌ات کجاست؟ کدوم شهر؟

بحران روانی؟ این توضیحاتی که دادی بیشتر بحران جسمانیه! نمیدونم شرایط مدرسه‌تون چجوریه، ولی چون مدرسه‌ی خودتونه، می‌تونی با مسئولینش از قبل صحبت کنی تا این مشکل رو برطرف کنن.
من کلی نوشته بودم که پاک شد (برای اثبات ! ) برای همین ایندفعه فقط کلیتو میگم : فقط دو تا خونه از چار تای گوشه ای هستن که اگه رنگ آمیزی کنیم کل جدولو به صورت شطرنجی  زوجیت حرکت ما (از سیاه به سفید و بالعکس ) رو به هم میزنن . اگه از اونا پرش بشه می فهمیم و طبیعتا از اونی که نزدیک تریم بهش پرش شده (از آخرین باری که دیدیم ) اما اگه از اون یکی بریم که زوجیت حرکتو به هم نمی زنه برای این که نشون بدی نمیشه از جایی که برای اولین بار دیده میشی و بعدش میری میپری (منظورم خونه ی پایین راسته ) و بعدش بری یه جایی که بدون پرش در تعدادی کمتر مساوی صبح 99 ام میشه رفت باید دو تا نا مساوی تشکیل بدی که یکیش قدر مطلقیه . با حالت بندی می تونی بفهمی که جواب نداره.
منظورم از استفاده از قدر مطلق اینه که برای رفتن از خونه ی (a,b) به خونه ی (c,d) حداقل 1+ |a-c| + |d-b| طول میکشه

ببخشید که توضیحش بد شد چون اگه خودم بودم عمرا نمی فهمیدم :)

آقای عابدی میشه یه سری نصایح هم برای امتحان تستی بزارید 
ممنون 
پاسخ:
توضیحات آزمون تستی در قالب یک پست داده شد.
1+ |a-c| + |d-b|

در مورد قدر مطلق قبلی باید بگم |a-c| + |d-b| است (حداقل تغییرات زمان برای جابه جایی چون من حالت اولیه رو یک گرفته بودم یه 1+ گزاشته بودم )


میشه یه نفر لطفا جواب سوال 1 و 2 ی دوره ی 83 رو بنویسه :)
salam.
@ hossein:
soale 1 sale 83 mishe ba 5 harekat vali esbat kamine boodanesha daghigh balad nistam.
soale 2 sale 83 ham mishe na lozooman.mesal naghzesham ine ke age 5 ta mohre az  adad k dashte bashim baad az ye modati dobare 5 ta mohre az adad 2k+2 ham khahim dasht.khodet emtehan koni behesh miresi.
bebakhshin yekam bad tozih dadam.

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی