به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
796 بازدید
در دبیرستان توسط Taha1381 (1,789 امتیاز)

به چند طریق می توان راس های یک جدول $n*n$را با چهار رنگ مختلف رنگ امیزی کرد به طوری که در هر مربع واحد از هر رنگ دقیقا یک راس داشته باشیم؟

جواب:$24*(2^n-1)$

مرجع: انالیز ترکیبی(عباس ثروتی)-فصل ۱-سوال۸۶

1 پاسخ

+1 امتیاز
توسط A Math L (2,400 امتیاز)
انتخاب شده توسط Taha1381
 
بهترین پاسخ

فرض مکنیم نام چهار رنگ $a,b,c,d$ باشند و $(x,y)$ نشان دهنده راسی با مختصات سطر $x$ و ستون $y$ پایین سمت چپ باشد .

برای راس $(1,1)$ چهار حالت ، برای راس $(1,2)$ سه حالت و برای راس $(2,1)$ دو حالت و رنگ راس $(2,2)$ به صورت یکتا مشخص میشود . که برابر 24 حالت می باشد . حال برای هر راس به صورت $(1,n)$ دو حالت وجود دارد و هر راس به صورت $(2,n)$ به صورت یکتا مشخص میشود .

اگر سطر اول رنگ ها به صورت یکی در میان بودند (مثلا $a,b,a,b ... a,b$) نتیجه میشود سطر دوم نیز رنگ ها به صورت یکی در میان اند $(c,d,c,d...c,d)$ ولی برای سطر های بعدی هر کدام 2 حالت وجود دارد (سطر های فرد یا $a,b...a,b$ یا $b,a...b,a$ و سطر های زوج یا $c,d...c,d$ یا $d,c...d,c$) که در این حالت تعداد برابر $24*2^{n-1}$

و اگر سطر دوم به صورت یکی در میان نبود مثلا مکانی وجود داشت که به صورت $a,b,c$ بود در بالای $b$ رنگ $d$ و در سمت راست $d$ رنگ $a$ و در سمت چپش رنگ $c$ قرار میگیرد و به همین صورت این سطر و سطر های بعدی به صورت یکتا مشخص میشوند . تعداد این حالات برابر است با $24*(2^{n-1}-1)$

$1$ حالت کم شده از $2^{n-1}$ همان حالت یکی در میان بودن سطر دوم میباشد .

$$24*2^{n-1}+24*(2^{n-1}-1)=24*(2^n-1)$$
این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...