בתשובה להאייל האלמוני, 04/12/04 22:46
דרקון לילדים 266449
בגלל שבכל שלב אפשר לעשות רק אחד משניים - ללחוץ על צפרדע חומה או ירוקה - מספיק אם אני אכתוב את סדרת הצעדים:
ירוק, חום, חום, ירוק, ירוק, ירוק, חום, חום, חום, ירוק, ירוק, ירוק, חום, חום, ירוק.

הרעיון הוא פשוט להפתיע: פשוט לדאוג שלא תגרום לשתי צפרדעים מאותו הצבע להיצמד (עד לקראת הסיום).
דרקון לילדים 266461
תודה.
ראה זה פלא, אתה חדל להשחית את זמנך עם מר פז ומיד זוכה לעשות מצוות.
דרקון לילדים 266668
פאלינדרום!
דרקון לילדים 266674
שתי שאלות:
1. האם אפשר לפתור את הבעיה הכללית של n צפרדעים ירוקות רצופות מול m צפרדעים כחולות רצופות (עם רווח אחד ביניהם)?
2. מתי הפתרון הוא פולינדרום?
דרקון לילדים 266676
אני מקווה שהפנית את השאלה לגדי.
דרקון לילדים 266679
שתי שאלות נוספות:
1. מה זה פאלינדרום?
2. מה זה פולינדרום?
דרקון לילדים 266685
דרקון לילדים 266732
אני מקווה שהפנת את השאלה לשכ"ג... אבל זה מעניין, אני אחשוב על זה.

תחושת הבטן הראשונה אומרת שהבעיה פתירה לכל m=n ושבמקרה זה הפתרון יהיה פאלינדרום. בקשר לשאר המקרים, זה מסקרן.

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

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

3. אחרי שנמציא גרסה תלת ממדית, אפשר יהיה להוסיף גם צבעים.
דרקון לילדים 266744
"Winning ways for your mathematical plays / Elwyn R. Berlekamp, John H. Conway, Richard K. Guy"?

(הספריה לא זמינה בשבוע שבועיים הקרובים. שווה לחכות?)
דרקון לילדים 266762
לא. זה ספר שצריך לקנות.
דרקון לילדים 266765
כאשר m=n , אם קיים פתרון *יחיד* אז הוא בהכרח פאלינדרום (רמז: גם הפתרון ברברס הוא פתרון).
דרקון לילדים 266771
במקרה n=m ניתן לבנות פתרון באינדוקציה. לצורך המחשה, משווים את המצב המתקבל לאחר יחח לזה שמתקבל לאחר יחחייי. אם לאחר יחחייי נוסיף צפרדע ירוקה משמאל וחומה מימין, המצב אנלוגי לזה שלאחר יחח. ההמשך (n=4) יהיה ...חחחחייייחחחחיייחחי (פאלינדרום). מבחינת הדוגמאות עד n=4 אפשר גם להסיק את מבנה הפתרון הפאלינדרומי לכל n, אבל עדיין נדרשת כאן הוכחה מסודרת.

הערה: כמובן שיש לפחות שני פתרונות, אבל אם דורשים שהקפיצה הראשונה תהיה של צפרדע ירוקה, יתכן שהפתרון יחיד.
חרמפפפ 266786
דרקון לילדים 266785
ברור שאם יש פתרון ל m=n הוא חייב להיות פאלינדרום, מטעמי סימטריה (לאחר שהמשחק נגמר, אתה יכול לשחק אותו בחזרה, וקיבלת את המשחק המקורי בהחלפת צבע הצפרדעים ).
דרקון לילדים 266808
אם הפתרון אינו יחיד (ר' הערות לעיל) הכיוון ההפוך יהיה גם פתרון, אבל אין די בסימטריה לבדה כדי להבטיח שפתרונות אלו יהיו פאלינדרומיים. לדוגמא: נניח שעל לוח שחמט מסודרות 8 מלכות לבנות על השורה הראשונה ו-‏8 שחורות על השמינית. אם כעת הדרישה היא להעביר את כל הלבנות לשורה האחרונה ואת כל השחורות לראשונה ע"י מסעים חוקיים (עם או בלי תנאי לגבי המיקום הספציפי אליו צריכה להגיע כל מלכה), לא תתקשה למצוא פתרונות בלתי סימטריים לבעיה.
דרקון לילדים 266829
צודק. אבל צריך להיות גם פתרון פאלינדרומי.
דרקון לילדים 266872
נו, אתה רואה? למה קיווית שעוזי מדבר אלי ולא אלייך?
דרקון לילדים 266874
תגובה 266808
דרקון לילדים 266867
תחושת בטן של מישהו כאן אומרת שאם פתרת ל mXm צפרדעים, תוכל לפתור לכל mXn כאשר n<m. פשוט חזור על הפתרון הקודם כשאתה משמיט ממנו את כל הצעדים אל/מ האבנים החסרות.

חזרה לעמוד הראשי

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים