مرحله ۲ روز دوم
پنجشنبه, ۱۴ ارديبهشت ۱۳۸۵، ۱۰:۱۴ ق.ظ
۵) این بصورت استقرایی ثابت میشه. یعنی مسلما فرد ۱ باید دره یک رو باز کنه. بعد نغر ۲ باید کار انجام بده. بعد ۳ باید انحام بده, بعد ۴ نباید انحام بده و همینطور فرض میکنیم که تا نفر k همه بصورت یکتا تعیین میشن. حالا بسته به اینکه در صندوق k باز باشه یا بسته, نفر k هم یکتا تعیین میشه(توجه کنید که غیر از k کس دیگری نمانده که بتونه صندوق k رو تغییر بده)
۶) این روشی که گغته برای یه خونه عددش میشه فلان, مثل اینه که عدد هر خونه بشه جمع همه‌ی اعداد سطرش بعلاوه‌ی جمع همه‌ی اعداد ستونش.(توجه کنید که جمع در Z2 میشه همون xor هست). که البته چون خودش دوبار حساب میشه, خودش تاثیر نداره. حالا فرض کنید به جدول داریم که جمع اعداد ستون i میشه a و جمع اعداد ستون j میشه b. (توجه کنید که a و b یا ۰ یا ۱ هستن) عدد سطر k ام ستون i می شه جمع اعداد سطر k و a. عدد سطر k ام ستون j می شه جمع اعداد سطر k و b. حالا اگر a=b بود این دو عدد مساوی وگرنه مخالف همدیگه می شند. پس اگه یه جدول اصلاحپذیر باشه اعداد ستون i ام یا همه مساوی یا همه مخالف اعداد ستون j ام هستند. (همچنین برای سطرها) حالا میخوایم ثابت کنیم جمع اعداد هر ستون مساویه. فرض کنید ستون i بشه a. اونهایی که مساویه ستونه‌هن که هیچ. اونهایی که مخالفه‌شن جمعشون میشه (n-a) که چون n زوجه (n-a) هم میشه همون a. پس جمع اعداد همه‌ی ستون‌ها یکسانه(و سطرها هم یکسانه). خوب حالا که جمعشون یکسانه برگردیم به ۴-۵ خط بالاتر. نتیجه میگیریم که همه‌ی ستون‌ها با هم مساویند(و همه‌ی سطرها هم). چون همه‌ی ستون‌ها مثل همند اگر خانه‌ی (i,j) یک باشه اونوقت سطر i و در نتیجه همه‌ی سطور ۱ میشوند. پس یا همه‌ی اعداد ۱ هستند و یا همه ۰. اگه همه ۰ باشند که خوب مستقیما مرحله‌ی بعدی به خودمون میرسیم. اما اگه همه ۱ باشند مرحله‌ی بعد به همه ۰ میرسیم و هیچوقت دیگه به همه ۱ نمیرسیم. پس جواب سؤال میشه تنها یک جدول و اون هم همه ۰.
۷) این سؤالیه که مسلما چندین راه داره ولی یه راهه خیلی آسون و کوتاهش اینه: بیاین ۲نفر ۲نفر دسته بندیشون کنید(نفر ۱۳۸۵ تنها میمونه). حالا نفر اول هر دسته میاد رنگ کلاه نفر دوم رو مینویسه و نفر دوم هم معکوس رنگ نفر اول رو مینویسه. اینجوری اگه رنگشون برابر بوده, نفر اول وگرنه اگه مخالف باشه نفر دوم درست گفته. اینجوری نزدیک به ۵۰٪ افراد درست خواهند گفت.
۸) از طرز سوال بدیهیه که با خیابان‌های موازی محورها نمیشه و با مورب‌ها میشه.
اینکه چرا موازی‌ها نمیشن: فرض کنید اگه مثلا خونه‌ی شهردار سمت راست یه خیابان عمودی باشه و اول کار به سمت پایین بره (بقیه هم به همین صورته), اونوقت همیشه یا سمت راست خیابان‌های عمودیه یا سمت بالای خیابان‌های افقیه. و برای همین همیشه یا داره به سمت پایین میاد یا به سمت چپ و هرگز به خودش نمیرسه. البته این رو میشه با استقرا روی تعداد چهارراه‌های رفته اثبات کرد.
اینکه جرا مورب‌ها میشه: میشه با ۳ جاده حرکت پیچش به راست رو شبیه‌سازی کرد. یعنی در سمت راست یک جاده حرکت کنی و به سمت راست بپیچی ولی همچنان در سمت راست جاده بمانی. حالا که این حرکت رو داریم خیلی راحت میتونیم دور بزنیم و به خودمون برسیم.
۶) این روشی که گغته برای یه خونه عددش میشه فلان, مثل اینه که عدد هر خونه بشه جمع همه‌ی اعداد سطرش بعلاوه‌ی جمع همه‌ی اعداد ستونش.(توجه کنید که جمع در Z2 میشه همون xor هست). که البته چون خودش دوبار حساب میشه, خودش تاثیر نداره. حالا فرض کنید به جدول داریم که جمع اعداد ستون i میشه a و جمع اعداد ستون j میشه b. (توجه کنید که a و b یا ۰ یا ۱ هستن) عدد سطر k ام ستون i می شه جمع اعداد سطر k و a. عدد سطر k ام ستون j می شه جمع اعداد سطر k و b. حالا اگر a=b بود این دو عدد مساوی وگرنه مخالف همدیگه می شند. پس اگه یه جدول اصلاحپذیر باشه اعداد ستون i ام یا همه مساوی یا همه مخالف اعداد ستون j ام هستند. (همچنین برای سطرها) حالا میخوایم ثابت کنیم جمع اعداد هر ستون مساویه. فرض کنید ستون i بشه a. اونهایی که مساویه ستونه‌هن که هیچ. اونهایی که مخالفه‌شن جمعشون میشه (n-a) که چون n زوجه (n-a) هم میشه همون a. پس جمع اعداد همه‌ی ستون‌ها یکسانه(و سطرها هم یکسانه). خوب حالا که جمعشون یکسانه برگردیم به ۴-۵ خط بالاتر. نتیجه میگیریم که همه‌ی ستون‌ها با هم مساویند(و همه‌ی سطرها هم). چون همه‌ی ستون‌ها مثل همند اگر خانه‌ی (i,j) یک باشه اونوقت سطر i و در نتیجه همه‌ی سطور ۱ میشوند. پس یا همه‌ی اعداد ۱ هستند و یا همه ۰. اگه همه ۰ باشند که خوب مستقیما مرحله‌ی بعدی به خودمون میرسیم. اما اگه همه ۱ باشند مرحله‌ی بعد به همه ۰ میرسیم و هیچوقت دیگه به همه ۱ نمیرسیم. پس جواب سؤال میشه تنها یک جدول و اون هم همه ۰.
۷) این سؤالیه که مسلما چندین راه داره ولی یه راهه خیلی آسون و کوتاهش اینه: بیاین ۲نفر ۲نفر دسته بندیشون کنید(نفر ۱۳۸۵ تنها میمونه). حالا نفر اول هر دسته میاد رنگ کلاه نفر دوم رو مینویسه و نفر دوم هم معکوس رنگ نفر اول رو مینویسه. اینجوری اگه رنگشون برابر بوده, نفر اول وگرنه اگه مخالف باشه نفر دوم درست گفته. اینجوری نزدیک به ۵۰٪ افراد درست خواهند گفت.
۸) از طرز سوال بدیهیه که با خیابان‌های موازی محورها نمیشه و با مورب‌ها میشه.
اینکه چرا موازی‌ها نمیشن: فرض کنید اگه مثلا خونه‌ی شهردار سمت راست یه خیابان عمودی باشه و اول کار به سمت پایین بره (بقیه هم به همین صورته), اونوقت همیشه یا سمت راست خیابان‌های عمودیه یا سمت بالای خیابان‌های افقیه. و برای همین همیشه یا داره به سمت پایین میاد یا به سمت چپ و هرگز به خودش نمیرسه. البته این رو میشه با استقرا روی تعداد چهارراه‌های رفته اثبات کرد.
اینکه جرا مورب‌ها میشه: میشه با ۳ جاده حرکت پیچش به راست رو شبیه‌سازی کرد. یعنی در سمت راست یک جاده حرکت کنی و به سمت راست بپیچی ولی همچنان در سمت راست جاده بمانی. حالا که این حرکت رو داریم خیلی راحت میتونیم دور بزنیم و به خودمون برسیم.
- ۸۵/۰۲/۱۴