موضوع مقاله: مربع لاتین | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مربع لاتین | مقدمه: مربع لاتین یک آرایهٔ مربعی (ماتریس مربعی) است که در هر سطر و هر ستون آن اعضای مجموعه A به‌طور کامل و بدون تکرار قرار داشته باشند. | ## بخش 1: مربع لاتین | مثال: در احتمالات ماتریس «متغیر تصادفی دوگانه» (که حاصل جمع هر سطر و ستون آن یک است) یک مربع لاتین است. حال در مورد مستطیل‌ها و مربع‌هایی بحث می‌کنیم که درایه‌های آن اعداد صحیح و مثبت هستند. یک مستطیل لاتین A با ابعاد p×q عبارت است از : یک ماتریس p × q که هر یک از درایه‌های آن عضو مجموعه {۳٬۲،1...n} بوده و هیچ عضو تکراری در سطر یا ستون آن به وجود نیاید. یا به عبارت دیگر آیا می‌توان دو سطر دیگر به این مستطیل لاتین افزود که تبدیل به مربع لاتین ۴×۴ شود؟ مانند: می‌توان نشان داد که هر مستطیل لاتین p×q با درایه‌هایی از مجموعه {۳٬۲،1...n} را می‌توان به مربع لاتین n×n گسترش داد. چون این سه عدد «۲» باید در دو سطر قرار گیرند پس دو تا از آن‌ها در یک سطر واقع شده‌اند؛ بنابراین مربع بدست آمده لاتین نخواهد بود. قبل از این که به بیان قضایای مورد نظر در این بحث بپردازیم، ابتدا به صورت دو قضیه و یک لم کمکی اشاره می‌کنیم: قضایای کمکی ۱)قضیه هال (صورت ماتریسی) : ماتریس M یک ماتریس m× n با درایه‌های صفر و یک است. در این صورت در هر سطر آن یک عدد ۱ وجود دارد و در هیچ ستونی بیش از یک عدد ۱ وجود ندارد اگر و تنها اگر برای هر مجموعه از سطرها (مثلاً r تایی) تعداد ستون‌هایی که ۱های این سطرها در آن‌ها قرار دارند، حد اقل برابر r باشد. | ## بخش 2: مربع لاتین | ∪An حال Sدارای یک مجموعه نماینده‌های متمایز شامل مجموعه P است اگر و تنها اگر: الف) S یک مجموعه نماینده‌های متمایز داشته باشد. قضایای اصلی قضیه۱:هر مستطیل لاتین n×p را می‌توان به مربع لاتین n×n گسترش داد اثبات: فرض کنیم L مستطیل لاتین n×p باشد. طبق قضیه هال اجتماع هر r تا از این مجموعه‌ها حداقل شامل r عضو متمایز است که n>r>1. = |An| = n - p| چون هر کدام از این مجموعه‌ها شامل عضوهایی از مجموعه {۳٬۲،1...n} است که در ستون p عضوی مربوط به آن نیامده‌اند. هر خانواده از مجموعه‌ها مانند S با ویژگی‌های مذکور باید یک مجموعه نماینده‌های متمایز داشته باشد. r مجموعه از خانواده S را در نظر گرفته و ثابت می‌کنیم شامل حد اقل r عضو متمایز است. ابتدا همهٔ اعضای r مجموعهٔ مفروز را (با در نظر گرفتن اعضای تکراری) در یک لیست ردیف می‌کنیم. از طرفی همان‌طور که قبلاً گفته شد هر j حد اکثر در n-p مجموعه ظاهر می‌شود؛ بنابراین اگر اجتماع r مجموعه مفروض شامل کمتر از r عضو متمایز باشد (یعنی حد اکثر r-1 عضو متمایز داشته باشد) لیست باید شامل حد اکثر (n-p r-1) عضو باشد که می‌دانیم درست نیست. | ## بخش 3: مربع لاتین | از طرفی همان‌طور که قبلاً گفته شد هر مجموعه نماینده‌های متمایز می‌تواند به عنوان یک سطر اضافی برای L در نظر گرفته شود و آن را به مستطیل لاتین p+1)×n) تبدیل کند. اکنون مستطیل لاتین p×q را مورد بررسی قرار داده و متوجه خواهیم شد که گسترش آن‌ها همیشه ممکن نیست. روشی ارائه می‌دهیم که به وسیلهٔ آن بتوان L را به مستطیل (p×(q+1 گسترش داد و این روش برای مستطیل بدست آمده در مرحله قبل قابل تکرار باشد و بتواند تا ساختن مستطیل لاتین p×n ادامه پیدا کند. از طرفی بنا بر قضیهٔ قبل مطمئن هستیم که این مستطیل p×n قابل گسترش به مربع لاتین n×n است. (که این مجموعه را به عنوان ستون اضافی برای گسترش L به مستطیل لاتین (p×(q+1 در نظر می‌گیریم) برای اثبات وجود مجموعه نماینده‌های متمایز خانواده S باید به دو نکته توجه کنیم. بنابراین مانند اثبات قضیه قبل اجتماع هر r تا از این مجموعه‌ها شامل حد اقل r عضو متمایز است. می‌توانیم این مجموعه نماینده‌های متمایز را به عنوان ستون اضافی برای گسترش L به مستطیل لاتین (p×(q+1 استفاده کنیم. | ## جمع‌بندی | اگر(L’(i) تعداد مرتبه‌های حضور عدد i در مستطیل لاتین جدید یعنی ’L باشد، در نتیجه خواهیم داشت: اگر i عضو p نباشد: L’(i) ≥ L(i)> p + q – n اگر i عضو p باشد: L’(i) = L(i) + 1 = p + q – n +1 که در هر صورت نتیجه می‌دهد: L’(i) ≥ p + q – n + 1 یعنی مستطیل لاتین ’L نیز شرط لازم وکافی برای گسترش دادن را دارد و از این رویه می‌تواند ادامه پیدا کند تا مستطیل لاتین p×n ساخته شود و از طرفی بنا بر قضیه قبل مطمئن هستیم که این مستطیل می‌تواند به مربع لاتین n×n گسترش یابد.