חידות...

[בגינס]

חידות...

1. מצאו קבוצה בת 8 מספרים שלמים בין 1 ל-100 שאינה מכילה שתי תת-קבוצות שונות עם סכום איברים זהה. 2. נתון לוח שחמט 8X8 סטנדרטי. ניתן להפוך את צבעיהן של המשבצות באופן הבא: בוחרים ריבוע 2X2 או 3X3 או 4X4 על הלוח והופכים את צבעה של כל משבצת בו (שחור ללבן; לבן לשחור). ניתן לחזור על התהליך ללא מגבלות. האם ניתן בדרך זו ליצור כל קונפיגורציה?

 

[טלמון סילבר]

1. אפשר להגדיל 100 ל-128?

 

[בגינס]

לא.

 

[טלמון סילבר]

לא פיר!

 

[טלמון סילבר]

ניסיון לפתרון מס. 1 - בעזרתך.

ובכן, הודות לעזרתך, ננסה משהו כזה: 3, 6, 12, 24, 48, 96, 97, 98. א. אם שני המספרים האחרונים אינם משתתפים באף תת-קבוצה, ונגיד שמתקיים שוויון בין שני הסכומים, אז אפשר לחלק את כל המספרים המשתתפים ב-3 והשוויון ישתמר. אבל תצוגת המספרים בבינארית מראה שבשתי תת-הקבוצות משתתפים ביטים אחרים, ולכן השוויון אינו יכול להתקיים. ב. אם אחד משני המספרים האחרונים שייך לאחת משתי תת-קבוצות, או שניהם משתתפים בהן אבל בתת-קבוצות שונות, אז שני הסכומים יהיו שונים במודולו 3, ולכן לא יכול להתקיים שוויון ביניהם. ג. אם שני המספרים האחרונים משתתפים באותה תת-קבוצה, אז סכום תת-הקבוצה השניה קטן מסכום תת-הקבוצה שלהם, אפילו אם שניהם יעמדו מול כל השאר.

 

[yak141]

פתרון ל-2

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

 

[טלמון סילבר]

../images/Emo45.gif החידה והפתרון נראים מצויין

 

[בגינס]

כל הכבוד לשניכם!