21 באוקטובר, 2010

חידות מתמטיות מחברים מהאמצע

רקע

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

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

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

נסביר:

סדר הפתרון של בעיה מתמטית הוא בדרך כלל:

  1. נוסח החידה: שומעים את החידה המלאה.
  2. העקרון לפתרון: מזהים עיקרון מתמטי שיש ליישם כדי לפתור.
  3. פתרון: יישום ספציפי של העקרון, עם פרטים המכוונים לחידה.

סדר הבנייה של חידה מתמטית הוא:

  1. העקרון לפתרון: בוחרים את העקרון שישמש בפתרון החידה.
  2. פתרון: מנסחים באופן מפורט את היישום של העקרון.
  3. נוסח החידה: תופרים את החידה סביב הפתרון.

דוגמא לעקרון לפתרון

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

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

חידה בינוניתמספרים זרים: מבין המספרים 1 עד 100 בוחרים 51 מספרים. הוכח שיש ביניהם שנים זרים. (שני מספרים שלמים וחיוביים הם זרים אם אין להם אף מכנה משותף גדול מ- 1).

חידה קשהלחיצות ידים: שישה אנשים היו בחדר.  יש להוכיח שתמיד יש שלושה אנשים ששלושתם לחצו זה לזה ידים, או שלושה שאף אחד מהם לא לחץ לאף אחד מהם יד.

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

עקרון שובך היונים

ניסוח אינטואיטיבי: אם מכניסים 11 יונים לשובך עם 10 תאים, אז לפחות בתא אחד חייבות להיות לפחות שתי יונים.
ניסוח מתמטי בסיסי: אם משבצים n+1 (או יותר) עצמים ל- n קבוצות, אז לפחות בקבוצה אחת יהיו לפחות שני עצמים.
ניסוח מתמטי מלא למקרה הבדיד: יהיו n, k, r מספרים טבעיים (כלומר: שלמים וחיוביים).  אם משבצים kn+r עצמים ל- n קבוצות, אז לפחות קבוצה אחת תכיל לפחות k+1 אברים.

פתרונות לחידות

עצור!

אם אתה רוצה לנסות ולפתור את החידות בעצמך – זה הזמן.  בתום הסעיף זה יהיה מאוחר מדי.

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

בחידה הזו, העצמים היו הגרבים והקבוצות היו הצבעים.

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

מספרים זרים:
נגדיר את הקבוצות כזוגות עוקבים של מספרים שהנמוך בהם הוא אי-זוגי, כלומר:
1,2 היא קבוצה אחת
3,4 היא קבוצה שניה
וכך הלאה עד הקבוצה החמישים: 99,100

לפי עקרון שובך היונים, אם אנחנו מחלקים 51 מספרים ל- 50 הקבוצות האלו, לפחות באחת הקבוצות יהיו שני אברים.

המסקנה מכך היא שבין ה-51 מספרים חייבים להיות שנים עוקבים.
כל שני מספרים עוקבים הם זרים.
מש"ל (מה שרצינו להוכיח).

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

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

נכנה את האנשים א, ב, ג, ד, ה, ו.

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

עכשיו נשאלת השאלה – האם בין שלושת האנשים, א, ב, ג, יש שנים שלחצו ידים?
אם כן, נגיד שאלה א, ב, אז השלושה א,ב,ו לחצו כולם את ידי כולם.
אם לא – אז בשלשה א,ב,ג אף אחד לא לחץ את ידו של אף אחד אחר.

כך, בכל מקרה יש או שלושה שלחצו ידים או שלושה שלא לחצו ידים.

הערות:

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

חידה מאולימפיאדה:
בחידות שבאולימפיאדות תמיד יש סיבוך נוסף.  במקרה הזה יש להשתמש פעמיים בעקרון שובך היונים.

יש תשעה מספרים ראשוניים קטנים מ- 26: 2,3,5,7,11,13,17,19,23
לכן כל ה-1985 מספרים שלנו הם מכפלות של חזקות של תשעת הראשוניים האלה.

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

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

עכשיו, גם על הזוגות האלה אפשר לעשות את אותו התהליך.
הפעם המגירות לא יהיו האם כל אחד מהגורמים הראשוניים הוא זוגי או אי-זוגי, אלא האם הוא מתחלק בארבע עם שארית 2 או בלי שארית.
שוב, יש שני מצבים אפשריים לתשעה מספרים ראשוניים, לכן יש שתים בתשיעית מגירות (קבוצות), כלומר 512 קבוצות.
כיוון ש- 737 גדול מ- 512, יש שני זוגות שמתאימים בכל המספרים הראשוניים, כלומר:
אם בפירוק לגורמים ראשוניים של הזוג האחד מופיע הראשוני 3 מספר המתחלק ל- 3 בלי שארית של פעמים, אז כך גם בזוג האחר,
ואם בפירוק של הזוג הראשון מופיע הראשוני 11 מספר המתחלק ב- 4 עם שארית 2 של פעמים, אז כך גם בזוג האחר,
וכך לכל תשעת הגורמים הראשוניים.
הפירוק של מכפלת המספרים בנויה מהצירוף של הגורמים הראשוניים בפירוק של שני המספרים, ולכן החזקה של כל גורם ראשוני היא או סכום של שני מספרים המתחלקים בארבע בלי שארית, ולכן מתחלק בארבע, או שהוא סכום של שני מספרים זוגיים המתחלקים לארבע כל אחד עם שארית 2, ושוב – הסכום מתחלק בארבע.

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

מש"ל.

כיצד לחבר חידה משלך

בשלב הראשון, החלט על העקרון של הפתרון.  נניח שהחלטת על עקרון שובך היונים.

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

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

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

עוד על חידות שובך:

2 תגובות   (רסס)

  1. מאת נועה-אור גולדפינגר:

    תודה על הפוסט המרתק. :-)

  2. מאת יעלי_לה:

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

    זה נכון לא רק לחידות מתמטיות :-) בדיוק ככה אני מחברת הגדרות היגיון (כמו לתשבצי היגיון)

הוספת תגובה

(מומלץ להיכנס או )