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

amirbd · שליחה 09/12/2007 14:36

עומר (Booboo) פתר את חידת המספר בעל 10 הספרות
ואריה (osherov) פתר את חידת המטבעות

האמת - חשבתי ששתיהן יחזיקו יותר זמן מעמד...

Booboo · שליחה 09/12/2007 14:50

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

כדי לחדד את הנקודה, תניחו שהתהליך הוא זה -

אני בוחר 50 מטבעות כלשהן ונותן אותם למשה - משה (שאין לו אינטרס לעזור לאריה) קובע את סדר המטבעות, ואז המשחק מתחיל

(אח, אח איזה חידה חמודה, אני מה זה מרוצה מעצמי )
...

כמו שכתבתי לך בבוקר בדקתי על דף עם 4,6,8 ו-10 מטבעות, וזה אמפירי לחלוטין שאריה ינצח או לפחות ישתווה למשה עם כל מספר של מטבעות.
השאלה איך להוכיח את זה

amirbd · שליחה 09/12/2007 17:34

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

AviBiton · שליחה 09/12/2007 20:24

Booboo כתב:כמו שכתבתי לך בבוקר בדקתי על דף עם 4,6,8 ו-10 מטבעות, וזה אמפירי לחלוטין שאריה ינצח או לפחות ישתווה למשה עם כל מספר של מטבעות.
השאלה איך להוכיח את זה
...

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

osherov · שליחה 09/12/2007 22:40

קחו שאלה שאני יודע את התשובה בלי הוכחה:

שבעה אנשים עומדים בטור אחד אחרי השני.
לכל אחד יש מספר בעל ספרה אחת שונה מהשני
המכפלה של שלושת הראשונים שווה למכפלה של שלושת האמצעים שווה למכפלה של שלושת האחרונים בטור. מה המספר של האמצעי (הרביעי בטור) ?

תשובות בפרטי, בונוס לזה שגם יסביר את תשובותו

moco · שליחה 09/12/2007 22:43

המספרים בני ספרה אחת? הניסוח לא ברור.

osherov · שליחה 09/12/2007 23:19

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

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

)

theAman פתר את החידה וכרגע הוא מחפש את ההוכחה\הסבר לפתרון

osherov · שליחה 10/12/2007 7:29

גם אמיר וגם משה (בסדר הזה) פתרו את החידה כולל הוכחות פשוטות ויפות

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

amirbd · שליחה 10/12/2007 10:02

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

אריה, רגע, מה עם הבונוס - אני לא מקבל איזה פרס קטן, קפה, עוגה, משהו

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

AviBiton · שליחה 10/12/2007 10:10

אין לי כרגע חידות, אז ברשותכם אעביר את הזכות לאמיר שהיה הראשון לתת הוכחה.

ד"א - אני אשמח לראות את ההוכחה.

osherov · שליחה 10/12/2007 10:12

בקרוב...אני אפרסם את ההוכחה

amirbd · שליחה 10/12/2007 11:35

theAman כתב:אין לי כרגע חידות, אז ברשותכם אעביר את הזכות לאמיר שהיה הראשון לתת הוכחה.
ד"א - אני אשמח לראות את ההוכחה.
...

משה - הרבה זמן לא הבאת חידה...

moco · שליחה 10/12/2007 11:59

amirbd כתב:
theAman כתב:אין לי כרגע חידות, אז ברשותכם אעביר את הזכות לאמיר שהיה הראשון לתת הוכחה.
ד"א - אני אשמח לראות את ההוכחה.
...
משה - הרבה זמן לא הבאת חידה...
...

את הזמן שיש לי תפסת עם משחק המטבעות

AviBiton · שליחה 10/12/2007 12:21

טוב, כל עוד אין חידות, אני אתן חידה שמצאתי (יחסית לחידות שהיו כאן היא קלה):
10 מספרים (לאו דוקא שונים) בין 1 ל-10. שסכומם שווה למכפלתם.
מהם המספרים?

יש 2 פתרונות שאני מצאתי.

פתרונות לפרטי.

amirbd · שליחה 10/12/2007 12:45

הבהרה נוספת משחק המטבעות

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

moco · שליחה 10/12/2007 12:56

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

osherov · שליחה 10/12/2007 13:46

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

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

moco · שליחה 10/12/2007 14:12

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

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

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

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

osherov · שליחה 10/12/2007 15:09

אלגוריתם שלך כמדומני לא יעיל ובעל סיבוכיות של 2 בחזקת n

moco · שליחה 10/12/2007 15:16

osherov כתב:אלגוריתם שלך כמדומני לא יעיל ובעל סיבוכיות של 2 בחזקת n
...

אתה צודק (לגבי התיאור השני) אבל איך זה בדיוק קשור לנושא ?

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

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

Re: ועוד הבהרה לחידה

Re: ועוד הבהרה לחידה