میخواهیم ۶ مهره از یک صفحه شطرنجی مهره دار برداریم بطوری که در هر سطر و ستون تعدادی زوج مهره باقی بماند.

Question

یک صفحه ی شطرنجی ۴*۴ داریم که در هر خانه ی ان مهره ای قرار داده شده است. میخواهیم ۶ مهره از روی صفحه برداریم به گونه ای که در هر سطر و هر ستون ، تعداد زوجی مهره باقی بماند. چگونه این کار را انجام دهیم؟

در چند بار ازمایشی که انجام دادم بنظرم این کار ناممکن است، ایا این حدس درست است؟ و اثبات می شود؟

Answer 1

بیایید ۴ سطر را ۴ لانه و ۶ مهره‌ای که می‌خواهید بردارید را ۶ کبوتر در نظر بگیریم. طبق اصل لانهٔ کبوتری یک خانه است که بیش از یک کبوتر می‌خواهد. بدون کاستن از کلیت فرض کنید سطر اول. این سطر ۲ یا ۳ یا ۴ مهره از دست خواهد داد. چون از دست دادن ۳ مهره باعث می‌شود تعداد باقیماندهٔ مهره‌ها در این سطر فرد شود پس نامطلوب است. می‌ماند حالت ۴ مهره یا ۲ مهره می‌ماند. ابتدا برویم سراغ ۴ مهره. پس سطر اول کلا خالی می‌شود و ۲ مهره باید از سایر سطرها برداریم. یک حالت این است که هر دو مهرهٔ مانده را از یک سطر برداریم، ستون‌هایی که این دو مهره در آنها نستند ۳ مهره‌ای خواهند شد پس این حالت نامطلوب است. در حالتی که دو مهره از دو سطر متفاوت برداشته‌شوند، آن دو سطر ۳ مهره‌ای خواهند شد. پس این حالت نیز نامطلوب است و در نتیجه ۴ مهره از سطر اول رد می‌شود. می‌ماند حالت ۲ مهره از سطر نخست. اکنون ۴ مهره و ۳ سطر را با اصل لانهٔ کبوتری در نظر بگیرید. یک سطر باید بیشتر از یک مهره از دست بدهد. دوباره ۳ مهره نامطلوب است و اگر ۴ مهره را در نظر بگیرید مشابه حالت ۴ مهره از سطر نخست رخ خواهد داد. پس تنها حالت ۲ مهره می‌ماند. تا اینجا سطر یک و سطر دو هر دو دو مهره از دست داده‌اند. اگر دو مهرهٔ ماندهٔ دیگر یکی در سطر ۳ و یکی در سطر ۴ بروند، این سطرها ۳ مهره‌ای خواهند شد و نامطلوب. پس به این حالت می‌رسیم که ۳ سطر باید ۲ مهره از دست بدهند. اگر ستونی پیدا شود که این سه سطر با هم از آن ستون مهره از دست داده باشند آنگاه تک‌مهره‌ای و نامطلوب می‌شود پس نباید ۳ مهره در زیر هم کم شده باشند.

هر حالت مطلوبی از جایگشت‌دادن سطرها و ستون‌های این حالت بدست می‌آید.