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

נשלח בתאריך: 04 June 2006 בשעה 21:28 | IP רשוּם

מישהו יכול לעזור לי עם השאלה הזו (אני תקוע איתה)

תהי A קבוצה של 100 מספרים טבעיים כלשהם

הוכח שקיימת קבוצה חלקית לא-ריקה של A שסכום איבריה מתחלק ב-100

תודה

נשלח בתאריך: 06 June 2006 בשעה 19:30 | IP רשוּם

הקבוצה החלקית גם יכולה להיות כל הקבוצה A

אני כבר יומיים עם התרגיל הזה ללא הצלחה

נשלח בתאריך: 24 June 2006 בשעה 16:14 | IP רשוּם

ע"פ השאלה האיברים ב A חייבים להיות שונים (מכיוון שזוהי קבוצה.. ואם היית שם את כל האיברים בתור 3 לדוגמא.. אז הקבוצה הייתה בעצם A={3}

קבוצה בעלת איבר 1..

נשלח בתאריך: 04 July 2006 בשעה 00:01 | IP רשוּם

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

נשלח בתאריך: 20 July 2006 בשעה 02:56 | IP רשוּם

עקרון שובך היונים, במילים פשוטות, אומר שאם יש לך  10 שובכים ו-11 יונים אזי בהכרח קיים שובך שבו ישנם לפחות 2 יונים.

באופן פורמלי, לא קיימת פונקציה חד-חד-ערכית מקבוצה סופית(!) לתת קבוצה ממש של עצמה. (בקבוצות אינסופיות זה לא עובד..)

באופן יותר כללי, אם ישנה קבוצה A בעלת עוצמה n, וקבוצה B בעלת עוצמה m כאשר n ו-m מספרים טבעיים וכן n>m אזי לא קיימת פונקציה חד-חד-ערכית מ-A ל-B.

במקרה שלעייל A היא קבוצת היונים ו-B היא קבוצת השובכים ולפיכך חייבות להיות 2 יונים שמותאם להן אותו השובך.

בחידה שניתנה כאן סביר להניח שצריך להשתמש בשארית מודולו100 (השארית שנותרת לאחר חלוקה במאה) כלומר להתייחס רק לספרת העשרות והאחדות שכן מבחינת החידה אין הבדל בין 17 ל-4617, ולכן אפשר להתייחס אל A כאל מולטי-קבוצה (שבה מותרות חזרות) של 100 מספרים טבעיים בין 0 ל-99 (כולל 0 ו-99) לא בהכרח שונים!!!

החידה האמת נראית די פשוטה אבל אין לי כוח לחשוב עליה עכשיו (2:53 לפנות בוקר!!!) אבל מצד שני גם המשפט האחרון של פרמה נראה די פשוט במבט ראשון...

נשלח בתאריך: 02 July 2010 בשעה 03:38 | IP רשוּם

תהא קבוצת מספרים טבעיים: X1…X100 נחלק אותן לקבוצות A1…A100 כך ש:   

A1 = {X1}

A2 = {X1 , X2}

A3 = {X1 , X2 , X3}

…

A100= {X1 , X2 …. ,X100}

נסכום כל קבוצה ונחלק ב100 , אם קיימת קבוצה כך ששארית החלוקה שווה ל 0 אז סיימנו. מ.ש.ל

אם לא קיימת קבוצה כזאת, אז קיימות 100 קבוצות ו 99 אפשרויות לשארית (1-99) ומכאן שעל פי עקרון שובך יונים קיימות שתי קבוצות בעלות אותה שארית Ax  ו Ay . כך ש X > Y.

מכיוון ש Ax מכילה את Ay נוכל להסתכל על הקבוצה החלקית:

Ax – Ay = {Ay+1, Ay+2+…+Ax}

מכיוון ש:

Sum Ax – Sum Ay = (n*100) + a – ( (m * 100) + a) = (n-m) * 100

N וM מספרים טבעיים כך ש N > M ו A היא שארית החלוקה ב 100.

קבוצת המספרים החלקית מתחלקת ב100. מ.ש.ל