שלום לכם,

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

נתונה רשימה של 9,788 מספרים שונים בין 1 ל-19,574. הוכיחו שברשימה הזו מצויים לפחות שני מספרים זרים זה לזה.

שיהיה לכם שבוע טוב,

סקובידו



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

6 תגובות

  • אבי

    הצעה להוכחה

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

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

    התבלבלת..

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

  • זיו

    ללא הוכחה

    המספרים הם 1 ו 19,574.

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

    מתחכם :)

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

  • רמי

    הוכחה

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

    יהא n מספר שלם חיובי.
    נסתכל על המספרים בין 1 ל 2n .
    טענה : בכל רשימה בעלת n+1 מספרים בין 1 ל 2n יש לפחות שני מספרים זרים זה לזה.
    הוכחת הטענה:
    הוכחה באינדוקציה.
    עבור n=2 המספרים הם : 1,2,3,4
    הרשימות האפשריות של 3 מספרים : 123,124,134,234
    אם מופיע המספר 1 אזי ברור כי הוא זר לכולם על פי ההגדרה.
    בקבוצה 234 , המספרים 3 ו 2 זרים. ולכן בסיס האינדוקציה הוכח.
    נניח כי עבור n מתקיימת הטענה ונוכיח עבור n+1 .
    כלומר יש להוכיח כי כל רשימה בעלת n+2 מספרים בין 1 ל 2n+2 יש לפחות שני מספרים זרים זה לזה.
    הוכחה:
    אם כל המספרים ברשימה קטנים מ 2n+1 , אזי על פי הנחת האינדוקציה, מספיק n+1 מספרים לקיום זוג זרים ולכן בודאי עבור n+2 מספרים.
    אחרת, אם אחד המספרים הוא 2n+1 אז יש בלעדיו n+1 מספרים הקטנים מ 2n+1 והנחת האינדוקציה תקפה לגביהם.
    אחרת, אם אחד המספרים הוא 2n+2 אז יש בלעדיו n+1 מספרים הקטנים מ 2n+1 והנחת האינדוקציה תקפה לגביהם.
    אחרת, אם שני המספרים 2n+1 וגם 2n+2 נמצאים, אז הם זרים זה לזה !!!!
    מש"ל.

    עבור n=9787 מתקבלת הוכחת החידה.

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

    יפה!

    ובעצם הטענה בפשטות היא שאם לוקחים n+1 מספרים בין 1 ל- 2n אז בטוח שיהיו ביניהם לפחות 2 מספרים סמוכים זה לזה- ומספרים סמוכים זרים זה לזה.