חידה

[טיקטי]

חידה

בוקר טוב נתונה קבוצה של n אנשים, בה כל אחד יודע פיסת רכילות שונה החלפת מידע מתבצעת באמצעות טלפון המקשר שני אנשים בסוף השיחה כל אחד מהאנשים יודע את שתי פיסות המידע שכל אחד מהם ידע בנפרד לפני השיחה כך ששניהם יודעים את אותו הדבר מהו מספר השיחות המינימלי שיש לבצע כך שכל n האנשים ידעו את כל הרכילויות?

 

[צוף החיים]

../images/Emo4.gifניחוש...

מממ... יש סיכוי קלוש שהתשובה היא n-1 ???

 

[avivRT]

../images/Emo128.gif

אפשר בפחות...

 

[טיקטי]

התשובה בספר אומרת שזה

ביותר מ-n-1

 

[avivRT]

../images/Emo128.gif לעצמי

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

 

[טיקטי]

צודק

 

[1אברהם]

לדעתי אם רק איש אחד

אמור לקבל את כל המידע צריך בדיוק N-1 שיחות ( ולא logN )

 

[avivRT]

אפשר גם כך וגם כך

אם עושים logN שיחות אז בסוף שני אנשים מקבלים את כל המידע ולכן זו האפשרות העדיפה גם אם רוצים שאיש אחד יקבל את כל המידע (כי logN<N-1 בד"כ).

 

[mili999]

אבל

אי אפשר שאיש אחד יידע את הכל ב-LOGN שיחות, המינימום זה N-1.

 

[avivRT]

נכון, שוב ../images/Emo128.gif לעצמי

ואני עוזב את החידה הזאת

 

[שץ מקשת]

../images/Emo62.gif נסיון

אני חושב שזה (N/2* LOG(N כל חצי מהקבוצה מדברת עם החצי השני (N/2) ואח'כ בריקורסיה בכל חצי שוב מדברים חצי מהקבוצה עם חצי אחר כף LOGN פעמים..

 

[שץ מקשת]

כף=כך

 

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

אם אינני טועה, סיפרו לי על

בעיית התקשורת הזאת בערך לפני 30 שנה, אבל לא זכור לי שדֻבּר אז על פתרון ידוע...

 

[snogal]

אבל גם אין פתרון עדיין אפשר

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

 

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

כן, גם אני עומד בערך באותו מקום.

חוץ ממקרים פרטיים כמו 4 עבור 4 6 עבור 5 8 עבור 6 10 עבור 7 12 עבור 8

 

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

טוב, אז

החל מ-4 יש לי 2n-4. נניח שזה אפשרי עבור n מסויים. ניקח n+1 אנשים. הראשון והשני מחליפים מידע פעם אחת. הראשון יושב בצד. שאר n האנשים מחליפים מידע ביניהם 2n-4 פעם ויודעים הכל זה על זה, וגם על הראשון שהלך הצידה, כי השני סיפר עליו הכל. עכשיו התקשרות אחרונה: מישהו מתקשר אל הראשון ומספר לו הכל. סה"כ התקשרויות:

1 + (2n - 4) + 1 = 2(n+1) - 4​

 

[טיקטי]

שאלה:בהתחלה כתבת את התשובה

הנכונה ואז למטה בחישוב יצא לך תשובה אחרת 2n-2 למה הכוונה?

 

[snogal]

התשובה האחרת

היא התשובה עבור n+1 (ולכן הביטוי n+1 בסוגריים) ההנחה הייתה עבור n כלומר עבור n מספר ההתקשרויות המינמלי הוא 2n-4. ההוכחה היא עבור n+1 אנשים ואז צריך להוכיח שהנוסחה עדיין נכונה כלומר מספר ההתקשרויות הוא

4(n+1)-4​

וזה בדיוק מה שיצא לטלמון.

 

[snogal]

תיקון

שורה אחרונה

2(n+1)-4​

 

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

הערות.

1. אפשר בדרכים שונות להגיע ל-2n-4. למשל: 4 אנשים עומדים בצד. אחד מהם (זה לא עקרוני) מדבר עם כל n-4 האחרים. אח"כ הרביעיה מחליפה מידע ב-4 שיחות, אח"כ מעבירים את כל המידע ל-n-4 האחרים. 2. אינני יודע איך להוכיח (אם זה בכלל נכון), שאי אפשר לשפר את 2n-4. 3. הבעייה ששמעתי לפני 30 שנה אולי קשורה איכשהו לחידה הזאת, אבל כנראה היה שם עוד משהו. קשה לזכור אחרי 30 שנה...