לא מפורסם

שלום לכם,

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

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

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

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

      

  קבוצת התאים הצהובים קשירה קבוצת התאים הצהובים אינה קשירה

בשפה הזו, צעד אחד לפני סיום המשחק מכיל הלוח שני צבעים A ו-B, וקבוצת הצבע A היא קשירה

התחילו בשתי השאלות הבאות:

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

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

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

בהצלחה,

סקובידו


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

7 תגובות

  • עטרה

    הערה

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

  • רמי

    שאלות להבנה

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

  • עטרה

    הסבר לחידה

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

  • עטרה

    סדרות שמתקבלות זו מזו על ידי תמורה על הצבעים

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

  • רמי

    נסיון לפתרון

    תודה על ההסבר.

    אם הבנתי נכונה, החידה דנה על לוח סופי (או אינסופי) כל שהוא, עם m צבעים (A1,A2, ...,Am), עם מינימום n שלבים לפתרון, מחפשים את הפתרונות השונים זה מזה (שלא ניתן לעבור ביניהם ע"י תמורות של צבעים) במצב המורכב ביותר האפשרי.
    למשל עבור n=1 הפתרון היחיד עבור m=2 הוא A2.
    עבור m=3 n=2 , הפתרון הוא : A2A3
    עבור m=2 n=2 , הפתרון הוא : (A2A1 (A1=A3
    עבור m=4 n=3 , הפתרון הוא : A2A3A4
    עבור m=3 n=3 , הפתרונות הם : (A2A1A4 (A1=A3
    (A2A3A1 (A1=A4
    (A2A3A2 (A2=A4
    עבור m=2 n=3 , הפתרון הוא :
    (A2A1A2 ( A2=A4 , A1=A3

  • עטרה

    נכון מאוד!

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

  • עטרה

    דוגמה

    נתון לוח, שהסדרה A2A3A1 היא פתרון אופטימלי שלו.
    בתחילת המשחק המשבצת השמאלית העליונה היתה בצבע A1.
    נסמן על ידי C את רכיב הקשירות של קבוצת הצבע A1 שמכיל את המשבצת השמאלית העליונה.
    אנו יכולים להסיק את המידע הבא:
    א. הקבוצה A1 אינה קשירה.
    ב. איחוד קבוצת הצבע A2 עם C הוא קבוצה קשירה.
    ג. איחוד קבוצות הצבע A2,A3 עם C הוא קבוצה קשירה.
    ד. הלוח כולו הוא קבוצה קשירה. (זה תמיד נכון.)
    מצד שני, יש מידע שאיננו יכולים לדעת:
    א. האם גם הסדרה A2A1A3 מהווה פתרון אופטימלי של הלוח? כלומר, האם איחוד קבוצות הצבע A1,A2 הוא קבוצה קשירה?
    ב. האם גם הסדרה A3A2A1 מהווה פתרון אופטימלי של הלוח? כלומר, האם איחוד קבוצת הצבע A3 עם C הוא קבוצה קשירה?
    ג. האם גם הסדרה A3A1A2 מהווה פתרון אופטימלי של הלוח? כלומר, האם איחוד קבוצת הצבע A3 עם C הוא קבוצה קשירה, וגם איחוד קבוצות הצבע A1,A3 עם C הוא קבוצה קשירה?
    לכן, הסדרה A2A3A1 אינה חלק של זוג סדרות, שלא ייתכן ששתיהן מהוות פתרונות אופטימליים של אותו לוח.