به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
844 بازدید
در دبیرستان توسط 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)$$
برای ترجمه ی یک جمله از انگلیسی به فرانسوی دو چیز ضروری است. اول، باید جمله ی انگلیسی را تماما بفهمیم. دوم، باید با اصطلاحات ویژه ای که در زبان فرانسوی هستند آشنا باشیم. این وضعیت خیلی شبیه هنگامی است که سعی داریم شرط را که با کلمات بیان شده است با نمادهای ریاضی بیان کنیم. اول، باید آن را تمام درک کنیم. دوم، باید با اصطلاحات ریاضی ریاضی آشنا باشیم.
...