חידת עכברים לבנים

[עריסטו]

חידת עכברים לבנים

יש קבוצה של ab+1 עכברים לבנים. הוכיחו: הקבוצה מכילה סידרה של a+1 עכברים שכל אחד מהם (חוץ מהראשון) הוא צאצא של העכבר הקודם בסידרה, או b+1 עכברים שאף אחד מהם אינו צאצא של אחר.

 

[יאיר של תמר]

זה רק אני??

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

 

[עריסטו]

הגדרת צאצא:

A נקרא צאצא של B אם A הוא בן של B או A הוא צאצא של בן של B. כלומא צאצא הוא בן, בן של בן, בן של בן של בן וכן הלאה.

 

[טלמון סילבר]

האם כל העכברים... זכרים?

האם לכל עכבר מקבוצה זו יכול להיות רק אב אחד?

 

[טלמון סילבר]

ניסיון (בהנחה שכך)

נניח שלא קיימת שרשרת צאצאוּת באורך a+1. ניקח את כל העכברים ה"מסופיים" (אלה שאין להם צאצאים בקבוצה). הכמות שלהם שווה x. אין ביניהם יחסי צאצאוּת. לכל אחד מהם יש מקסימום a-1 עכברים, שהוא מהווה צאצא שלהם (לעכברים ה"מסופיים" יכולים להיות אבות-סבים-וכו' משותפים, ולחלקם או לכולם יכולים להיות פחות מ- a-1). הכמות המקסימלית של עכברי הקבוצה כֻּלה היא (כשכלם מסיימים מחרוזות באורך a, וכל המחרוזות זרות):

(a - 1 + 1)x = ax​

מכאן: x>b.

 

[עריסטו]

../images/Emo127.gif

 

[עריסטו]

../images/Emo26.gifבעצם יש לי שאלה../images/Emo36.gif

האם הטענה אינה נכונה כאשר יכולים להיות לעכבר שני הורים בקבוצה

 

[טלמון סילבר]

אין לי מושג. אבל ההוכחה שהצעתי

אינה עוברת במקרה זה. נעשה ניסיון כזה. נעמיד בשורה הראשונה את כל העכברים ה"שורשיים" - אלה שאינם מהווים צאצאים של מישהו מהקבוצה. נעמיד בשורה השנייה את כל הצאצאים הישירים של עכברי השורה הראשונה, כלומר את אלה, שאין בקבוצה אף אחד מהשושלת העומד בינם לבין עכברי השורה הראשונה. בשורה השלישית נעמיד את צאציהם הישירים של עכברי השורה השנייה, וכו'. אם נסכים שיכולים להיות לעכבר מספר אבות-סבים-וכו' מהקבוצה, אבל נטיל הגבלה אחרת: אין אף עכבר המתאים למספר שורות שונות(!), אזי באף שורה לא יהיו שני עכברים שאחד מהם הוא צאצא של השני. תחת הגבלה זו, אם נניח שמספר השורות שווה m, והגודל המקסימלי של שורה שווה n, אז:

mn > ab :וחייב להתקיים לפחות אחד מן השניים m > a ,לפחות a+1 ובמקרה זה יש שושלת באורך n > b ."עכברים "מנותקים b+1 ובמקרה זה יש לפחות​

 

[mor48]

שאלה

נניח יש אב אחד ושאר העכברים הם בניו. כל עכבר למעט האב יש לו אב. (לא מתאים ל B+1) איך תסדר אותם בסדרה כך שכל אחד קודמו הוא אביו?

 

[עריסטו]

התכוונת לשרשר לטלמון?

 

[טלמון סילבר]

תגובה

"נניח יש אב אחד ושאר העכברים הם בניו". "כל עכבר למעט האב יש לו אב". "(לא מתאים ל B+1)" - לא הבנתי. מה שווה A, ומה שווה B? "איך תסדר אותם בסדרה כך שכל אחד קודמו הוא אביו? " - את מי "אותם"? נניח שיש אב אחד ויש לו n בנים. סה"כ n+1 עכברים. יש לנו קבוצה של n עכברים "מנותקים", ויש לנו שושלות באורך 2. מה השאלה? אם n=ab, אז מתקיים אחד התנאים: או a = 1 או b < n

 

[mor48]

הבנתי את הטעות שלי בניסוח

או b+1 עכברים שאף אחד מהם אינו צאצא של אחר. חשבתי שאף אחד מהם אין לו אב בכלל ה ab+1 עכברים עכשיו אני רואה שעריסטו התכוון שיש קבוצה שבה אין שניים שאחד הוא צאצא של השני.

 

[מספר6]

זהירות ספוילר!

למעשה, מדובר במשפט ידוע מתורת הקבוצות. יכולים להיות גם מיליון הורים.

 

[טלמון סילבר]

../images/Emo35.gif נתת לי רעיון מצוין לחידה../images/Emo70.gif

חידה: נסו למצוא חידה שאינה "משפט ידוע"! או שאי-אפשר למצוא לה פתרון באינטרנט

 

[ףרמיוםFm]

מה יש לי בכיס?

 

[טלמון סילבר]

אולי, צריך לבדוק. וזה

הזכיר לי חידה אחרת, באמת מוכרת: מה יש הרבה בכיס ריק?

 

[ףרמיוםFm]

בהנחה שהתשובה היא מה שאני חושב שהיא

הניסוח קצת בעייתי

 

[טלמון סילבר]

ספר על מה אתה חושב,

ואיך צריך לתקן את הניסוח.

 

[ףרמיוםFm]

אוקיי

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

 

[טלמון סילבר]

לא, התכוונתי למשהו אחר!

וניחוש שגוי כמובן אינו הופך אף אחד ל"אידיוט"