משחק

[milloarnon]

משחק ../images/Emo35.gif

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

 

[עריסטו]

פתרון

נכתוב בכל משבצת של הלוח מספר, כמו בתמונה המצורפת (התמונה מראה את 16 המשבצות בפינה בשמאלית העליונה של הלוח). נשים לב כי בכל צעד במשחק סכום המספרים במשבצות התפוסות אינו משתנה. נבדוק מה סכום המספרים בכל הלוח: סכום המספרים בשורה הראשונה הוא 2, סכום המספרים בשורה השניה הוא 1, סכום המספרים בשורה השלישית הוא 1/2,... לכן סכום המספרים בכל הלוח הוא 4. סכום המספרים בעשרת המשבצות עליהן מדובר בחידה הוא 3.25. לכן אם הן פנויות סכום המספרים במשבצות התפוסות יכול להיות לכל היותר 0.75. במצב ההתחלתי של המשחק סכום המספרים במשבצות התפוסות הוא 1, וכאמור סכום זה אינו משתנה במהלך המשחק. לכן לא ניתן לפנות את עשרת המשבצות.

 

[עריסטו]

שכחתי לצרף התמונה ../images/Emo163.gif

הנה

 

[milloarnon]

../images/Emo45.gif ../images/Emo41.gif ../images/Emo127.gif ../images/Emo41.gif ../images/Emo45.gif

מרשים מאוד. האם חשבת על התשובה הזאת בעצמך או שזכרת\מצאת אותה איפשהוא ?

 

[srulikbd]

באמת מדהים ../images/Emo13.gif יש עוד פתרונות

אלגנטיים שכאלה

 

[עריסטו]

יש

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

 

[עריסטו]

ברור שלא חשבתי על זה לבד... ../images/Emo3.gif

כלומר חשבתי על זה לבד אבל בהשראת חידת החיילים של Conway: http://www.cut-the-knot.org/proofs/checker.shtml שההוכחה שלה דומה מאוד

 

[srulikbd]

שאלה

דווקא החידה של CONWAY לא כל כך דומה לפי דעתי, אז יפה שהצלחת

בטח אפשר איכשהו לשלב את זה בחידות שחמט, אולי אתה מכיר שילוב כזה

 

[עריסטו]

לא מכיר, אם כי יש חידות שחמט

שהרעיון בהן מתמטי.

 

[עריסטו]

חידות המשך

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

 

[עריסטו]

../images/Emo208.gif

 

[srulikbd]

:|

שאלה נחמדה

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

(כי אין לי רעיון אחר

) קיצר רמז

 

[עריסטו]

לא הייתי שואל את א' וב' אם זה היה

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