שלום לכם,

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

בר-מוח הכין תרגיל משותף. הוא לקח מאה מנורות, נתן לכל אחת מהן מספר, והצמיד מספר גם לכל אחד מהגמדים מאחד ועד מאה. כל גמד בתורו יתבקש לחשב אלו מספרים מחלק המספר שקיבל ולשנות את מצב המנורה המתאימה. לדוגמה, הגמד שמספרו 22 ידליק או יכבה את המנורות שמספריהן הם 22, 44, 66 ו-88. בתחילת התרגיל כל המנורות תהיינה דלוקות.

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

"תצטרך לחשב המון כדי לדעת לאיזו תוצאה לצפות!" כתבתי לו בחזרה.

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

הרהרתי קצת, הבנתי שהוא צודק ומצאתי את הפתרון.

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

אילוסטרציה: Shutterstock

סקובידו


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

24 תגובות

  • עטרה

    חידת הרחבה 4

    חידה על בסיס החידה המתוקנת:
    בסוף המשימה הסתכל בר-מוח על הנורות הדלוקות, ולהפתעתו דלקו רק הנורות שהאינדקסים שלהן הם מספרים ראשוניים, כלומר, 2,3,5,7,11, וכו'.
    התברר כי חלק מהגמדים חמדו לצון ושינו את מספריהם (ונשארו בתחום בין 1 ל 100).
    איזה אוסף של 100 מספרים בין 1 ל 100 יגרום, על פי חוקי החידה, להדלקת הנורות הנ"ל בלבד?

  • רמי

    חידת הרחבה 3

    על בסיס החידה המתוקנת (בה גם כל הנורות תקינות):
    בסוף המשימה הסתכל בר-מוח על הנורות הדלוקות ולהפתעתו רק הנורות 1,2,3,5,8,13,21,34,55, ו 89 דלקו.
    התברר כי כמה מ 100 הגמדים חמדו לצון ושינו את מספריהם (ונשארו בתחום בין 1 ל 100).
    איזה אוסף של 100 מספרים בין 1 ל 100 , יגרום, על פי חוקי חידה, להדלקת הנורות הנ"ל בלבד?
    (*) יתכנו מספר תשובות

  • עטרה

    לא פתרתי

    לא היה לי זמן למחשב אז לא פתרתי בינתיים.
    אפשר רמז?

  • רמי

    רמז

    אפשר ליצור תהליך לכיבוי והדלקת הנורות.
    ניקח לדוגמא כמצב התחלתי את פתרון החידה (הכול דלוק למעט המרובעים).
    בפרט נורות 99 ו 98 דלוקות. היות ושתיהן צריכות להיות כבויות בסוף התהליך, ניתן לגמד 99 את המספר 98, גמד 98 נשאר עם מספרו.
    כעת גם נורה 99 וגם נורה 98 כבויות.

  • עטרה

    תשובה

    ל 58 גמדים יש את המספרים הבאים:
    {4, 6, 7, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 28, 29, 31, 34, 37, 39, 40, 41, 43, 44, 45, 47, 48, 50, 52, 53, 55, 56, 59, 60, 61, 65, 66, 67, 70, 71, 73, 75, 76, 77, 79, 80, 83, 84, 88, 90, 92, 97, 99}
    ל 42 הגמדים האחרים יש מספרים שרירותיים כלשהם, כאשר כל מספר שרירותי כזה מופיע אצל מספר זוגי של גמדים מתוך 42 הגמדים. (אם המספר השרירותי מופיע גם אצל גמד מהקבוצה של 58 הגמדים, אז בסך הכל המספר מופיע אצל מספר אי-זוגי של גמדים.)

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

  • רמי

    פתרון נכון

    גם הפתרון שלי דומה לפתרון זה.

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

  • רמי

    חידת הרחבה 2

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

  • עטרה

    תשובה

    לפי הנתונים של החידה, אם יש ל N מספר אי זוגי של מחלקים, אז הנורה N כבויה בסוף התרגיל.
    בנוסף, לפי הנתונים של חידת ההרחבה, אם מספר המחלקים של N הוא 6 או יותר, אז הנורה N שרופה בסוף התרגיל.
    לא קיים מספרים עם 0 מחלקים.
    לכן, אם נורה N דולקת בסוף התרגיל, אז מספר המחלקים של N הוא 2 או 4.
    לכן, N=p*q או N=p^2 או N=p^4, כאשר p,q הם מספרים ראשוניים.

  • רמי

    הערה

    היות וכל הנורות דלוקות בתחילת התרגיל, נשארה להן הדלקה אחת בלבד (לאחר הכיבוי שלהן) בהמשך.
    כלומר אם מספר המחלקים של N הוא 3 או יותר, אז הנורה N לא תהיה דלוקה בסוף התרגיל.

  • שי

    תיקון טעות

    נורות 4 ו-9 נדלקות פעמיים ולא שלוש כפי שחשבתי... אז הנורות שיישארו דלוקות הן ריבועי המספרים הראשוניים (אין עוד מחלקים אחרים שיכבו וידליקו וישרפו את הנורות האלו): 1, 4, 9, 25, 49.

  • רמי

    נורה 4 תשאר כבויה

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

  • שי

    נראה לי ש-

    רק נורה 1 שנדלקת פעם אחת וזהו. נורה 4 נדלקת 3 פעמים ונשרפת, כך גם נורה 9, על אחת כמה וכמה נורה 16, נורה 25 תשרף בדרכן של 4 ו-9, וכן הלאה.

  • שי

    האם ביקרת בכפר הדרדסים או בכפר הגמדים? :) בכל מקרה:

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

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

    https://www.dropbox.com/s/5nar4ujn0nm5xgg/state.txt

  • רמי

    דיבוג הקוד של השאלה הראשונה

    נראה לי כי צריך להחליף i ב j :
    במקום השורה :
    ;[lamp [i-1]=!lamp [i-1
    צ"ל:
    ;[lamp [j-1]=!lamp [j-1
    ואתה אמור לקבל את רשימת המנורות הכבויות.

    הקוד בתוכנית השניה נראה לי בסדר.

  • שי

    לשם השוואה, הנה תוכנית מחשב שמציגה את החידה המעודכנת

    שתי התוכניות מציגות כפלט את אותה תשובה, השאלה היא למה... (גם התוכנית הזו נכתבה בשפת JAVA)
    https://www.dropbox.com/s/xue21de3fflmwya/compare.txt

  • רמי

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

    1) פתרון החידה המקורית (הטעות). [חידה טובה בכל מובן]:
    מנורה שמספרה i תיהיה דלוקה אם"ם floor(100/i))mod(2)=0), כלומר, אם החלק השלם של חלוקת 100 ב i הוא זוגי, אזי המנורה i תדלוק.
    מספרי המנורות שידלקו :
    1,2,5,6,7,8,10,12,15,16,21,22,23,24,25,34,35,36,37,
    38,39,40,41,42,43,44,45,46,47,48,49,50

    2) פתרון החידה החדשה/המתוקנת:
    המנורות i^2 עבור i בקבוצה {1,2,3,4,5,6,7,8,9,10} תיהינה כבויות. שאר הנורות תדלוקנה.
    מספר אי זוגי של מחלקים גורם לכיבוי, המחלקים באים בזוגות למעט במספר ריבועי שם סופרים את השורש/גורם פעם אחת.

  • יוסף

    תשובה פשוטה ביותר והסבר (והסבר הטעות של השאר בשאלה..)

    שטותים והבלים לא הבנת נכון מאה לא תטופל ע"י 2 וכו' אלא רק ע"י מאה הוכחה לכך :כותב החידה היה צריך לומר שגמד מספר 12 מטפל גם ב 24 או 48 מכאן הוכחה לטיפשותך/כם והתשובה : שבר מוח יסתובב בכל המנורות שיחלק את מספר הגמדים במספר המנורה למשל מנורה מספר 58 כמה פעמים נכנס מאה ב58 רק פעם אחת ומפני זה מנורה 58 תהיה כבויה מפני שהפעמים שהוא נכנס במאה הוא אי זוגי (1) ואל תטעה שוב ותאמר ש 58 תטופל בידי 2 כי כבר הסברתי טעותך בנל וכך גם תהיה החוקיות בכולם .(נסו למשל 3 נכנס במאה 33 פעמים ובגלל שהתוצאה אי זוגית הנורה תהיה כבויה או למשל 48 נכנס בשתיים פעמיים ובגלל ששתיים זוגי הנורה תהיה דלוקה(היא תכבה ע"י 48 ותדלק ע"י 96 או להפך תלוי מי יגיע ראשון))ומדוע ?פשוט וקל מחלקים X במאה ורואים כמה גמדים "טפלו" במנורה אם התוצאה זוגית יהיה דלוק ואם אי זוגי יהיה כבוי. 1 דלוק 2 דלוק 3 כבוי 4 כבוי 5 דלוק וכו' דרך צלחה מקוה שעזרתי ...

  • תום

    איזה מירמור למה להשתמש במילים כאלו?

    לפני שאתה צווח ומכנה אנשים כטיפשים עדיף שתספור עד 10

  • מומחה מצוות מכון דוידסוןפזיה

    התנצלות. הייתה טעות בחידה.

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

  • אחיה

    פתרון

    המספרים המרובעים ידלקו 1,4,9,16,25,36,49,64,81,100

  • רמי

    ומה עם נורה 2 ?

    כל 50 הגמדים שמספריהם זוגיים ידליקו/יכבו נורה 2.
    היות ובתחילה נורה 2 היתה דלוקה, בהרי גם בסוף התהליך תמשיך לדלוק!! (50 זוגי => (כיבוי+הדלקה) כפול 25).
    כמו כן נורה 100 תטופל רק ע"י גמד 100, ולכן לאחר שיכבה אותה, היא תשאר כבויה.

  • תום

    כנראה שלא הבנת את החידה

    נורה 100 תטופל ע"י גמד 1,2,5,10,20 וכו'
    כל המחלקים של 100 יטפלו בנורה 100
    לכל מספר שיש לו ריבוע יש לו מספר מחלקים אי זוגיים
    ויוצא מכן שלמשל נורה מספר 4 המחלקים שלה 1,2,4
    הראשון ידליק השני יכבה והרביעי ידליק ואז המצב נשאר כמות שהוא.
    בחידה הנ"ל התוצאה הפוכה כיון שהדרישה היא שהנורות דולקות בהתחלה אז יוצא מכך שהראשון כיבה השני הדליק והרביעי כיבה.

  • רמי

    מחלקים של המספר של הגמד ולא של הנורה

    בחידה זו מדובר במחלקים של המספר של הגמד.
    על פי הדוגמא בחידה גמד 12 ידליק/יכבה את המנורות שמספריהן הם 1, 2, 3, 4, 6 ו-12.
    אזי :
    גמד 2 ידליק/יכבה את המנורות שמספריהן הם 1, ו-2.
    גמד 4 ידליק/יכבה את המנורות שמספריהן הם 1, 2, ו-4.
    גמד 6 ידליק/יכבה את המנורות שמספריהן הם 1, 2, 3 ו-6.
    :
    גמד 34 ידליק/יכבה את המנורות שמספריהן הם 1, 2, ו-17.
    :
    גמד 100 ידליק/יכבה את המנורות שמספריהן הם 1, 2, 4, 5, 10, 20, 25, 50 ו-100.

  • מומחה מצוות מכון דוידסוןפזיה

    התנצלות- הייתה טעות בחידה

    והיא תוקנה עכשיו.