JOKOPOST | עיתון המאמרים והבלוגים המוביל בישראל

facebook twitter linkedin

חידות חשיבה (21)

אולימפיאדת המתמטיקה

חידות חשיבה (21) ד"ר יצחק קאופמן
ינואר 04
19:30 2018

(1) הוחלט שמשלחת ישראל לאולימפיאדת המתמטיקה הבינלאומית תיבחר מתוך 100 תלמידי כיתות יב' בבית הספר הריאלי בחיפה. מארגני האולימפיאדה דורשים שכל מדינה תקבע את גודל המשלחת שלה באחת מ- 2 האפשרויות הבאות: (א) משלחת בת 14 תלמידים; (ב) משלחת שבה ההפרש בין מספרי הדרכונים של כל 2 תלמידים מתחלק ב- 7. מנהל בית הספר חייב להחליט מיידית באיזו מהאפשרויות לבחור מבלי שמספרי הדרכונים ידועים לו. באיזו אפשרות כדאי לו לבחור אם הוא מעוניין שהמשלחת תהיה גדולה ככל האפשר?

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

 

 

 

רמזים (אם אתם זקוקים להם):

(1) חשבו מה קורה כשממיינים 100 מספרים לקבוצות לפי השארית שמתקבלת כשמחלקים אותם ב- 7.

(2) בדקו מהו המספר המינימלי ומהו המספר המקסימלי של לחיצות ידיים שיכול להיות למשתתף כלשהו.

 

 

 

פתרון:

(1) למנהל בית הספר כדאי לבחור באפשרות ב'. הוא יכול להחליט על כך מבלי שיראה את מספרי הדרכונים כי בכל קבוצה של 100 מספרים ישנם לפחות 15 מספרים שההפרש בין כל 2 מהם מתחלק ב- 7. ניתן להוכיח זאת באופן הבא:

מחלקים את 100 המספרים ל- 7 קבוצות.

קבוצה 1: מספרים שמתחלקים ב- 7 עם שארית 1.

קבוצה 2: מספרים שמתחלקים ב- 7 עם שארית 2.

קבוצה 3: מספרים שמתחלקים ב- 7 עם שארית 3.

קבוצה 4: מספרים שמתחלקים ב- 7 עם שארית 4.

קבוצה 5: מספרים שמתחלקים ב- 7 עם שארית 5.

קבוצה 6: מספרים שמתחלקים ב- 7 עם שארית 6.

קבוצה 7: מספרים שמתחלקים ב- 7 בלי שארית.

כשמחלקים 100 מספרים ל- 7 קבוצות ברור שלפחות באחת הקבוצות יש לפחות 15 מספרים. כל 2 מספרים בקבוצה זו נותנים אותה שארית כשמחלקים אותם ב- 7 ולכן הפרשם מתחלק ב- 7. המסקנה היא, כאמור, שכדאי למנהל לבחור באפשרות ב' כי אז יהיו במשלחת לפחות 15 תלמידים.

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

 

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

על המחבר / המחברת

יצחק קאופמן

יצחק קאופמן

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

4 תגובות

  1. נטלי
    נטלי ינואר 05 2018, 11:47
    איך יודעים שהחידה קשה

    ההסבר של הפתרון הרבה יותר ארוך מהחידה

    השב לתגובה
    • גל
      גל ינואר 05 2018, 16:58
      לא נכון

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

      השב לתגובה
  2. גליה
    גליה ינואר 05 2018, 12:38
    רק בלי בושות בתחרות

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

    השב לתגובה
  3. מלכה נ.
    מלכה נ. ינואר 08 2018, 13:57
    אין לי משהו מיוחד להגיד

    אבל אני בהחלט נהנית מהחיגות

    השב לתגובה

כתוב תגובה

הוסף תגובה:

<

* אני מתחייב לפעול על פי תנאי השימוש באתר


התגובות יפורסמו לפי שיקול דעת העורך

כתבות נוספות

פוסטים אחרונים בהגיגים

יתר המאמרים במדור