חידות שח-מט

[yak141]

חידות שח-מט

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

 

[yak141]

לאן נעלמו כל חובבי הקומבינטוריקה?

מפליא אותי שאין כלל התעניינות בחידות.... טוב נו... ניחא.

 

[ררדד]

נסיונות

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

 

[ררדד]

הוכל=נוכל כמובן..../images/Emo163.gif

 

[snogal]

ג

צריחים: מספר מקסימלי 8. כל צריח מאיים על כל השורה שהוא תופס , סה"כ ישנן 8 שורות. מספר אפשרויות לסידור: !8 פרשים: מספר מקסימלי 32 , כל הפרשים על אותו צבע. מספר אפשרויות לסידור 2 (או על משבצות לבנות או על שחורות.) מלכים: מספר מקסימלי 16 . מספר אפשרויות לסידור 32 (???) רצים:

 

[rainbow16]

הממ.. ג'

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

 

[ררדד]

ד

התשובות דומות בחלקן לסעיף הקודם (מה שגורם לי לפקפק בהן..) א) צריחים: מס' מינימלי 8, כאשר כמו בתשובתו של סנוגל, מספר אפשרויות הסידור הוא !8 ב) רצים: מספר הרצים המינימלי הוא 8, ויש 4 אפשרויות סידור (בטור לאורך הלוח על אחד מהישרים האמצעיים, ואותו דבר לרוחב הלוח) ג) מלכים: 16 מלכים ואין לי שמץ של מושג לגבי מספר אפשרויות הסידור. ד) פרשים: מספר מינימלי כדי לאיים על כל הלוח- 16, כאשר הם מסודרים לאורך השורות: (1,6) (2,6) (3,6) (2,7) (3,8). מספר אפשרויות הסידור הוא 12 (לאורך ולרוחב הלוח). האחרון לגמרי לפי ניסוי וטעיה אז לא יודע אם צדקתי בו, או בכלל..

 

[ררדד]

ד -הפעם פלוס תיקון קטן לסעיף האחרון

התשובות דומות בחלקן לסעיף הקודם (מה שגורם לי לפקפק בהן..) א) צריחים: מס' מינימלי 8, כאשר כמו בתשובתו של סנוגל, מספר אפשרויות הסידור הוא !8 ב) רצים: מספר הרצים המינימלי הוא 8, ויש 4 אפשרויות סידור (בטור לאורך הלוח על אחד מהישרים האמצעיים, ואותו דבר לרוחב הלוח) ג) מלכים: 16 מלכים ואין לי שמץ של מושג לגבי מספר אפשרויות הסידור. ד) פרשים: מספר מינימלי כדי לאיים על כל הלוח- 16, כאשר הם מסודרים לאורך השורות: (1,6) (2,6) (3,6) (2,7) (3,7) (3,8). מספר אפשרויות הסידור הוא 12 (לאורך ולרוחב הלוח). האחרון לגמרי לפי ניסוי וטעיה אז לא יודע אם צדקתי בו, או בכלל..

 

[ררדד]

אוף אני אידיוט!

בשאלה האחרונה הסעיף של מלכים- המספר מינימלי שיאיים על כל הלוח הוא 9 אבל עדיין אין לי מושג לגבי מספר אפשרויות הסידור

 

[yak141]

חלק מהפתרונות נכונים אבל....

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

 

[rainbow16]

המממ..

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

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

 

[tamir eliav]

ניסיון לפתור את ג

ג. 8 צריחים, !8 אפשרויות סידור. 8 רצים, 10 סידורים. 16 מלכים, 4 סידורים. 24 פרשים, 4 סידורים. אבל לא מוכח.

 

[ררדד]

בקשר לרצים

אם תעמיד את כולם בשורה הראשונהת תוכל להעמיד עוד 6 בשורה השמינית (עוד 6 כי ניתן להעמיד רק אחד בקצה האלכסונים הראשיים)

 

[אלישע האחר]

א"א

ראה פתרון מלא במשפט האחרון של פרמה

 

[yak141]

תודה על ההצעה

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

 

[בגינס]

הוכחות ל-א ול-ב...

אנסה להוכיח את הפתרונות... א. אם מוציאים שתי משבצות מהלוח בעלות אותו הצבע, הרי נותרות על הלוח 32 משבצות בצבע אחד ו-30 בצבע אחר. אבל כלי הדומינו מכסים משבצות סמוכות, כלומר משבצות בעלות צבעים מנוגדים, ועל כן לוח זה אינו ניתן לכיסוי כנדרש. ב. במקרה זה הכיסוי אפשרי. ניתן להוכיח זאת ע"י המסלול של Ralph Gomory (ראה קובץ מצורף). הוצאת שתי משבצות בעלות צבעים מנוגדים תיתן לוח עם 31 משבצות בכל צבע, ואותו ניתן לכסות ע"י 31 כלי דומינו. למשל, אם מוציאים את המשבצות 30 ו-52 אז אחד המסלולים הוא מ-31 עד 54, והשני מ-54 עד 29.

 

[yak141]

פתרון נכון מאוד ../images/Emo24.gif

הפתרון ל-א' יפה ומדויק ובמקרה זה אציין גם אץ פתרונו של רדדד שנכון באותה מידה.

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

 

[בגינס]

תגובה...

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

{1,2,...,64}​

נתיחס לזוג (64,1) כזוג מספרים עוקבים (כלומר סידרנו את הקבוצה, למשל, במעגל עם כיוון השעון בסדר עולה) אם מוציאים שני מספרים, כך שאחד זוגי והשני אי-זוגי, האם ניתן ליצור שתי תתי קבוצות, כך שאת כולן ניתן לסדר בסדרה של מספרים עוקבים בסדר עולה ומספר איבריהן זוגי? התשובה לכך חיובית (בהנחה כמובן שהסדרה: (61,62,63,64,1,2) היא סדרה של מספרים עוקבים בסדר עולה). נבהיר: יהיו i ו-j שני מספרים כלשהם בקבוצה הנ"ל, המקיימים:

64>=i>j>=1​

נניח בה"כ ש-i זוגי ו-j אי-זוגי. לאחר הוצאתם מהקבוצה המקורית נותרנו עם קבוצה בת 62 איברים. i כאמור זוגי, ולכן המספר העוקב לו הוא אי-זוגי. j אי-זוגי, ולכן המספר ש-j עוקב לו הוא זוגי. לכן אם נתבונן בקבוצה:

{i+1,...,j-1}​

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

{j+1,...,i-1}​

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

 

[yak141]

נראה די טוב!!! ../images/Emo6.gif