במשחק הקלפים SET, השחקנים צריכים לזהות כמה שיותר מהר שלשה של קלפים המהווה "סט", מבין 12 קלפים המונחים על השולחן. המשחק אמנם דורש מהירות בזיהוי תבניות, אך מסתתרת מאחוריו מתמטיקה מרתקת, ואף שאלות פתוחות - כאלו שאנחנו עדיין לא יודעים מה התשובה אליהן

סט [1] הוא משחק קלפים, שבו לכל קלף ישנם ארבעה מאפיינים: מספר הצורות שמופיע עליו (אחת, שתיים או שלוש), סוג הצורה שמופיע עליו (מעויין, אליפסה או גל), צבע הצורות (אדום, ירוק או סגול), ומילוי הצורות (ריק, מפוספס, או מלא). להלן כמה קלפי סט, להמחשת הרעיון.

שלשה של קלפים נקראית "סט", אם עבור כל אחד מהמאפיינים: או שכל הקלפים זהים עבורו, או שכולם שונים זה מזה. למשל, השלשה הבאה היא סט, כי מספר הצורות והמילוי זהים בכולם, אולם הצבע והצורה שונים:

ואילו זו אינה סט, כי מספר הצורות אינו זהה בכולן, אך גם אינו שונה בכולן:

המשחק מתנהל כך: מניחים 12 קלפים על השולחן. המשתתף הראשון שמזהה סט לוקח את שלושת הקלפים.כעת, מכניסים שלושה קלפים חדשים, וכן הלאה. לעתים, השחקנים לא מוצאים סט בכל 12 הקלפים, ואז מכניסים שלושה קלפים נוספים, עד שאחד השחקנים מזהה סט. בדרך כלל, שחקנים מוצאים סט ב-15 קלפים סט בקלות יחסית.

והרי לנו שאלה מתמטית מתבקשת: האם בכל קבוצה של 15 קלפים יש בהכרח סט? ואם לא, אז כמה קלפים צריך כדי שבטוח יהיה סט?

ובכן, לפני שננסה לענות על השאלה, הבה נהרוס את המשחק סט לכולם, ונציג אותו בצורה מתמטית: כל קלף מיוצג ע"י ארבעה מאפיינים (צורה, צבע, מילוי ומספר צורות) שלכל מאפיין אחת משלוש אפשרויות. אפשר לייצג קלף כזה ע"י ארבעה מספרים, שכל אחד מהם הוא 0, 1, או 2. למשל, הקלף 0201 אומר שהמאפיין הראשון מקבל ערך 0, השני 2 השלישי 0 והרביעי 1 (ההתאמה בין המאפיינים למספרים היא שרירותית).

כעת, מהו סט? הקלפים 0000, 0001, 0002, למשל, הם סט, כי שלושה המאפיינים הראשונים שווים בכולם, והאחרון שונה בכולם. גם 0102 1112 2122 הם סט, כי המאפיינים הראשון והשלישי שונים בכולם, והשני והרביעי זהים. האם יש איזושהי חוקיות לעניין הזה? בוודאי. אולם כדי לראות אותה בקלות, כדאי לפשט מעט את המשחק.

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

מכאן, שיש בדיוק 9 קלפים. כעת, למשל 00 11 22 הוא סט, וגם 00 21 12.

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

אז האם כל סט מיוצג ע"י קו ישר? ובכן, כן, רק שצריך להבין מה הכוונה בקו ישר.

למשל, הסט 00 21 12 לא נראה כמו קו ישר. אולם אם נדמיין את הטבלה שלנו כממשיכה באופן מחזורי (ויש בזה הגיון, כי ההתחלה מהמאפיין 0 היא שרירותית, היה אפשר להתחיל ב-1 או ב-2), אז הסט הזה נראה כמו קו ישר בציור הבא (התאים הצהובים ממחיש את ה"העתקה" המחזורית):

עכשיו נחזור לשאלה: כמה קלפים אפשר להניח על השולחן בלי שיהיה אף סט? כעת השאלה היא למעשה כמה תאים ניתן לבחור בלי שיהיה אף קו ישר עם 3 תאים.

ובכן, הנה דוגמה ל 4 קלפים בלי אף סט (12, 21, 10, 01):

האם אפשר לשים גם 5 קלפים בלי סט? מסתבר שלא. אפשר להוכיח זאת די בקלות, אבל גם לא קשה לבדוק את כל 126 האפשרויות ל 5 קלפים מתוך 9.

אוקיי, מה לגבי קלפים עם 3 מאפיינים, במקום 2? גם אותם אפשר לתאר כקווים ישרים, הפעם בטבלה תלת ממדית, עם 27 תאים.

אפשר לתאר אוסף של 9 קלפים בלי סט די בקלות (נסו!). האם אפשר לתאר אוסף כזה עם  10 קלפים? ובכן, יש 8,436,285 אפשרויות שונות. אפשר להראות עם מחשב שבכולן יש סט, אולם אפשר גם להוכיח זאת עם כלים מתמטים בסיסיים [2].

ומה לגבי המשחק המקורי עם 4 מאפיינים? כעת יש 81 קלפים. עם מעט מחשבה, ניתן למצוא קבוצה של 20 קלפים ללא סט [2], האם אפשר עם 21? יש כ 13 קווינטיליון אפשרויות (מספר עם 20 ספרות), אז בדיקה ישירה של כולן לא אפשרית. אולם, אפשר להוכיח שבכל קבוצה של 21 קלפים יש בהכרח סט. עם זאת, לכך נדרשים כלים מתמטיים עמוקים למדי.

אבל למה לעצור כאן? מה עם 5 מאפיינים? 6? 7?

ובכן, מסתבר שאלו שאלות מאוד קשות. אנחנו יודעים את התשובה ב 5 מאפיינים (לכל היותר 45 קלפים בלי סט) [3] וב-6 מאפיינים (לכל היותר 112) [4,5]. ככל שמספר המאפיינים גדל כך מורכבות הבעיה גדלה, וההוכחות של התוצאות האלו הן לגמרי לא פשוטות. ב-7 מאפיינים אנחנו כבר לא ממש יודעים מה קורה. אפשר לבנות קבוצה של 236 קלפים בלי סט, אבל אנחנו רק יודעים שבכל קבוצה עם 291 קלפים בהכרח יש סט [5].

לסיום, נעיר שיש עוד שאלות מעניינות רבות בנושא. למשל - מה הסיכוי לראות סט בקבוצה בגודל מסויים? אלו שאלות מסובכות, הניתוח שלהן קשה, ולרבות מהן אנחנו לא יודעים את התשובה. רוצים לחפש קצת סטים? ראו חידה יומית ב [6]. מסתבר שגם במשחק תמים מסתתר היופי שבמתמטיקה.

מקורות:

[1]. https://en.wikipedia.org/wiki/Set_(card_game)

[2]. Davis, B. L., & Maclagan, D. (2003). The card game SET. The Mathematical Intelligencer, 25(3), 33-40.

[3]. Edel, Y., Ferret, S., Landjev, I., & Storme, L. (2002). The classification of the largest caps in AG (5, 3). Journal of Combinatorial Theory, Series A, 99(1), 95-110.

[4]. Edel, Y., & Bierbrauer, J. (2001). Large caps in small spaces. Designs, Codes and Cryptography, 23(2), 197-212.

[5]. Calderbank, A. R., & Fishburn, P. C. (1994). Maximal three-independent subsets of {0, 1, 2} n. Designs, Codes and Cryptography, 4(4), 203-211.

[6]. https://www.setgame.com/set/puzzle