زوج متناظر در مربعهای لاتین: بررسی دو درایهٔ همجایگاه
مربع لاتین چیست و چگونه زوج متناظر تعریف میشود؟
یک مربع لاتین به اندازهٔ $n \times n$، جدولی است که در هر سطر و هر ستون آن، هر یک از نمادهای $n$تایی، دقیقاً یک بار ظاهر میشود. معمولاً نمادها اعداد $1$ تا $n$ یا حروف لاتین هستند. برای نمونه، یک مربع لاتین $3 \times 3$ به شکل زیر است:
| ستون ۱ | ستون ۲ | ستون ۳ |
|---|---|---|
| ۱ | ۲ | ۳ |
| ۲ | ۳ | ۱ |
| ۳ | ۱ | ۲ |
حال فرض کنید دو مربع لاتین $L_1$ و $L_2$ با همان اندازه $n$ و با همان مجموعه نمادها داشته باشیم. زوج متناظر به دو درایهای گفته میشود که در یک سطر و یک ستون مشخص (همجایگاه) قرار دارند؛ یعنی اگر خانهٔ $(i,j)$ را در نظر بگیریم، مقدار $L_1(i,j)$ و $L_2(i,j)$ با هم یک زوج مرتب میسازند. در این مقاله، زوج متناظر را معمولاً به صورت $(a,b)$ نشان میدهیم که $a$ مقدار از مربع اول و $b$ مقدار از مربع دوم است.
تکرار زوجها و ارتباط با متعامدی (Orthogonality)
یکی از پرسشهای مهم این است: چه تعداد از زوجهای متناظر ممکن در دو مربع لاتین تکرار میشوند؟ اگر دو مربع لاتین متعامد1 باشند، آنگاه هر زوج مرتب $(a,b)$ که در آن $a$ و $b$ از مجموعهی $\{1,\dots,n\}$ هستند، دقیقاً یک بار در سراسر جدول ترکیبی (روی همگذاری دو مربع) ظاهر میشود. در غیر این صورت، برخی زوجها ممکن است غایب باشند یا چند بار تکرار شوند.
برای بررسی این موضوع، جدول فراوانی زوجهای متناظر را تشکیل میدهیم. در این جدول، سطرها نمادهای مربع اول و ستونها نمادهای مربع دوم هستند و در هر خانه تعداد دفعاتی که آن زوج خاص در موقعیتهای همجایگاه دیده میشود را مینویسیم. از آنجا که هر مربع لاتین است، مجموع هر سطر و هر ستون در این جدول برابر $n$ خواهد بود.
| وضعیت دو مربع | تکرار هر زوج متناظر | تعداد کل زوجهای متمایز |
|---|---|---|
| متعامد (Orthogonal) | دقیقاً $1$ بار | $n^2$ (همهٔ زوجها) |
| غیر متعامد (غیر متعامد) | بعضی زوجها $0$، بعضی $\ge 2$ | کمتر از $n^2$ |
برای نمونه، دو مربع لاتین بالا (مثال پیشین) متعامد نیستند، زیرا زوج $(1,1)$ فقط یک بار آمده اما ممکن است زوجی مثل $(2,2)$ اصلاً دیده نشود. با بررسی دقیق میتوان جدول فراوانی را رسم کرد.
روش گامبهگام برای یافتن و شمارش زوجهای متناظر
برای یک جفت مربع لاتین دلخواه، مراحل زیر را برای تحلیل زوجهای متناظر دنبال میکنیم:
- گام ۱: دو مربع لاتین $L_1$ و $L_2$ را به صورت دو جدول مجزا بنویسید.
- گام ۲: برای هر خانه $(i,j)$ از $i=1$ تا $n$ و $j=1$ تا $n$، زوج $(L_1(i,j), L_2(i,j))$ را ثبت کنید.
- گام ۳: یک جدول $n \times n$ بسازید که سطرها متناظر با مقدار $L_1$ و ستونها متناظر با مقدار $L_2$ باشند. در خانهٔ $(a,b)$ تعداد دفعات وقوع زوج $(a,b)$ را قرار دهید.
- گام ۴: مجموع هر سطر و هر ستون را بررسی کنید. اگر همهٔ مجموعها برابر $n$ باشند، آنگاه جدول فراوانی یک ماتریس دوضربی (doubly stochastic) خواهد بود. در حالت متعامد، این ماتریس همان ماتریس جایگشتی یکتاست (یعنی هر سطر و هر ستون دقیقاً یک $1$ و بقیه صفر دارد).
$L_1 = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix}$ و $L_2 = \begin{bmatrix} 1 & 3 & 2 \\ 2 & 1 & 3 \\ 3 & 2 & 1 \end{bmatrix}$.
لیست زوجها در خانههای همجایگاه: (1,1), (2,3), (3,2), (2,2), (3,1), (1,3), (3,3), (1,2), (2,1). هر زوج مرتب از مجموعه {1,2,3} دقیقاً یک بار ظاهر شده است؛ بنابراین این دو مربع متعامد هستند و همهٔ $9$ زوج ممکن را به عنوان زوج متناظر داریم.
کاربرد عملی: طراحی آزمایشها و جداول مرتبهبندی
مفهوم زوج متناظر در دو مربع لاتین کاربرد مستقیم در طراحی آزمایشهای فاکتوریل دارد. فرض کنید میخواهیم تأثیر دو عامل مختلف (مانند نوع کود و میزان آبیاری) را بر روی محصول کشاورزی آزمایش کنیم. هر عامل را در $n$ سطح مختلف در نظر میگیریم. اگر یک طرح آزمایشی بر اساس دو مربع لاتین متعامد طراحی کنیم، آنگاه هر ترکیب از سطوح دو عامل (هر زوج متناظر) دقیقاً یک بار در کل آزمایش تکرار میشود و این باعث حذف خطاهای سیستمی میشود. به عبارت دیگر، با استفاده از زوجهای متناظر در دو مربع لاتین متعامد، یک طرح بلوکی کامل و متعادل خواهیم داشت.
همچنین در رمزنگاری کلاسیک، گاهی از دو مربع لاتین برای ساختن جدول جانشینی دو بعدی استفاده میشود. زوجهای متناظر در حقیقت نگاشتی از یک نماد به یک جفت نماد هستند که امنیت رمز را افزایش میدهد. هر چه تعداد زوجهای متمایز بیشتر باشد (حداکثر $n^2$)، فضای کلید بزرگتر خواهد بود.
چالشهای مفهومی
۱) آیا ممکن است در دو مربع لاتین، یک زوج متناظر بیش از یک بار تکرار شود؟
بله، اگر دو مربع لاتین متعامد نباشند، ممکن است یک زوج خاص چندین بار در خانههای مختلف تکرار شود. برای نمونه، اگر $L_1 = L_2$ (دو مربع یکسان)، آنگاه زوج $(a,a)$ برای هر $a$ دقیقاً $n$ بار تکرار میشود (چون در هر سطر یک بار مقدار $a$ ظاهر میشود). بنابراین تکرار بیش از یک بار امکانپذیر است.
۲) آیا هر دو مربع لاتین هماندازه، حتماً حداقل یک زوج متناظر یکسان دارند؟
خیر. برای $n \ge 2$ میتوان دو مربع لاتین ساخت که در هیچ خانهای مقادیر یکسان نداشته باشند. چنین مربعهایی را فاقد زوج یکسان مینامند. برای $n=3$ مثال متعامد بالا را ببینید: در هیچ خانهای $L_1(i,j) = L_2(i,j)$ نیست، بنابراین زوج متناظری با دو عدد برابر وجود ندارد.
۳) چگونه میتوان تعداد کل زوجهای متناظر متمایز را بدون شمردن همهٔ خانهها به دست آورد؟
تعداد کل زوجهای متمایز (تکرار نشده) در دو مربع لاتین همیشه بین $n$ و $n^2$ است. مقدار دقیق آن برابر است با تعداد زوجهای $(a,b)$ که حداقل یک بار در جدول فراوانی مقدار مثبت دارند. از آنجا که مجموع کل زوجها (با تکرار) برابر $n^2$ است، اگر میانگین تکرار هر زوج متمایز را $k$ بگیریم، تعداد زوجهای متمایز برابر $n^2/k$ خواهد بود. اما برای محاسبه دقیق، باید حداقل یک بار کل خانهها را پیمایش کرد.
پاورقی
1 متعامد (Orthogonal): دو مربع لاتین $L_1$ و $L_2$ را متعامد گوییم هرگاه در روی همگذاری آنها، هر زوج مرتب $(a,b)$ از نمادها دقیقاً یک بار ظاهر شود. این شرط معادل آن است که جدول فراوانی زوجهای متناظر، هر درایهٔ غیرصفر برابر یک داشته باشد و دقیقاً $n^2$ درایهٔ یک وجود داشته باشد.