קומבינטוריקה

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

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

  • רצים - לא מוגנים

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

  • רצים - שמורים

    כמה רצים נחוצים כדי שכל משבצת תהיה מאויישת או מותקפת, וכל רץ יהיה שמור על ידי רץ אחר? ואיך ניתן למקם אותם? מקורות:

  • בישופים בהתכנסות

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

  • שמונה מלכות

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

  • שמונת הכוכבים

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

  • בעיה בפסיפסים

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

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

     

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

    מקורות:

  • מתחת לצעיף

    אם הקורא יבחן את הדיאגרמה לעיל, הוא יראה שמיקמתי שמונה אותיות V, שמונה אותיות E, שמונה אותיות I ושמונה אותיות L בדיאגרמה כך שאף אות אינה נמצאת בקו אחד עם אות דומה לה אופקית, אנכית או אלכסונית. לכן, אף V אינו בקו אחד עם V אחר, אף E עם E אחרת, וכן הלאה. ישנן דרכים רבות ושונות לסדר את האותיות בתנאי זה. החידה היא למצוא סידור שמניב את המספר הגדול ביותר האפשרי של מילים בנות ארבע אותיות, בקריאה מלמעלה למטה ומלמטה למעלה, אחורה וקדימה, או באלכסון. כל החזרות נחשבות למילים שונות, וחמשת הוריאציות שניתן להשתמש בהן הן: VEIL, VILE, LEVI, LIVE ו-EVIL.

    זה יובהר לחלוטין כשאומר שהסידור לעיל מקבל ניקוד של שמונה, מכיוון שהשורה העליונה והתחתונה נותנות שתיהן VEIL; הטורים השני והשביעי נותנים שתיהן VEIL; ושני האלכסונים, החל מה-L בשורה החמישית וה-E בשורה השמינית, נותנים שתיהן LIVE ו-EVIL. לכן ישנן שמונה קריאות שונות של המילים בסך הכל.

    חידת מילים קשה זו ניתנת כדוגמה לשימוש בניתוח לוח שחמט בפתרון דברים כאלה. רק אדם שמכיר את בעיית "שמונה המלכות" יכול לקוות לפתור אותה.

    מקורות:

  • הריבוע של באשה

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

    שימו לב ל"שורה של ארבעה קלפים", כך שהאלכסונים היחידים שעלינו להתייחס אליהם כאן הם שני הארוכים.

    מקורות:

  • קוביות האותיות - שלושים ושש

    האיור מייצג קופסה המכילה שלושים ושש קוביות אותיות. החידה היא לסדר מחדש את הקוביות כך שאף A לא יהיה בקו אנכי, אופקי או אלכסוני עם A אחר, אף B עם B אחר, אף C עם C אחר, וכן הלאה. תגלו שאי אפשר להכניס את כל האותיות לקופסה בתנאים אלה, אך העניין הוא למקם כמה שיותר. כמובן שאסור להשתמש באותיות אחרות מלבד אלה המוצגות. מקורות:

  • לוח השחמט הצפוף

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