ואריה (osherov) פתר את חידת המטבעות
האמת - חשבתי ששתיהן יחזיקו יותר זמן מעמד...
שירשור החידות הגדול
- Booboo
-
- חבר ותיק
- תגובות: 1929
- הצטרף: דצמבר 2005
- מיקום: ראש העין
- נתן תודות: 23 פעמים
- קיבל תודות: 20 פעמים
Re: ועוד הבהרה לחידה
כמו שכתבתי לך בבוקר בדקתי על דף עם 4,6,8 ו-10 מטבעות, וזה אמפירי לחלוטין שאריה ינצח או לפחות ישתווה למשה עם כל מספר של מטבעות.amirbd כתב:ברור שעבור סדרים מסויימים של מטבעות לאריה יש עבודה קלה מאד, אך זה לא אריה שבוחר איך להניח את המטבעות.
כדי לחדד את הנקודה, תניחו שהתהליך הוא זה -
אני בוחר 50 מטבעות כלשהן ונותן אותם למשה - משה (שאין לו אינטרס לעזור לאריה) קובע את סדר המטבעות, ואז המשחק מתחיל
(אח, אח איזה חידה חמודה, אני מה זה מרוצה מעצמי)
...
השאלה איך להוכיח את זה
"When all are one and one is all, To be a rock and not to roll"
- AviBiton
-
- גורו HTmobile
- תגובות: 17346
- הצטרף: אפריל 2005
- מיקום: קרית שמונה
- נתן תודות: 503 פעמים
- קיבל תודות: 358 פעמים
Re: ועוד הבהרה לחידה
אני נמצא באותו מצב,לא יצא לי להתעמק בחידה מאז שכתבתי לאמיר, אבל קל מאוד לראות שאריה ינצח ובאמת השאלה היא איך להוכיח.Booboo כתב:כמו שכתבתי לך בבוקר בדקתי על דף עם 4,6,8 ו-10 מטבעות, וזה אמפירי לחלוטין שאריה ינצח או לפחות ישתווה למשה עם כל מספר של מטבעות.
השאלה איך להוכיח את זה...
קחו שאלה שאני יודע את התשובה בלי הוכחה:
שבעה אנשים עומדים בטור אחד אחרי השני.
לכל אחד יש מספר בעל ספרה אחת שונה מהשני
המכפלה של שלושת הראשונים שווה למכפלה של שלושת האמצעים שווה למכפלה של שלושת האחרונים בטור. מה המספר של האמצעי (הרביעי בטור) ?
תשובות בפרטי, בונוס לזה שגם יסביר את תשובותו
שבעה אנשים עומדים בטור אחד אחרי השני.
לכל אחד יש מספר בעל ספרה אחת שונה מהשני
המכפלה של שלושת הראשונים שווה למכפלה של שלושת האמצעים שווה למכפלה של שלושת האחרונים בטור. מה המספר של האמצעי (הרביעי בטור) ?
תשובות בפרטי, בונוס לזה שגם יסביר את תשובותו
כפי שנרשם המספרים הם הכן בעלי סיפרה אחת ושונים אחד מהשנילכל אחד יש מספר בעל ספרה אחת שונה מהשני...
(משה, כבר אמרתי לך פעם שהיית צריך ללכת להיות עורך-דין
)theAman פתר את החידה וכרגע הוא מחפש את ההוכחה\הסבר לפתרון
גם אמיר וגם משה (בסדר הזה) פתרו את החידה כולל הוכחות פשוטות ויפות 
מכיוון שלא חייבתי להביא גם הוכחה (זה היה בונוס)
אני מעביר את זכות השאלה ל theAman שפתר ראשון
מכיוון שלא חייבתי להביא גם הוכחה (זה היה בונוס)
אני מעביר את זכות השאלה ל theAman שפתר ראשון
אריה, רגע, מה עם הבונוס - אני לא מקבל איזה פרס קטן, קפה, עוגה, משהוosherov כתב:גם אמיר וגם משה (בסדר הזה) פתרו את החידה כולל הוכחות פשוטות ויפות
מכיוון שלא חייבתי להביא גם הוכחה (זה היה בונוס)
אני מעביר את זכות השאלה ל theAman שפתר ראשון...
(משה, לא, הזכות לתת עוד חידות זה לא נחשב פרס...)
אמיר.
- AviBiton
-
- גורו HTmobile
- תגובות: 17346
- הצטרף: אפריל 2005
- מיקום: קרית שמונה
- נתן תודות: 503 פעמים
- קיבל תודות: 358 פעמים
טוב, כל עוד אין חידות, אני אתן חידה שמצאתי (יחסית לחידות שהיו כאן היא קלה):
10 מספרים (לאו דוקא שונים) בין 1 ל-10. שסכומם שווה למכפלתם.
מהם המספרים?
יש 2 פתרונות שאני מצאתי.
פתרונות לפרטי.
10 מספרים (לאו דוקא שונים) בין 1 ל-10. שסכומם שווה למכפלתם.
מהם המספרים?
יש 2 פתרונות שאני מצאתי.
פתרונות לפרטי.
דווקא לא נשמע לי כזה פשוט למצוא אלגוריתם שממקסם את הרווחיםדווקא אלגוריתם שממקסם את רווחיו של אריה זה פשוט, להוכיח שזה מבטיח לאריה ניצחון זה כבר סיפור אחר...
משה מה האלגוריתם שחשבת עליו ?
תעשה dynamic programming מלמטה למעלה, כאשר בכל שלב אריה בוחן עבור אחת משתי הבחירות שלו מול אחת משתי התגובות של היריב את המקסימום שנקבע ממה שכבר חושב עבטר פחות מטבעות + הרווח/הפסד מזוג הצעדים.osherov כתב:דווקא לא נשמע לי כזה פשוט למצוא אלגוריתם שממקסם את הרווחיםדווקא אלגוריתם שממקסם את רווחיו של אריה זה פשוט, להוכיח שזה מבטיח לאריה ניצחון זה כבר סיפור אחר...
משה מה האלגוריתם שחשבת עליו ?...
אפשרות אחרת (בעצם תיאור של אותו דבר שתיארתי קודם) תפרוס את כל העץ (הבינארי במקרה זה) של כל אפשרויות המשחק. תבדוק במעין minmax מה המקסימום של אריה פר כל התגובות של היריב והטובות ליריב.
לסיכום: יש לנו פה משחק עם כל האינפורמציה גלויה ומספר סופי של צעדים, אז ניתן לבחון את כל האפשרויות מראש.
משה
אתה צודק (לגבי התיאור השני) אבל איך זה בדיוק קשור לנושא ?osherov כתב:אלגוריתם שלך כמדומני לא יעיל ובעל סיבוכיות של 2 בחזקת n...
אם הייתי מצליח להוכיח שאותו מסלול אופטימלי לאריה הוא גם עם רווח חיובי אז הייתי פותר את החידה, גם אם אריה צריך לחשב במשך 2 מיליארד שנה.
לצערי, לא הצלחתי, ודי עזבתי את זה.
משה
