תכנון בלוקים

תכנון בלוקים מאוזן הוא מבנה קומבינטורי שבו מאורגנים באופן סימטרי בלוקים של נקודות בקבוצה סופית. תכנוני בלוקים מהווים ענף בתורת הקומבינטוריקה, ויש להם קשרים גם לתורת החבורות ולגאומטריה סופית. הם פותחו לצורך תכנון של ניסויים מוגבלים בסטטיסטיקה; הראשונים שערכו טבלאות של תכנוני בלוקים הם רונלד פישר ופרנק ייטס (1943), מאבות הסטטיסטיקה המודרנית.

נאמר שאנו מבקשים לאמוד במהירות את כוחם של עשרה סוסי עבודה, ובאפשרותנו לרתום למחרשה ארבעה סוסים בכל פעם. דגימה של רביעיות סוסים באקראי תיצור הטיות הנובעות מעצם הדגימה, ולכן רצוי לדגום באופן סימטרי, כך שכל סוס ישתתף בחרישה אותו מספר פעמים. אם חוששים לאינטראקציות אפשר להקפיד יותר, ולדגום כך שכל צמד סוסים יופיע מספר שווה של פעמים. באופן נאיבי אפשר למדוד כמה זמן נדרש מכל רביעיית סוסים לחרוש ניר אחד, אלא שניסוי מלא ידרוש ${\binom {10}{4}}=210$ ימי עבודה. אפשר לבצע במקום זה ניסוי קצר יותר, שיימשך רק 15 ימי עבודה, כך שכל סוס ישתתף בחרישה שש פעמים, וכל שני סוסים ישתתפו בחרישה יחד פעמיים. זהו "תכנון בלוקים מאוזן" עם פרמטרים $(10,15,6,4,2)$. האיזון מאפשר להשיג שונות נמוכה של האומדים בהשוואה לניסוי לא מאוזן באורך דומה.

הגדרה והפרמטרים היסודיים

תכנון בלוקים מאוזן (Balanced Incomplete Block Design, ובקיצור המקובל BIBD) הוא מערכת הכוללת קבוצה של $\nu$ נקודות ומשפחה של $b$ בלוקים, שהם תת-קבוצות בגודל $k$, כך שכל נקודה נמצאת בדיוק ב-$r$ בלוקים, וכל זוג נקודות נמצא בדיוק ב-$\lambda$ בלוקים. הווקטור $(\nu ,b,r,k,\lambda )$ מחזיק את הפרמטרים של המערכת.

הנחות הסימטריה מובילות לשני אילוצים על הפרמטרים: $\nu r=bk$ ו-$r(k-1)=\lambda (\nu -1)$ (הוכחה: ספור נקודות וזוגות של נקודות בבלוקים, בשתי דרכים). בזכות האילוצים האלה, הפרמטרים נקבעים על ידי כל שלושה מתוכם. יש שתי דרכים מקובלות לציין את הפרמטרים: כל החמישה בסדר המופיע לעיל; או רק גודל הקבוצה, גודל הבלוק, ומקדם הכפילות, $(\nu ,k,\lambda )$. לאור ההכללה להלן, מקובל גם הסימון $2-(\nu ,k,\lambda )$.

אי-השוויון של פישר קובע שמספר הבלוקים אינו נופל ממספר הנקודות (כלומר $\nu \leq b$). התנאים האריתמטיים הכרחיים, אבל אינם מספיקים. לדוגמה, לא קיים תכנון עם הפרמטרים $(43,43,7,7,1)$ (Tarry, 1900).

הכללות

תכנון בלוקים מאוזן נקרא גם תכנון-2, משום שהדרישה היא שכל 2 נקודות תהיינה שייכות לאותו מספר בלוקים. בציון הפרמטרים, מדובר בתכנון $2-(\nu ,k,\lambda )$, שבו, בהכרח, $b={\frac {\lambda \nu (\nu -1)}{k(k-1)}}$ ו-$r={\frac {\lambda (\nu -1)}{k-1}}$.

בדומה לזה, אפשר להגדיר תכנון-t לכל t: מערכת שבה כל t-יה של נקודות נמצאת ב-$\lambda$ בלוקים. זהו תכנון $t-(\nu ,k,\lambda )$. התנאי עבור ערך מסוים של t גורר את התנאי לכל ערך נמוך ממנו (עם $\lambda$ אחר), בדיוק כפי שהדרישה שכל זוג נקודות יהיה שייך למספר קבוע של בלוקים (t=2) גוררת את הדרישה שכל נקודה תהיה שייכת למספר קבוע של בלוקים (t=1). תכנון-1 אינו אלא פירוק של קבוצה לבלוקים זרים בגודל קבוע.

מערכת שיוך (association scheme) היא מערכת שבה הזוגות (או באופן כללי יותר תת-הקבוצות בגודל t) מחולקים למשפחות, שבכל אחת מהן יש איזון (ערך $\lambda$) אחר.

תכנוני הבלוקים שבהם עוסק הערך הזה הם אחידים (כל הבלוקים הם בעלי אותו גודל), פשוטים (אין חזרות על בלוקים), ובינאריים (אין חזרות על נקודות). מכאן יכול הקורא להסיק על הכללות לתכנונים שאינם אחידים, אינם פשוטים, או אינם בינאריים.

מקרים פרטיים

תכנון-t עם $\lambda =1$ נקרא מערכת שטיינר: מערכת שבה כל t נקודות שייכת לבלוק יחיד. בפרט, BIBD (כלומר תכנון-2) עם $\lambda =1$ ו-$k=3$, היינו, תכנון $2-(\nu ,3,1)$, הוא מערכת שטיינר משולשת, עם $b={\frac {\nu (\nu -1)}{6}}$ בלוקים ו-$r={\frac {\nu -1}{2}}$. תכנון $2-(n^{2}+n+1,n+1,1)$ הוא מישור פרויקטיבי סופי. מישור פאנו שייך לשתי הקבוצות האלה ($\nu =7$, $n=2$).

תכנונים סימטריים

תכנון-2 שבו מספר הבלוקים שווה למספר הנקודות ($\nu =b$) נקרא תכנון סימטרי. תכנון הוא סימטרי אם ורק אם $k=r$, אם ורק אם $\nu ={\frac {k(k-1)}{\lambda }}+1$. בתכנון סימטרי כל שני בלוקים נחתכים ב-$\lambda$ נקודות, וגם להפך: מערכת של $\nu$ תת-קבוצות בגודל קבוע של קבוצה בגודל $\nu$, שכל שתיים מהן נחתכות במספר קבוע של נקודות, היא תכנון סימטרי. משפט ברוק-רייזר-צ'ולה מציב תנאי על קיומו של תכנון סימטרי $(\nu ,\nu ,k,k,\lambda )$: אם $\nu$ זוגי אז הסדר $k-\lambda$ הוא ריבוע; ואם $\nu$ אי-זוגי צריך להיות פתרון שלם למשוואה הדיופנטית $x^{2}-(k-\lambda )y^{2}-(-1)^{(\nu -1)/2}\lambda z^{2}=0$.

תכנון סימטרי עם $\lambda =1$ הוא מישור פרויקטיבי סופי. לדוגמה, התכנון היחיד עם פרמטרים $(7,7,3,3,1)$ הוא מישור פאנו.

תכנון סימטרי עם $\lambda =2$ נקרא דו-מישור: כל שתי נקודות מוכלות בשני בלוקים, וכל שני בלוקים נחתכים בשתי נקודות. הפרמטרים של תכנון כזה הם $(k(k-1)/2+1,k,2)$, והערך k-2 הוא הסדר שלו. ידועים רק 18 דו-מישורים, מסדר 0, 1, 2, 3, 4 (שלושה), 7 (ארבעה), 9 (חמישה), 11 (שניים). הסדרים 5,6,8,10 אינם אפשריים לפי משפט ברוק-רייסר-צ'ולה.

תכנון סימטרי עם הפרמטרים $(4a-1,4a-1,2a-1,2a-1,a-1)$ נקרא תכנון הדמר; יש התאמה בין תכנונים כאלה לבין מטריצות ריבועיות H שכל רכיביהן 1 או 1-, המקיימות $\ HH^{t}=4aI$.

בניות מתכנון נתון

המשלים של תכנון בלוקים מאוזן הוא התכנון עם אותה קבוצת נקודות, והחלפת כל בלוק במשלים שלו. המשלים של תכנון $(\nu ,b,r,k,\lambda )$ הוא תכנון $(\nu ,b,b-r,\nu -k,\lambda +b-2r)$. המספר $n=r-\lambda$ הוא הסדר של תכנון בלוקים מאוזן. לתכנון ולמשלים שלו יש אותו סדר.

מתכנון $t-(\nu ,k,\lambda )$ מתקבל התכנון הנגזר $(t-1)-(\nu -1,k-1,\lambda )$ על ידי הסרת נקודה מן המרחב ומכל הבלוקים שעוברים דרכה (הבלוקים שאינם עוברים דרכה, מושלכים). ידוע איזה תכנוני-2 סימטריים הם נגזרים.

מתכנון סימטרי אפשר לבנות את התכנון הדואלי עם אותם פרמטרים, שהנקודות שלו הן הבלוקים של התכנון המקורי, ובלוק שלו הוא קבוצת הבלוקים שעוברים דרך נקודה בתכנון המקורי. הבנייה עובדת משום שכל שני בלוקים של תכנון סימטרי נחתכים כאמור ב-$\lambda$ נקודות. מתכנון סימטרי $(\nu ,\nu ,k,k,\lambda )$ אפשר לבנות הטלה, שהיא תכנון $(k,\nu -1,k-1,\lambda ,\lambda -1)$ שהנקודות שלו הן הנקודות בבלוק קבוע של התכנון המקורי, והבלוקים שלו הם החיתוכים של הבלוק הקבוע עם הבלוקים האחרים. אפשר גם לבנות שארית (residual design) שהיא תכנון $(\nu -k,\nu -1,k,k-\lambda ,\lambda )$, על ידי מחיקת כל הנקודות בבלוק קבוע. תכנון $(\nu ,b,r,k,\lambda )$ הוא קוואזי-שארית אם $r=k+\lambda$; כל שארית היא קוואזי-שארית, ואם $\lambda =1,2$ אז גם ההפך נכון (Hall-Connor 1953).

מטריצת החילה

תכנון בלוקים הוא גאומטריית חילה עם אובייקטים משני טיפוסים (נקודות ובלוקים). אפשר לתאר תכנון בלוקים באמצעות מטריצה $\ A\in \operatorname {M} _{b\times \nu }(\mathbb {Z} )$ שערכיה הם 1 (במקומות (x,b) שבהם הנקודה x שייכת לבלוק b) ו-0 (אם לא). מן התנאי על זוגות של נקודות נובע ש-$A^{t}A=\lambda J_{\nu }+(r-\lambda )I_{\nu }$, כאשר I היא מטריצת היחידה, ו-J המטריצה שכל רכיביה 1. כאשר התכנון סימטרי זו מטריצה הפיכה, ומכאן נובע ש-$AA^{t}=A^{t}A$, ולכן כל שני בלוקים נחתכים באותו מספר נקודות. חישוב הדטרמיננטה גם מוכיח את משפט ברוק-רייזר-צ'ולה עבור $\ \nu$ זוגי. (ההוכחה למקרה האי-זוגי יותר מתוחכמת, ומבוססת על ראיית מטריצת החילה כאיזומורפיזם בין תבניות ריבועיות).

דוגמאות

יש BIBD יחיד עם פרמטרים $(6,10,5,3,2)$. יש ארבעה BIBD עם פרמטרים $(8,14,7,4,3)$.

פתירות

תכנון בלוקים מאוזן נקרא פתיר (resolvable) אם אפשר לחלק את הבלוקים שלו למשפחות שכל אחת מהן מהווה חלוקה של המרחב לבלוקים זרים. מישור אפיני סופי הוא פתיר. בעיית 15 התלמידות של קירקמן מבקשת לפתור את מערכת שטיינר המשולשת $(15,35,7,3,1)=S(2,3,15)$. תכנון פתיר מקיים גרסה חזקה של אי-שוויון פישר: $b\geq \nu -1+r$ (ובאופן שקול: $r\geq k+\lambda$).

באופן כללי יותר, תכנון בלוקים מאוזן הוא $\alpha$-פתיר אם יש חלוקה של הבלוקים למשפחות (מספרן בהכרח $r/\alpha$) כך שכל נקודה שייכת בדיוק ל-$\alpha$ בלוקים מכל משפחה. תכנון פתיר הוא תכנון 1-פתיר (כלומר $\alpha =1$). מתקיימת ההכללה של אי-שוויון פישר: $b\geq \nu -1+r/\alpha$. המקרה $\alpha =r$ הוא טריוויאלי: כל תכנון בלוקים $(\nu ,b,r,k,\lambda )$ הוא r-פתיר, על ידי "חלוקה" של הבלוקים למשפחה אחת.

פתירות אפינית

תכנון בלוקים $\alpha$-פתיר הוא אפיני אם כל שני בלוקים ממשפחות שונות נחתכות ב-$\mu$ נקודות, וכל שני בלוקים מאותה משפחה נחתכים במספר קבוע של נקודות (השווה בהכרח ל-$k+\lambda -r$; אם $\alpha =1$ הערך הזה הוא אפס והתנאי נובע מהנחת הפתירות). תכנון פתיר הוא אפיני אם ורק אם $b=\nu -1+r/\alpha$ (אם $\alpha =1$ התנאי הזה שקול ל-$r=k+\lambda$, כלומר, התכנון שלנו הוא קוואזי-שארית). נסמן ב-$s$ את מספר הבלוקים בכל משפחה. הפרמטרים $s,\mu ,\alpha$ קובעים את כל הפרמטרים של תכנון אפיני: $\nu ={\frac {s^{2}\mu }{\alpha ^{2}}}$, $k={\frac {s\mu }{\alpha }}$, ו-$\lambda ={\frac {s\mu -1}{s-1}}$ (ממילא $r={\frac {s^{2}\mu -\alpha ^{2}}{\alpha (s-1)}}$ ו-$b=sr/\alpha$). גם כאן המקרה $\alpha =r$ הוא טריוויאלי: כל תכנון בלוקים סימטרי $(\nu ,\nu ,k,k,\lambda )$ הוא תכנון k-פתיר אפיני.

ידועים תכנוני בלוקים 1-פתירים אפיניים עם s=2, ועם $(s,\mu )=(q,q^{d-2})$ כאשר q היא חזקת ראשוני; דוגמה לטיפוס האחרון היא התכנון שהבלוקים שלו הם העל-מישורים האפיניים במרחב וקטורי מעל השדה מסדר q.

מקורות

• [1] - על תכנונים 1-פתירים אפיניים.

ראו גם

• מערכת שטיינר
• גרף רגולרי בחזקה (strongly regular graph)

קישורים חיצוניים

• תכנון בלוקים, באתר MathWorld (באנגלית)