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

osherov · שליחה 24/06/2008 23:03

נמחק

moco · שליחה 24/06/2008 23:11

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

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

osherov · שליחה 24/06/2008 23:17

moco כתב:למה שלא תנסח את ההוכחה בצורה מסודרת.
ייתכן שאני פשוט לא מבין אותה.

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

האם הדוגמה שהבאתי על הדוגמה שלך לא שיכנע אותך ?

moco · שליחה 24/06/2008 23:28

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

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

amirbd · שליחה 26/06/2008 1:01

חברה - לדעתי החידה קשה (לפני הרמז), ובינונית אחריו, כל הכבוד לפותרים. המאמר שפרסם את האלגוריתם הזה [left]"Finding a majority among n votes"
[/left]התפרסם ב-journal of algorithms ב-1989, והמחברים הם M.J. Fisher and S.L. Salzberg.

אלגוריתם :

מונה מתחיל ב-0.

אם המונה=0, אני אזכור את השם הבא (במקום מי שאני זוכר עכשיו), ואעלה את המונה ל-1
אם המונה חיובי, נעלה אותו ב-1 אם השם הבא זהה לשם בזכרון, אחרת, נקטין את המונה ב-1 (אבל נשמור את אותו השם בזכרון).

בסוף הרשימה אני אכריז על השם בזכרון

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

moco · שליחה 26/06/2008 1:15

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

AviBiton · שליחה 01/07/2008 9:11

מה קורה עם חידה חדשה?

amirbd · שליחה 01/07/2008 14:02

theAman כתב:מה קורה עם חידה חדשה?
...

כן, משה, מה קוררררה?

moco · שליחה 01/07/2008 14:30

שאלה טובה. מה אתם אומרים שנתחיל למחזר חידות מתחילת השרשור?

המצב באמת קשה.

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

osherov · שליחה 01/07/2008 15:44

אמיר,
בנוסף מה אתה חושב על הצורה בה הצגתי את הפתרון (זה שמשה לא משתכנע ממנו)

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

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

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

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

לעומת:
אבי, אבי, אבי, אבי, אבי, אבי, אריה, אריה, אריה, אריה, אריה ,אריה ,אריה
1,2,3,4,5,6,5,4,3,2,1,0,1

moco · שליחה 06/07/2008 9:48

חידה חדשה!

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

AviBiton · שליחה 06/07/2008 10:04

moco כתב:חידה חדשה!

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

לא כ"כ הבנתי את השאלה...
יש סיכוי לאיזה הסבר עם שרטוט או משהו קצת יותר מפורט?

moco · שליחה 06/07/2008 11:05

תגיד מה חסר בהסבר המילולי ואנסה להבהיר.
צירפתי פה ציור שעשיתי ביד חופשית. הירוק זה המסלול בשתי ההחזרות הראשונות.
האדום זה סוף המסלול.

AviBiton · שליחה 06/07/2008 11:09

moco כתב:תגיד מה חסר בהסבר המילולי ואנסה להבהיר.
צירפתי פה ציור שעשיתי ביד חופשית. הירוק זה המסלול בשתי ההחזרות הראשונות.
האדום זה סוף המסלול.
...

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

moco · שליחה 04/08/2008 22:19

מה קורה ומי קורא פה?

AviBiton · שליחה 04/08/2008 23:30

שכחתי שיש חידה באויר

amirbd · שליחה 22/09/2008 3:54

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

אולי הגיע הזמן לאיזשהוא רמז?

AviBiton · שליחה 22/09/2008 8:05

amirbd כתב:משה - חשבתי קצת על חידת המשולש. לא קופצת לי שום תובנה (ואני עסוק מדי מכדי לכתוב תוכנית שתחשב את זה).

אולי הגיע הזמן לאיזשהוא רמז?
...

אמיר, מה קרה?
קצת קשה אז מוותרים?
החידה הזו רק חודשיים וחצי באויר וכבר אתה רוצה רמז?

חוץ מזה, מתי תחזור כבר לאיזור הזמן של ישראל?

moco · שליחה 22/09/2008 9:37

האמת, אני צריך לפתור את זה שוב כי שכחתי את התשובה

מה שחשוב פה זה התובנה שעושה את זה לפשוט. זו אותה תובנה שעובדת עם כל שאלה שקשורה להחזרות.
תחשוב על מראה.

amirbd · שליחה 22/09/2008 16:01

moco כתב:האמת, אני צריך לפתור את זה שוב כי שכחתי את התשובה

מה שחשוב פה זה התובנה שעושה את זה לפשוט. זו אותה תובנה שעובדת עם כל שאלה שקשורה להחזרות.
תחשוב על מראה.
...

פתרתי את החידה הארורה הזאת - לרשום את הפתרון פה או בפרטי?