שירשור החידות הגדול

[AviBiton]

רמז:

בואו נחשוב על חידה אחרת -

יש לכם רק מונה, ואני, כמו קודם, הולך להקריא רשימת שמות.

כעת המשימה שלכם היא להגיד לי בסוף רשימה, האם "משה" הוקרא רוב הפעמים.

...

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

[amirbd]

רמז:

בואו נחשוב על חידה אחרת -

יש לכם רק מונה, ואני, כמו קודם, הולך להקריא רשימת שמות.

כעת המשימה שלכם היא להגיד לי בסוף רשימה, האם "משה" הוקרא רוב הפעמים.

...

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

...

ראשית, אמרתי שזו חידה קשה
שנית, קשה לי לתת עוד רמז בלי לפתור את החידה

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

[AviBiton]

מבחינתי אין בעיה, מה אומר משה?

[moco]

חכה עוד קצת, אולי עליתי על משהו

[amirbd]

משה פתר את החידה

(ידעתי שאני צריך רק לאיים שאני אפרסם את הפתרון... )

[moco]

משה פתר את החידה

(ידעתי שאני צריך רק לאיים שאני אפרסם את הפתרון... )

...

זה באמת נכון. מתאמצים רק כשאין ברירה.

[osherov]

נמחק

[amirbd]

שימו לב שיש שם שמושמע רוב הפעמים - כלומר יותר פעמים הוא מושמע מאשר הפעמים שהוא לא מושמע.

...

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

בשם הראשון שיקרא אני יזכור את השם ויעלה את המונה באחד
במידה והשם הבא שיקרא הוא השם אותו אני זוכר אני שוב יקדם את המונה באחד
במידה והשם הוא שם של מישהו אחר אני יוריד את המונה באחד.
כך אני המשיך הלאה, כבל רגע נתון במידה והמונה הולך להיות שלילי (-1) אז אני יהפוך אותו ל 1 ויחליף את השם אותו אני זוכר בשם החדש !?

נשמע פשוט מידי ???

...

זה אכן הפתרון

[osherov]

בטעות רשמתי את הפיתרון לשרשור

אמיר,
אגב, אני חושב שלכולנו (חוץ ממך) מגיע
אחרי הרמזים שלך התשובה היא די מתבקשת

[amirbd]

נמחק

...

למה מחקת למעלה ?

[osherov]

נמחק

...

למה מחקת למעלה ?

...

כי בטעות שלחתי לשרשור

[moco]

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

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

[osherov]

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

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

...

בגלל שרוב השמות שנקראים הם של אדם אחד אז
הפתרון נראה לי די self explained וממש לא דורש הוכחה
אתה לא חושב ככה ?!

[moco]

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

[osherov]

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

...

נניח שהחידה הייתה מגדירה שיש סה"כ 2 שמות ואחד מהם מושמע יותר פעמים מהשני
במקרה זה הפתרון המדובר היה די ברור,
עכשיו אני טוען שהמקרה של חידה עם 2 שמות הוא מקרה קיצון (worst case) לחידה שאמיר שאל ולכן הפתרון בטח תקף לחידה של אמיר

[moco]

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

תראה, בסופו של דבר הפתרון נכון, לי הוא פשוט לא כל כך ברור מאליו.

[osherov]

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

תראה, בסופו של דבר הפתרון נכון, לי הוא פשוט לא כל כך ברור מאליו.

...

הכוונה שלי הייתה שאם תיקח את כל השמות שהם לא השם "המנצח" ותשנה את שמם לשם אחד ויחיד ואז תפעיל שוב את האלגוריתם, המונה שלך תמיד יהיה נמוך (יותר קרוב ל 0) או שווה מהמקרה שהיו לך יותר משני שמות

[AviBiton]

כך אני המשיך הלאה, כבל רגע נתון במידה והמונה הולך להיות שלילי (-1) אז אני יהפוך אותו ל 1 ויחליף את השם אותו אני זוכר בשם החדש !?

...

השורה הזו הייתה חסרה לי
מגיע לי אפילו יותר מהפטיש הזה על הראש.

[osherov]

בימים הטובים של השרשור השאלה הייתה נפתרת ב 21 דקות, מקסימום ב 21 שעות אבל בטח שלא ב 21 ימים (ועוד אחרי רמז)
נראה לי שאנחנו מזדקנים

[moco]

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

תראה, בסופו של דבר הפתרון נכון, לי הוא פשוט לא כל כך ברור מאליו.

...

הכוונה שלי הייתה שאם תיקח את כל השמות שהם לא השם "המנצח" ותשנה את שמם לשם אחד ויחיד ואז תפעיל שוב את האלגוריתם, המונה שלך תמיד יהיה נמוך (יותר קרוב ל 0) או שווה מהמקרה שהיו לך יותר משני שמות

...

זה פשוט לא נכון
נניח שאריה זה השם המנצח, ומשה ואבי הם עוד שמות. הסדרה מתחילה ב אבי, משה, אבי,משה,אבי,משה . כלומר המונה : 1,0,1,0,1,0,
תשנה לשם אחד המונה יהיה 1,2,3,4,5,6.

היתכן שעוד לא פתרת ?

אמיר כתב לי שפתרתי קצת מסובך, אבל בכל אופן, ההוכחה שלי מבוססת על רעיון אחר.