برنامهریزی با مربعهای لاتین متعامد: تنظیم دو ویژگی همزمان، بهطوری که هر زوج ویژگی دقیقاً یکبار رخ دهد
مربع لاتین چیست؟ قانون «تکتک بودن» در سطرها و ستونها
یک مربع لاتین جدولی به ابعاد $n \times n$ است که در هر سطر و هر ستون آن، هر یک از $n$ نماد (مثل اعداد $1$ تا $n$) دقیقاً یک بار ظاهر شود. به عبارت ساده: اگر به هر سطر مثل یک ردیف از صندلیها نگاه کنید، هیچ نمادی تکرار نمیشود. همین قانون برای ستونها نیز برقرار است.
مثال علمی ساده: فرض کنید یک دبیرستان قصد دارد $4$ آزمون مختلف (ریاضی، فیزیک، شیمی، زیست) را در $4$ ساعت متفاوت و $4$ کلاس مجزا برگزار کند. اگر بخواهیم در هر ساعت هر آزمون دقیقاً یک بار برگزار شود و در هر کلاس نیز هر آزمون فقط یک بار باشد، از یک مربع لاتین مرتبه $4$ استفاده میکنیم. سطرها نشاندهنده کلاسها، ستونها نشاندهنده ساعتها و درون جدول نام آزمون قرار میگیرد.
| سطر\ستون | ستون ۱ | ستون ۲ | ستون ۳ |
|---|---|---|---|
| سطر ۱ | $1$ | $2$ | $3$ |
| سطر ۲ | $2$ | $3$ | $1$ |
| سطر ۳ | $3$ | $1$ | $2$ |
مشاهده میکنید که در هر سطر اعداد $1,2,3$ دقیقاً یک بار آمده و در هر ستون نیز همین قانون برقرار است. چنین ساختاری پایهی اصلی برنامهریزی یکبعدی است.
تعامد (Orthogonality): دو مربع لاتین چگونه با هم ترکیب میشوند؟
حال فرض کنید دو ویژگی متفاوت داریم. مثلاً ویژگی اول نوع نوشیدنی (آبمیوه، چای، قهوه) و ویژگی دوم نوع خوراکی (بیسکویت، کیک، میوه). میخواهیم هر ترکیب (آبمیوه+بیسکویت)، (آبمیوه+کیک)، ... دقیقاً یک بار در یک برنامهریزی زمانی ظاهر شود. این کار با مربعهای لاتین متعامد انجام میشود.
دو مربع لاتین $A$ و $B$ از مرتبه $n$ را متعامد میگوییم اگر هر جفت مرتب $(A_{ij}, B_{ij})$ برای تمام سلولها یکتا باشد. به زبان ساده: هفتهای ترکیب نمادها در تمام خانههای جدول، هیچ تکراری ندارند.
مثال عینی: برای $n=3$ دو مربع لاتین زیر را در نظر بگیرید:
| سلول (i,j) | مربع اول (نوشیدنی) | مربع دوم (خوراکی) | زوج ترکیبی |
|---|---|---|---|
| (1,1) | آ | ب | (آ،ب) |
| (1,2) | ب | ک | (ب،ک) |
| (1,3) | ج | م | (ج،م) |
| (2,1) | ب | م | (ب،م) |
| (2,2) | ج | ب | (ج،ب) |
| (2,3) | آ | ک | (آ،ک) |
اگر جدول کامل را بنویسید، میبینید همه $9$ زوج ممکن دقیقاً یک بار ظاهر میشوند.
ساخت گامبهگام یک برنامه دو ویژگی بدون تکرار زوجها
فرض کنید میخواهیم یک کارگاه آموزشی با $4$ مربی و $4$ موضوع برگزار کنیم. هر مربی باید هر موضوع را دقیقاً یک بار تدریس کند و همچنین هر زوج (مربی، موضوع) فقط در یک بازه زمانی مشخص رخ دهد. این معادل طراحی دو مربع لاتین متعامد است.
مرحله ۱: یک مربع لاتین مبنا برای مربیها میسازیم (با اعداد $0,1,2,3$):
مرحله ۲: مربع لاتین دوم برای موضوعها (متعامد با اولی) از رابطه:
مرحله ۳: با قرار دادن جفتها $(A_{ij}, B_{ij})$ در هر خانه، همه $16$ ترکیب ممکن بدون تکرار حاصل میشود. کافی است سطرها را زمانها و ستونها را مکانها در نظر بگیریم.
کاربرد عملی: آزمایش کشاورزی و جدول زمانی مسابقات
فرض کنید یک پژوهشگر کشاورزی میخواهد اثر $3$ نوع کود و $3$ نوع آبیاری را روی رشد گیاه آزمایش کند. اگر او هر ترکیب را در یک قطعه زمین متمایز و در یک زمان خاص کاشت، به $9$ قطعه نیاز دارد. اما با کمک مربع لاتین متعامد میتواند $3$ زمان و $3$ مکان را به گونهای تنظیم کند که هر زوج (کود، آبیاری) دقیقاً یک بار ظاهر شود و اثرات مزاحم مکانی و زمانی نیز کنترل گردد.
مثال دیگر: در مسابقات ورزشی، اگر $5$ تیم داشته باشیم و بخواهیم هر دو تیم دقیقاً یک بار با هم بازی کنند، یک مربع لاتین متعامد از مرتبه $5$ (که برای اعداد اول وجود دارد) برنامه دور برگشت را بدون تداخل زمانی فراهم میکند.
چالشهای مفهومی
پاسخ: خیر. برای $n=2$ دو مربع لاتین متعامد وجود ندارد (حداکثر یک جفت). برای $n=6$ نیز تا مدتها اثبات شده بود وجود ندارد (مسئله ۳۶ افسر اویلر). برای توانهای اعداد اول و اعداد صحیح بزرگتر از $2$ به جز $6$ معمولاً وجود دارند.
پاسخ: اگر نمادهای مربع اول را $a$ و مربع دوم را $b$ بنامیم، کافی است لیست همه جفتهای $(a,b)$ را بسازیم. اگر تعداد جفتهای یکتا برابر $n^2$ باشد، متعامدند. روش سریعتر: برای هر $i,j$ اگر $A_{ij}=A_{kl}$ و $B_{ij}=B_{kl}$ همزمان فقط زمانی رخ دهد که $(i,j)=(k,l)$.
پاسخ: حداکثر تعداد $n-1$ است. یعنی اگر $n$ عدد اول یا توانی از عدد اول باشد، یک مجموعه کامل از $n-1$ مربع لاتین متعامد دوتایی وجود دارد که با میدانهای متناهی ساخته میشوند.
پاورقی
1 طراحی آزمایشها (Design of Experiments): روشی آماری برای برنامهریزی آزمونها به گونهای که نتایج معتبر و قابل تعمیم باشند.
2 مربع لاتین (Latin Square): جدول $n \times n$ با $n$ نماد متفاوت که هر نماد در هر سطر و هر ستون یک بار ظاهر میشود.
3 تعامد (Orthogonality): ویژگی دو مربع لاتین که در آن تمام جفتهای مرتب نمادها منحصربهفرد باشند.
4 مربع یونانی-لاتین (Graeco-Latin Square): حاصل ترکیب دو مربع لاتین متعامد که در هر خانه یک زوج (نماد یونانی، نماد لاتین) قرار دارد.