עקרון שובך היונים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ r2.7.2+) (בוט מוסיף: vi:Nguyên lý ngăn kéo Dirichlet |
Delbarital (שיחה | תרומות) מאין תקציר עריכה |
||
שורה 18:
*נניח כי נערכת מסיבה עם כמות כלשהי של מוזמנים. כל אורח לוחץ ידיים פעם אחת לכל אחד ממכריו במסיבה (ייתכן שאורח ילחץ ידיים לחלק, לכל או לאף אחד מהאורחים האחרים). בהכרח יש שני אורחים שלחצו אותו מספר של ידיים. הוכחה: נניח כי במסיבה יש <math>n</math> אורחים. מספר הידיים שכל אורח לוחץ הוא בין 0 ל-<math>n-1</math> (שכן הוא לא לוחץ ידיים לעצמו). כלומר לאורח יש <math>n</math> אפשרויות שונות למספר הלחיצות. כדי שלא יהיו שני אורחים מבין <math>n</math> האורחים שלחצו אותו מספר של ידיים, בהכרח יש אורח שלחץ 0 ידיים, אורח שלחץ יד אחת, וכן הלאה עד לאורח שלחץ <math>n-1</math> ידיים. אבל מצב זה אינו ייתכן שכן האורח שלחץ <math>n-1</math> ידיים בהכרח לחץ את ידייהם של כל שאר האורחים, ולכן לא ייתכן שיהיה אדם שלחץ 0 ידיים. מכאן שיש שני אנשים שלחצו אותו מספר של ידיים.
*בכל תת-קבוצה של <math>\ n+1</math> ערכים מתוך הקבוצה <math>\ \left\{1,2,\dots,2n\right\}</math> יש שני ערכים כך שאחד מהם מחלק את השני. כדי לראות זאת, ניתן לכתוב כל מספר בקבוצה בצורה <math>\ 2^k m</math> כש-<math>\ m</math> הוא אי זוגי וקטן מ-<math>\ 2n</math> (<math>\ m</math> מתקבל פשוט על ידי חלוקה חוזרת ונשנית של המספר ב-2 עד שמתקבל ערך אי זוגי). יש רק n מספרים אי-זוגיים בין 1 ל-2n ולכן יש בקבוצה שני ערכים בעלי אותו חלק אי-זוגי m - ואחד מהם (זה שהחזקה של 2 עבורו היא קטנה יותר) בהכרח מחלק את השני.
*
==הוכחת העקרון==
|