کلید مرحله 2
سلام بچه ها. این کلیدی هست که شاززز آماده کرده برای روز اول تستی. امیدوارم کلید ما درست باشه. احتمالا جواب خیلی از سوالا درست خواهد بود. اگه که به نظرتون جواب سوالی غلط میومد میل بزنید به شاززز ما میخونیم راه حلتون رو. پاسخ نامه تشریحی هم هر وقت آماده شد میذاریم.
2) 55
3) 10
4) 4
5) 6!
6) 46
7) 7
8) 2 * 3^5
9) 4
10) C(8,4)^2
11) 57 / 128
12) 6
13) 2
14) 10!/5!
15) C(10,5)
16) 342
17) 16
18) 9
19) 6
20) 5
________________________________________________________________________________________________________
خب الان آزمون تموم شده و فکر کردن بهش هیچ فایده ای نداره. اول دوما برن شروع کنن به کد زدن مستقل ازین که چی کار کردی توی آزمون. سوما هم یک برنامه ریزی درست بکنن و هم نهایی بخونن هم کد بزنن تا رستگار شن. سعی میکنم اولین وقتی که داشتم فکر کنم روی سوالای تشریحی و یک پاسخ نامه ای راهنمایی ای چیزی بذارم.
از آقایان محمد مهدی جهان آرا ,مهرداد میری ,آرمان کریمی و خانم ها بهار سلامتیان و کیمیا همتی به خاطر اینکه منو کمک کردن ممنونم. اینم یک پاسخ نامه یا راهنما برا سوالا :دی
____________________________________________________________________________________________
سوال اول:
قسمت الف: میخواهیم ثابت کنیم:
D(A,C)
فرض کنید که A,C در مکان X ام با هم تفاوت داشته باشند. اکنون B یا با A و یا با C و یا به هردو در مکان X ام متفاوت خواهد بود.
قسمت ب: میخواهیم ثابت کنیم یکی از رشته ها مانند P وجود دارد که:
Min : رشته ای که D آن کمینه شود
D(Min)
طرف چپ که واضح است طبق تعریف Min.
برای طرف راست, رشته ای رو از بین pi ها در نظر بگیرید که فاصلش از Min کمترین باشه و اسمش رو X بذارین. حالا ثابت کنید که به ازای هر رشته ی دیگه از بین pi ها نامساوی زیر برقراره:
D(X,pi)
__________________________________________________________________________________________________
سوال دوم:
سوال دوم را به سوال زیر تبدیل کنید:
یک دنباله از اعداد دارید که a1,a2,...,an هستند. شما k مرحله الگوریتم زیر را بر روی آن ها انجام میدهید:
فرض کنید که روی خانه ی i ام ایستاده اید. در ابتدا نیز بر روی خانه ی 1 ام ایستاده اید. اگر ai > ai+1 جای ai,ai+1 را عوض کنید. حال بر روی خانه ی i+1 بایستید. تا جایی این کار را انجام دهید که i
اکنون ما تعداد جایگشت هایی را میخواهیم که با انجام k بار الگوریتم بالا مرتب شوند.
پس برای 1, k + 1 مکان خوب وجود دارد. برای 2, k + 1 مکان خوب وجود دارد .... برای n - k هم k + 1 مکان خوب وجود دارد. برای n - k + 1 تا n نیز به تعداد خانه های خالی مکان خوب داریم.
پس در کل جواب برابر است با:
______________________________________________________________________________________________
قطر فرعی: خانه ی های روی قطر بالا سمت راست به پایین سمت چپ یک مربع,قطر فرعی را تشکیل میدهند.
تعریف مربع خوب: به مربعی خوب میگوییم که شکلات های قطر فرعی آن,خورده نشده باشند و اگر شکلات خانه ی X این مربع خورده شده باشد,شکلات خانه ی متقارن X نسبت به قطر فرعی نیز خورده شده باشد.
میخواهیم ثابت کنیم که مربع های خوب را نفر دوم میبرد.
روی n استقرا بزنید.
حال اگر نفر اول در خال خوردن شکلات های یک مربع مثل مربع X بود حالات زیر را در نظر بگیرید.
1. مربع X شامل یکی از خانه های قطر فرعی یا یکی از خانه های مجاور قطر فرعی میباشد.
2. مربع X شامل هیچ یک از خانه های قطر فرعی یا مجاور قطر فرعی نیست.
حالت 1: اکنون یا میتوان به یک مربع خوب دیگر رسید و یا نفر اول کل شکلات های جدول را خورده است. (چرا؟)
حالت 2: نفر دوم نیز مربع X_ را انتخاب میکند که این مربع متقارن است با مربع X نسبت به قطر فرعی. ( چرا حتما شکلات دارد؟ )
_____________________________________________________________________________________________________
سوال چهارم:
قسمت الف: یک جدول که دارای 99! سطر و 1392 ستون است را در نظر بگیرید. اکنون خانه ی i,j این جدول را یک کنید اگر که در جایگشت با مدل i,عدد روی کارت با شماره ی j با خودش برابر باشد. حال دو گونه شماری بزنید...
قسمت ب: دسته های اول را یک سری دسته با 99 تا کارت , یک دسته با 20 کارت (فکر کنم) , و بقیه را با 1 کارت تقسیم کنید. در دسته بندی جدید در دسته ی اول خود از هر کدام از دسته های قدیمی یک کارت بگذارید. و بقیه را دلخواه دسته بندی کنید. اکنون ثابت کنید 15 رنگ بیشتر نمیشود.
_____________________________________________________________________________________________________
سوال پنجم:
قسمت الف: استقرا بزنید. برای nk تا راس گرافتان را بسازید. اکنون یک خوشه با k راس اضافه کنید. حال یکی از راس های خوشه ی جدید را نادیده بگیرید و بقیه راس های این خوشه را به همه ی راس های گراف nk راسی فرض وصل کنید. ثابت کنید این گراف دسته بندی یکتا دارد و تعداد یال های آن نیز برابر عدد مورد نظر در سوال است.
قسمت ب: فرض کنید یک دسته یندی یکتا وجود داشته باشد. اکنون آن دسته بندی را در نظر بگیرید. حال ثابت کنید دو دسته مثل X,Y وجود دارند که بین این دو دسته بیش از k^2 - k یال است. اکنون ثابت کنید راس هایی مثل x در X و y در Y وجود دارند که x به همه ی راس های Y وصل است و y به همه ی راس های X. حال جای راس های x,y را عوض کنید.
______________________________________________________________________________________________
شاد و خوش و خرم باشید. تا بعد ...
- ۹۲/۰۲/۱۰