مربع لاتین

قضایای کمکی

۱)قضیه هال (صورت ماتریسی) : ماتریس M یک ماتریس m× n با درایه‌های صفر و یک است. در این صورت در هر سطر آن یک عدد ۱ وجود دارد و در هیچ ستونی بیش از یک عدد ۱ وجود ندارد اگر و تنها اگر برای هر مجموعه از سطرها (مثلاً r تایی) تعداد ستون‌هایی که ۱های این سطرها در آن‌ها قرار دارند، حد اقل برابر r باشد.
۲)یک خانواده از مجموعه‌ها به صورت{ S={A1، A2، A3 ،...، An را در نظر می‌گیریم. مجموعه P را نیز یصورت زیر فرض می‌کنیم:
P زیر مجموعهٔ A1∪A2∪... ∪An
حال Sدارای یک مجموعه نماینده‌های متمایز شامل مجموعه P است اگر و تنها اگر:
الف) S یک مجموعه نماینده‌های متمایز داشته باشد.
ب) برای هر  داشته باشیم:

لم کمکی

لم: فرض کنید L، مستطیل لاتین p × q شامل درایه‌های {۲٬۱،... ،n} باشد.
اگر  دو عدد صحیح باشند، آنگاه تعداد اعضای مجموعه {۲٬۱،... ،n} که دقیقاً m بار در L آمده و در همهٔ r سطر اول ظاهر شده‌اند بیشتر از  نمی‌باشند.

قضایای اصلی

قضیه۱:هر مستطیل لاتین n×p را می‌توان به مربع لاتین n×n گسترش داد
اثبات: فرض کنیم L مستطیل لاتین n×p باشد. برای هر n>i>1 تعریف می‌کنیم:
یافتن یک سطر اضافی از اعضای مجموعه{۳٬۲،1...n} برای تبدیل L به مستطیل لاتینیp+1)×n) در واقع معادل یافتن یک مجموعهٔ نماینده‌های متمایز از خانواده {S={A1،A2،A3،... ،An است. طبق قضیه هال اجتماع هر r تا از این مجموعه‌ها حداقل شامل r عضو متمایز است که n>r>1. قبل از ارائه استدلال به دو نکته اشاره می‌کنیم.
۱)
A1| = |A2| = |A3| = ... = |An| = n - p|
چون هر کدام از این مجموعه‌ها شامل عضوهایی از مجموعه {۳٬۲،1...n} است که در ستون p عضوی مربوط به آن نیامده‌اند.
۲) به ازای هر n>j>1عدد j در دقیقاً n - p مجموعه از خانواده S وجود دارد. زیرا j در دقیقاً p مکان L ظاهر می‌شود(p ستون مختلف). پس در n - p ستون وجود ندارد و بنا بر تعریف Aiها درn-p مجموعه مختلف ظاهر می‌شود.
هر خانواده از مجموعه‌ها مانند S با ویژگی‌های مذکور باید یک مجموعه نماینده‌های متمایز داشته باشد. r مجموعه از خانواده S را در نظر گرفته و ثابت می‌کنیم شامل حد اقل r عضو متمایز است. ابتدا همهٔ اعضای r مجموعهٔ مفروز را (با در نظر گرفتن اعضای تکراری) در یک لیست ردیف می‌کنیم. (r (n – p عضو بدست می‌آید. از طرفی همان‌طور که قبلاً گفته شد هر j حد اکثر در n-p مجموعه ظاهر می‌شود؛ بنابراین اگر اجتماع r مجموعه مفروض شامل کمتر از r عضو متمایز باشد
(یعنی حد اکثر r-1 عضو متمایز داشته باشد) لیست باید شامل حد اکثر (n-p)(r-1) عضو باشد که می‌دانیم درست نیست. چون شامل (r(n-p عضو است. پس هر خانواده S شامل r مجموعه از Aiها، حد اقل r عضو متمایز دارد و طبق قضیهٔ هال خانواده { S={A1، A2، A3 ،...، An شامل یک مجموعه نماینده‌های متمایز از Aiها است.
از طرفی همان‌طور که قبلاً گفته شد هر مجموعه نماینده‌های متمایز می‌تواند به عنوان یک سطر اضافی برای L در نظر گرفته شود و آن را به مستطیل لاتین p+1)×n) تبدیل کند. به همین ترتیب می‌توان با ادامهِ این رویه به مربع لاتین n×n رسید.
اکنون مستطیل لاتین p×q را مورد بررسی قرار داده و متوجه خواهیم شد که گسترش آن‌ها همیشه ممکن نیست.
قضیه۲: اگر L یک مستطیل لاتین p×q با درایه‌هایی از مجموعه {۳٬۲،1...n} باشد، آنگاه L را می‌توان به یک مربع لاتین n×n گسترش داد اگر و تنها اگر مقدار (L(i (تعداد تکرارهای i در L) برای هر n>i>1 در شرط زیر صدق کند:
L(i) ≥ p + q – n
اثبات: فرض می‌کنیم که L قابل گسترش به مربع لاتین n× n باشد:
در شکل روبرو یک مربع لاتین 2*2 را مشاهده کی کنیم نیما مهراندیش 703 حلی 5 دوره اول
چون i به تعداد (L(i مرتبه در L ظاهر شده و P مرتبه در دو بخش M و L با هم ظاهر می‌شود. پس (p - L(i در M تکرار شده‌است. اما از طرفی i به تعداد n - q مرتبه در دو بخش Q و M با هم تکرار می‌شود. پس داریم:
p - L(i) ≤ n – q → L(i) ≥ p + q – n
برعکس فرض کنیم رابطه L(i) ≥ p + q – n به ازای هر i بر قرار باشد و q<n. روشی ارائه می‌دهیم که به وسیلهٔ آن بتوان L را به مستطیل (p×(q+1 گسترش داد و این روش برای مستطیل بدست آمده در مرحله قبل قابل تکرار باشد و بتواند تا ساختن مستطیل لاتین p×n ادامه پیدا کند. از طرفی بنا بر قضیهٔ قبل مطمئن هستیم که این مستطیل p×n قابل گسترش به مربع لاتین n×n است. پس حکم قضیه ثابت می‌شود.
برای هر p>i>1 مجموعه Ai را به صورت زیر تعریف می‌کنیم:
حال نشان می‌دهیم که خانواده {S={A1، A2، A3 ،...، An دارای یک مجموعه نماینده‌های متمایز شامل مجموعهٔ P است. (که این مجموعه را به عنوان ستون اضافی برای گسترش L به مستطیل لاتین (p×(q+1 در نظر می‌گیریم)
برای اثبات وجود مجموعه نماینده‌های متمایز خانواده S باید به دو نکته توجه کنیم.

۱)

A1| = |A2| = |A3| = ... = |Ap| = n – q|
۲) چون هر i در(p-L(i سطر ظاهر نشده و از طرفی p -L(i) ≤ n – q پس هر i در حد اکثر n-q تا از مجموعه‌های A1، A2، ...، Ap ظاهر شده‌است. بنابراین مانند اثبات قضیه قبل اجتماع هر r تا از این مجموعه‌ها شامل حد اقل r عضو متمایز است. در نتیجه طبق قضیه هال یک مجموعه نماینده‌های متمایز از خانوادهٔ مذکور وجود دارد.
حال برای آن که اثبات کنیم مجموعه نماینده‌های متمایز مورد نظر شامل مجموعه P است، باید نشان دهیم:
و سپس از قضیه کمکی ۲ استفاده می‌کنیم. برای پرهیز از پیچیده شدن مسئله این حکم را تنها برای {I={۱٬۲٬۳،... ،r اثبات می‌کنیم. (در حقیقت ما یک مجموعه r عضوی شامل{A1، A2، A3 ،... ،Ar} را بررسی می‌کنیم و بقیه مجموعه‌ها نیز شبیه همین مورد هستند). بنا بر تعریف داریم:
می‌دانیم هر عضو p مانند k دقیقاً p+q-n مرتبه در L ظاهر می‌شود. حال اگر p + q - n <r آنگاه k حد اقل در یکی از Aiها ظاهر شده. بنابراین جمع بالا صفر شده و نا مساوی بر قرار می‌شود.
اما اگر p + q - n ≥ r از لم گفته شده‌استفاده می‌کنیم و با در نظر گرفتن m = p + q – n نتیجه می‌گیریم که:
بنا بر نامساوی فوق طبق قضیه هال خانواده S یک مجموعه نماینده‌های متمایز شامل P دارد. می‌توانیم این مجموعه نماینده‌های متمایز را به عنوان ستون اضافی برای گسترش 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 گسترش یابد.