رنگ امیزی پراکنده

Question

یک رنگ امیزی از خانه های یک جدول با دو رنگ سیاه و سفید را پراکنده می گوییم اگر هیچ دو خانه ی سیاهی ضلع مشترک نداشته باشند.ثابت کنید تعداد رنگ امیزی های پراکنده ی یک جدول $10*10$ از $10^{15}$ بیش تر و از $10^{25}$ کم تر است.

Answer 1

یکی از حالات مورد نظر رنگ کردن مانند صفحه شطرنج میباشد . اگر در این حالت یک یا چند خانه سیاه را سفید کنیم حالت مطلوب دیگری بدست می آید چون 50 خانه سیاه داریم و هر خانه میتواند سیاه بماند یا سفید شود پس $2^{50}=1024^5$ حالت بدست می آید که از $10^{15}=1000^5$ بیشتر است .

چون در مربع $10*10$ بیست و پنج مربع $2*2$ وجود دارد و در هر مربع $2*2$ هفت حالت مطلوب وجود دارد پس تعداد حالات از $7^{25}$ کمتر میباشد .