חידה חביבה

[Core]

חידה חביבה

ביער מסויים ישנם עצים. טענה: אם מספר העצים שביער גדול ממספר העלים שעל כל אחד מהם, אזי יש לפחות 2 עצים שבהם מספר העלים שווה. הוכיחו\הפריכו...

 

[yontanbn]

פתרון

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

 

[Deathatred]

הפתרון נכון רק בהנחה

שלא יכול להיות מצב שלעץ אין עלים.כלומר אנו מניחים שאין מצב שלעץ יש 0 עלים.

 

[yontanbn]

התייחסות לאפס...

קראתי את התגובה הנוספת של deathatred וכמובן, הוא צודק. בניסוח הנוכחי של החידה התשובה היא דווקא לא כי אף אחד לא אומר שלא יכול להיות עץ עם אפס עלים בשובכים שלי, השובך שבא לפני מס´ 1 זה שובך מספר 0, ואם השובך המקסימלי הוא שובך מספר 17, זה אומר שיש *18* שובכים... ואם יש 18 עצים זה מסתדר...

 

[Deathatred]

עקרון שובך היונים

אם ביער יש N עצים, לפי הנתון הראשון, לכל עץ יש מקסימום N-1 עלים. לפי עקרון שובך היונים, אם עלינו לחלק N עצמים ב N-1 תאים (כאשר כל עצם, בעצם עץ, הולך לתא שמספרו כמספר העלים עליו) אזי לפחות בתא אחד יהיו לפחות שני עצמים. כלומר, יהיו לפחות שני עצים שבהם מספר העלים שווה. חשוב מאוד: כל האמור לעיל נכון רק בהנחה שלכל עץ יש לפחות עלה אחד. אחרת, יש דוגמה נגדית: שני עצים, באחד עלה ובשני אין עלים בכלל.