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

חברים בפייסבוק
תמונה של יצחק
ד"ר יצחק קאופמן

בין משתמשי הפייסבוק ישנם "חברים" וישנם מי שאין ביניהם חברוּת ויכונו כאן "זרים".

(א) הוכיחו שבתוך קבוצה של 6 משתמשים יש תמיד 3 שהם חברים או 3 שהם זרים.

(ב) האם גם בתוך קבוצה של 5 משתמשים יש תמיד 3 שהם חברים או 3 שהם זרים?

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

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

פתרון: (א) נסמן את שישה אנשי הקבוצה באותיות א' עד ו' (איור 1).

באיורים הבאים קו מלא פירושו "חברוּת" וקו שבור פירושו "זרוּת". למעשה עלינו להוכיח שבחיבורים בין 6 האותיות יהיה תמיד משולש שמורכב מקווים מלאים בלבד, או משולש שמורכב מקווים שבורים בלבד.

נתבונן באדם המסומן א' (בחירה של אדם אחר לא תשנה שום טיעון בהמשך). יחסיו עם כל האחרים יסומנו על ידי 5 קווים שיצאו ממנו לכל אחד מהאחרים בקבוצה. האפשרויות עבור 5 הקווים הן:

0 קווים מלאים ו-5 קווים שבורים.

1 קווים מלאים ו-4 קווים שבורים.

2 קווים מלאים ו-3 קווים שבורים.

3 קווים מלאים ו-2 קווים שבורים.

4 קווים מלאים ו-1 קווים שבורים.

5 קווים מלאים ו-0 קווים שבורים.

משש השורות האחרונות ניתן להסיק שתמיד יוצאים מ-א' לפחות 3 קווים מלאים או לפחות 3 קווים שבורים.

נדון בנפרד במקרה שבו יוצאים מ-א' לפחות 3 קווים מלאים ובמקרה שבו יוצאים מ-א' לפחות 3 קווים שבורים.

מקרה 1: נניח שיוצאים מ-א' לפחות 3 קווים מלאים (איור 2), כלומר ב', ג' ו-ד' הם חברים של א'.

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

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

קיבלנו שבמקרה 1 יש תמיד משולש שמורכב מקווים מלאים בלבד או משולש שמורכב מקווים שבורים בלבד.

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

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

תת-מקרה 2ב': אם כל השלושה ב', ג' ו-ד' הם חברים, אזי המשולש ב-ג-ד מורכב מ-3 קווים מלאים.

הראינו שלא משנה מי הם חברים ומי הם זרים – בתוך קבוצה של 6 משתמשים תמיד תימצא קבוצה של 3 חברים או קבוצה של 3 זרים.

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

הערה:

חלק (א) של החידה הוא מקרה פרטי של משפט ידוע שניסח המתמטיקאי הבריטי פרנק רמזי (Frank Ramsey) ב-1930. משפט זה נקרא "משפט רמזי" והוא הוביל לפיתוח תחום שלם בקומבינטוריקה שנקרא תורת רמזי.

שיתוף ב facebook
Facebook
שיתוף ב twitter
Twitter
שיתוף ב linkedin
LinkedIn
שיתוף ב whatsapp
WhatsApp
שיתוף ב email
Email

3 תגובות

  1. ככל שהחידה קצרה יותר
    הסבר התרון ארוך יותר
    גיליתי את הנוסחה

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

  3. המרשים בחידה זה הפתרון המוסבר בצורה מדוקדקת. לא מכיר כאלה. כל הכבוד.

כתיבת תגובה

האימייל לא יוצג באתר.

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

עשוי לעניין אותך