مرحله ۲ روز اول
چهارشنبه, ۱۳ ارديبهشت ۱۳۸۵، ۰۱:۵۷ ب.ظ
۱) الف) با خودتون ب) تابلویه که جواب بصورت مجموعی از اعدادمون هستن که هر کی ضریب -۱ یا ۱ داره. البته حتما یه نفر با ضریب مثبت وجود داره(با استقرا تابلوئه). پس جواب بصورت (جمع چند تا) منهای (جمع بقیه) هست. حالا ما جواب مینیمم رو در نظر میگیریم. میایم اول قسمت مثبت رو جمع میزنیم و بعد قسمت منفی رو جمع میزنیم و آخر این دو عدد رو از هم کم میکنیم.
۲) نقش رو تعریف میکنیم خطی که مینیمم مسیر رو از گوشه‌ی بالا سمت چپ به پایین سمت راست رو طی میکنه و البته از روی محیط قالیها میگذره. حالا فرض استقرا اینه که ما هر نقشی که کمتر از k تا قالی توشه میتونیم درست کنیم. حالا واسه k قالی میایم اون قالی رو در نظر میگیریم که بالا و سمت راستش خالیه ( مثلا میتونید از روی نقش اولین حرکت سمت راستمون رو دنبال کنید و به محض اینکه حرکت سمت پایین کردید این جا همون قالین). خوب حالا این قالیه رو حذف کنید و طبق استقرا بقیه رو بسازید و بعد هم اینو اضافه کنید.
۳) اول همه‌ی لامپ‌ها رو رندوم میبندیم به کلیدها. حالا دو حالت پیش میاد:
الف) یدونه لامپ روشن بشه: که بدیهیه: با ۱۰۰ حرکت خرابها رو درمیاریم و هر کلیدی رو با لامپ سالمه چک میکنیم اگر روشن شد که میفهمیم کلید درسته و لامپه نظیرش خراب بوده. اگر هم روشن نشه فقط میفهمیم که کلید خرابه. از این دومی ۵۰ بار اتفاق میفته که لامپ‌های نظیرشونرو میتونیم با اون کلید درسته چک کنیم و حله.
ب)هیچکی روشن نشه: که خوب پس یار هر کس دقیقا برعکسه خودش بوده. پس ۵۰ تای اول رو در خودشون یکی شیفت میدیم جلو(یعنی ۱ به ۲, ۲ به ۳, ... , تا ۵۰ به ۱). اگه کسی روشن نشد که تابلویه وگرنه یه دونه روشن میشه. حالا بوسیله‌ی این و شبیه به بالا حل میکنیم البته توجه داشته باشید که با تعیین هرکس وضعیت اون یار قبلیش هم معلوم میشه.
اینکه چرا میشه ۲۵۰ تا حداکثر, خودتون چک کنید.
۴) سوال هم ارزه با اینکه بگیم: دو رشته اگر حداکثر در ۲ بیت تفاوت داشته باشند باید کد متفاوتی براشون خرج بشه. که این اگر کدمون حداکثر k باشه غیر ممکن و اگر k+1 باشه حتما ممکنه. که مسئله مورد اول رو می‌خواد. کافیه بیاین یدونه رشته رو با همه‌ی کسانی که باهاش تو یه بیت تفاوت دارند رو در نظر بگیرید. این دو به توان k بعلاوه‌ی ۱ رشته میشه. که چون با k بیت کد حداکثر دو به توان k حالت میشه پوشوند لذا دو تا از این رشته‌ها کد یکسان دارند و نمیتوان بینشان تفاوت گذاشت.(در حقیقت نمی‌فهمیم که کدامیک از اینها منظور فرستنده بودند.)
اینها هم تقریبا حل-راهنمایی بودند و مقداریش رو باید خودتون ثابت کنید.
۲) نقش رو تعریف میکنیم خطی که مینیمم مسیر رو از گوشه‌ی بالا سمت چپ به پایین سمت راست رو طی میکنه و البته از روی محیط قالیها میگذره. حالا فرض استقرا اینه که ما هر نقشی که کمتر از k تا قالی توشه میتونیم درست کنیم. حالا واسه k قالی میایم اون قالی رو در نظر میگیریم که بالا و سمت راستش خالیه ( مثلا میتونید از روی نقش اولین حرکت سمت راستمون رو دنبال کنید و به محض اینکه حرکت سمت پایین کردید این جا همون قالین). خوب حالا این قالیه رو حذف کنید و طبق استقرا بقیه رو بسازید و بعد هم اینو اضافه کنید.
۳) اول همه‌ی لامپ‌ها رو رندوم میبندیم به کلیدها. حالا دو حالت پیش میاد:
الف) یدونه لامپ روشن بشه: که بدیهیه: با ۱۰۰ حرکت خرابها رو درمیاریم و هر کلیدی رو با لامپ سالمه چک میکنیم اگر روشن شد که میفهمیم کلید درسته و لامپه نظیرش خراب بوده. اگر هم روشن نشه فقط میفهمیم که کلید خرابه. از این دومی ۵۰ بار اتفاق میفته که لامپ‌های نظیرشونرو میتونیم با اون کلید درسته چک کنیم و حله.
ب)هیچکی روشن نشه: که خوب پس یار هر کس دقیقا برعکسه خودش بوده. پس ۵۰ تای اول رو در خودشون یکی شیفت میدیم جلو(یعنی ۱ به ۲, ۲ به ۳, ... , تا ۵۰ به ۱). اگه کسی روشن نشد که تابلویه وگرنه یه دونه روشن میشه. حالا بوسیله‌ی این و شبیه به بالا حل میکنیم البته توجه داشته باشید که با تعیین هرکس وضعیت اون یار قبلیش هم معلوم میشه.
اینکه چرا میشه ۲۵۰ تا حداکثر, خودتون چک کنید.
۴) سوال هم ارزه با اینکه بگیم: دو رشته اگر حداکثر در ۲ بیت تفاوت داشته باشند باید کد متفاوتی براشون خرج بشه. که این اگر کدمون حداکثر k باشه غیر ممکن و اگر k+1 باشه حتما ممکنه. که مسئله مورد اول رو می‌خواد. کافیه بیاین یدونه رشته رو با همه‌ی کسانی که باهاش تو یه بیت تفاوت دارند رو در نظر بگیرید. این دو به توان k بعلاوه‌ی ۱ رشته میشه. که چون با k بیت کد حداکثر دو به توان k حالت میشه پوشوند لذا دو تا از این رشته‌ها کد یکسان دارند و نمیتوان بینشان تفاوت گذاشت.(در حقیقت نمی‌فهمیم که کدامیک از اینها منظور فرستنده بودند.)
اینها هم تقریبا حل-راهنمایی بودند و مقداریش رو باید خودتون ثابت کنید.
- ۸۵/۰۲/۱۳