שיעור 33

ALS-XZ

הכלל

שתי קבוצות כמעט נעולות המקושרות באמצעות מועמד משותף מוגבל מחייבות מועמד משותף נוסף להופיע לפחות באחת מהן, ולכן ניתן להסיר את אותו מועמד מכל תא מחוץ לשתי הקבוצות שרואה את כל התאים עם אותו מועמד בשתי הקבוצות יחד.

צעד אחר צעד

1. הסתכלו על הקבוצה הראשונה . 2 התאים האלה נמצאים כולם באותה שורה ויש בהם יחד 3 מועמדים שונים, אחד יותר ממספר התאים. זה נקרא Almost Locked Set (ALS).
2. כעת הסתכלו על הקבוצה השנייה . 3 התאים האלה נמצאים כולם באותה שורה ויש בהם יחד 4 מועמדים שונים, אחד יותר ממספר התאים, ולכן גם הם יוצרים ALS. הקבוצות חולקות את 3 כמועמד משותף מוגבל (RCC): כל תא עם 3 בקבוצה אחת רואה את כל התאים עם 3 באחרת. לכן ניתן להציב את הספרה 3 לכל היותר באחת הקבוצות, ולעולם לא בשתיהן.
3. שתי הקבוצות מכילות את 5 כמועמד. מכיוון שניתן להציב את הספרה 3 לכל היותר בקבוצה אחת, לפחות קבוצה אחת לא תשתמש ב-3. בקבוצה שאינה משתמשת ב-3 נותר מספר מועמדים שונים השווה למספר התאים, ולכן כל אחד מהם, כולל 5, חייב להופיע בתוכה. לכן 5 חייב להופיע לפחות באחת משתי הקבוצות, וניתן להסיר את המועמד 5 מכל תא מחוץ לשתי הקבוצות שרואה את כל התאים עם המועמד 5 בשתי הקבוצות יחד. מכאן השם: X הוא 3, המועמד המשותף לשתי הקבוצות, ו-Z הוא 5, המועמד שמסירים.