خب جوابش

مربع ها را به صورت زیر رنگ آمیزی می کنیم

هر مربع که هم شماره ی سطرش و هم شماره ستونش فرد می باشد را سیاه می کنیم .

حال خانه ی خالی اولیه سیاه شده است(بدیهی) حال به راحتی می توان نشان داد که خانه ی خالی فقط روی خانه های سیاه حرکت می کند .

زیرا خانه ی خالی که با دومینو جابجا می شود تغییرات ستونی و سطریش زوج است و زوجیت خانه ی اولیه را حفظ می کند .

به صورت زیر تبدیل به گرافش می کنیم :

راس ها را خانه های سیاه می گیریم و بین دو خانه ی( راس) A,B یال می کشیم اگر و تنها اگر دومینویی رو A وجود دارد که خانه ی دیگرش مجاور B باشد . (یال جهت دار نیست)

حال n+1 به توان دو راس و به همین تعداد منهای یک یال (از هر راس سیاه یک یال را خارج کردیم به غیر از خانه ی خالی ) حال کافیست ثابت کنیم همبند می باشد یعنی ثابت شود که گراف حاصل یک درخت است و دور ندارد و خانه ی خالی که در خانه ی سیاه است به هر خانه ی سیاه دیگر (مانند چهار گوشه) می تواند برود .

اثبات این موضوع هم سخت نیست

دور در جدول یعنی یک ناحیه که محیطش به بیرون دومینویی خارج نکرده است . که اسمش را ناحیه ی ممنوعه می گذاریم .

و نام ناحیه ای که می توانیم با دومینوهایمان به آن برویم مجاز می گذاریم .

فرض کنید خانه ی خالی در راست بالا باشد حال به ناحیه ای که ما نمی توانیم با دومینو هایمان وارد شویم یعنی بین آن ناحیه و ناحیه مجاز هیچ راهی نیست بنابراین ما توانستیم یک ناحیه را با دومینو بپوشانیم یعنی مساحت ناحیه زوج است و ناحیه ی مجاز مساحتش فرد است ( به علاوه خانه ی خالی)

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

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

ناحیه ی A ممنوعه است . که مرز هایش خانه ی های سیاه هستند . حال ارتفاع هر ستون در ناحیه ی زرد فرد می باشد (از یک سیاه به یک سیاه ) سر جمع هم فرد تا ستون داریم پس مساحت ناحیه ی A فرد است پس تناقض چون فرد تا خانه را با دومینو نمی توان پوشاند پس به بیرون دومینو دارد .

اگر به نظرتون جاییش اشکال دارد بفرمایید. و گرنه که خودتون می دونید دیگه ... ;))

در ضمن اثبات برای هم الف و ب می باشد .

با تشکر از آقای کلاه قرمزی !!!