مربع لاتین

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک مربع لاتین در منقوش در شیشه رنگی در کالج کایوس کمبریج.

تعریف[ویرایش]


مربع لاتین یک آرایه ی مربعی (ماتریس مربعی) است که در هر سطر و هر ستون آن اعضای مجموعه A به طور کامل و بدون تکرار قرار داشته باشند.

مثال: در احتمالات ماتریس «متغیر تصادفی دوگانه» (که حاصل جمع هر سطر و ستون آن یک است) یک مربع لاتین است.

Matrix.JPG

حال در مورد مستطیل ها و مربع هایی بحث می کنیم که درایه های آن اعداد صحیح و مثبت هستند. یک مستطیل لاتین A با ابعاد p×q عبارت است از: یک ماتریس p × qکه هر یک از درایه های آن عضو مجموعه {3،2،1...n} بوده و هیچ عضو تکراری در سطر و یا ستون آن بوجود نیاید.در حالت خاص اگر p = q = n آن را مربع لاتین می نامیم.در این صورت هر سطر و هر ستون جایگشتی از مجموعه {3،2،1...n} است.

Mahbod11.JPG

حال این سوال را مطرح می کنیم که آیا یک مستطیل لاتین الزاماً بخشی از یک مربع لاتین است؟ مثال: آیا مستطیل لاتین زیر بخشی از یک مربع لاتین 4×4 است؟یا به عبارت دیگر آیا می توان دو سطر دیگر به این مستطیل لاتین افزود که تبدیل به مربع لاتین 4×4 شود؟

Mahbod71.JPG

به طور مشابه آیا مستطیل لاتین مقابل بخشی از مربع لاتین 5×5 است؟

Mahbod81.JPG

مستطیل لاتین اول می تواند به مربع لاتین گسترش پیدا می کند. مانند :

Mahbod21.JPG

می توان نشان داد که هر مستطیل لاتین p×q با درایه هایی از مجموعه {3،2،1...n} را می توان به مربع لاتین n×n گسترش داد.اما مستطیل دوم قابل گسترش نیست. چون به ستون های اول و دوم وسوم باید عدد «2» اضافه شود.چون این سه عدد «2» باید در دو سطر قرار گیرند پس دو تا از آنها در یک سطر واقع شده اند.بنابراین مربع بدست آمده لاتین نخواهد بود. قبل از این که به بیان قضایای مورد نظر در این بحث بپردازیم، ابتدا به صورت دو قضیه و یک لم کمکی اشاره می کنیم :

قضایای کمکی[ویرایش]


1)قضیه هال(صورت ماتریسی) : ماتریس M یک ماتریس m× n با درایه های صفر و یک می باشد. در این صورت در هر سطر آن یک عدد 1 وجود دارد و در هیچ ستونی بیش از یک عدد 1 وجود ندارد اگر و تنها اگر برای هر مجموعه از سطر ها (مثلاً r تایی) تعداد ستون هایی که 1های این سطر ها در آن ها قرار دارند، حد اقل برابر r باشد.

2)یک خانواده از مجموعه ها به صورت{ S={A1 ، A2 ، A3 ،... ، An را در نظر می گیریم. مجموعه P را نیز یصورت زیر فرض می کنیم:

P زیر مجموعه ی A1∪A2∪...∪An

حال Sدارای یک مجموعه نماینده های متمایز شامل مجموعه P است اگر و تنها اگر:

الف) S یک مجموعه نماینده های متمایز داشته باشد.

ب) برای هر Mahbod101.JPG داشته باشیم: Mahbod91.JPG

لم کمکی[ویرایش]


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

قضایای اصلی[ویرایش]


قضیه1:هر مستطیل لاتین n×p را می توان به مربع لاتین n×n گسترش داد

اثبات: فرض کنیم L مستطیل لاتین n×p باشد. برای هر n>i>1 تعریف می کنیم:

Mahbod123.JPG

یافتن یک سطر اضافی از اعضای مجموعه{3،2،1...n} برای تبدیل L به مستطیل لاتینیp+1)×n) در واقع معادل یافتن یک مجموعه ی نماینده های متمایز از خانواده {S={A1،A2،A3،...،An است. طبق قضیه هال اجتماع هر r تا از این مجموعه ها حداقل شامل r عضو متمایز است که n>r>1 . قبل از ارائه استدلال به دو نکته اشاره می کنیم.

1) A1| = |A2| = |A3| = ... = |An| = n - p| چون هر کدام از این مجموعه ها شامل عضوهایی از مجموعه {3،2،1...n} است که در ستون p عضوی مربوط به آن نیامده اند.

2) به ازای هر 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 را مورد بررسی قرار داده و متوجه خواهیم شد که گسترش آن ها همیشه ممکن نیست.

قضیه2: اگر L یک مستطیل لاتین p×q با درایه هایی از مجموعه {3،2،1...n} باشد، آنگاه L را می توان به یک مربع لاتین n×n گسترش داد اگر و تنها اگر مقدار (L(i (تعداد تکرار های i در L) برای هر n>i>1 در شرط زیر صدق کند:

L(i) ≥ p + q – n

اثبات: فرض می کنیم که L قابل گسترش به مربع لاتین n× n باشد:

Mahbod61.JPG

چون 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 را به صورت زیر تعریف می کنیم :

Mahbod51.JPG

حال نشان می دهیم که خانواده {S={A1 ، A2 ، A3 ،...، An دارای یک مجموعه نماینده های متمایز شامل مجموعه ی P می باشد. (که این مجموعه را به عنوان ستون اضافی برای گسترش L به مستطیل لاتین (p×(q+1 در نظر می گیریم.)

برای اثبات وجود مجموعه نماینده های متمایز خانواده S باید به دو نکته توجه کنیم.

1)[ویرایش]

A1| = |A2| = |A3| = ... = |Ap| = n – q|

2) چون هر i در(p-L(i سطر ظاهر نشده و از طرفی p -L(i) ≤ n – q پس هر i در حد اکثر n-q تا از مجموعه های A1 ، A2 ، ... ، Ap ظاهر شده است. بنا بر این مانند اثبات قضیه قبل اجتماع هر r تا از این مجموعه ها شامل حد اقل r عضو متمایز می باشد.در نتیجه طبق قضیه هال یک مجموعه نماینده های متمایز از خانواده ی مذکور وجود دارد.

حال برای آن که اثبات کنیم مجموعه نماینده های متمایز مورد نظر شامل مجموعه P است، باید نشان دهیم :

Mahbod22.JPG

و سپس از قضیه کمکی 2 استفاده می کنیم. برای پرهیز از پیچیده شدن مساله این حکم را تنها برای {I={1،2،3،...،r اثبات می کنیم. (در حقیقت ما یک مجموعه r عضوی شامل{A1 ، A2 ، A3 ،...،Ar} را بررسی می کنیم و بقیه مجموعه ها نیز شبیه همین مورد هستند). بنا بر تعریف داریم :

Mahbod222.JPG

می دانیم هر عضو p مانند k دقیقاً p+q-n مرتبه در L ظاهر می شود. حال اگر p + q - n <r آنگاه k حد اقل در یکی از Ai ها ظاهر شده. بنا بر این جمع بالا صفر شده و نا مساوی بر قرار می شود.

اما اگر p + q - n ≥ r از لم گفته شده استفاده می کنیم و با در نظر گرفتن m = p + q – n نتیجه می گیریم که :

Mahbod2222.JPG

Mahbod41.JPG

بنا بر نامساوی فوق طبق قضیه هال خانواده 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 گسترش یابد.

منابع[ویرایش]


  • Aspects of combinatorics: a wide-ranging introduction By Victor Bryant

Cambridge University Press، 1993 - Mathematics - 266 pages