ABA


"חידה קטנה, באדיבות liranr"
גירסת הדפסה        
קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #6785 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 6785
dryice

   16:41   18.08.03   
אל הפורום  
  חידה קטנה, באדיבות liranr  
 
   ערכתי לאחרונה בתאריך 21.08.03 בשעה 18:06 בברכה, dryice
 
נסיך סעודי עם קצת הרבה כסף על הידיים, נוחת אצלך בסלון,
לאחר שניסית לעניין אותו במשחק פוקר בשביל לקחת ממנו קצת כסף
ללא הצלחה, הוא מציע לשחק במשחק הבא:
הנסיך יניח N מטבעות זהב על השולחן, כל שחקן בתורו מוציא 1
עד 3 מטבעות ושם בצד, מי שלוקח המטבע האחרון זוכה.
הנסיך מהמר על מטבעות הזהב, אתה מהמר על האוטו(ששווה קצת פחות,
נו בכל זאת הוא הנסיך)
הנסיך משום שהוא בחר את המשחק, מסדר המטבעות ונותן לך להחליט
מי יתחיל, במה תבחר?

DRYICE


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

  האשכול     מחבר     תאריך כתיבה     מספר  
  אומנם הרעיון שלי liranr 18.08.03 17:08 1
     אתן לו להתחיל ואשלים במידת הצורך לשלוש. MadXP 18.08.03 20:15 2
         אתה מתחמם, אבל זה לא ממש זה liranr 18.08.03 20:37 3
             אז נעבוד בקבוצות של 4 szargel 18.08.03 21:21 4
                 השאלה מוכרת ... :) codmaster 18.08.03 23:41 5
                     נכון מאוד :-) :-) liranr 19.08.03 07:44 6
                         לא משנה , אל תתאכזב codmaster 19.08.03 08:28 7
                         היה משחק מחשב כזה לפני 20 שנה שנקרא גפרורים no1 19.08.03 08:36 8
                             כשהייתי בכתה ד' פיצחתי את השיטה! Back Ofirus 24.08.03 21:00 12
  הרחבה blarg 23.08.03 22:49 9
     בדיוק אותה חוקיות szargel 24.08.03 01:21 10
         אני חושש שלא הבנת נכון. dryice 24.08.03 14:08 11
             יכול להיות שלא הבנתי נכון szargel 25.08.03 07:00 13
  משחק מוכר גם לא מהשרדות chatter  29.08.03 18:46 14

       
liranr

   17:08   18.08.03   
אל הפורום  
  1. אומנם הרעיון שלי  
בתגובה להודעה מספר 0
 
   אבל העלילה של הנסיך הסעודי חדשה לי לחלוטין - החידה שלי הייתה הרבה
יותר "אפורה". מאיפה המצאת את הסיפור?
בכל אופן - בהצלחה לכולם.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MadXP

   20:15   18.08.03   
אל הפורום  
  2. אתן לו להתחיל ואשלים במידת הצורך לשלוש.  
בתגובה להודעה מספר 1
 
   כלומר אם לדוגמא יש 6 מטבעות והוא הוציא 1 אז אני יוציא 2
זה הרעיון בכללי
כשאגיע ל -3 האחרונים
אז אוציא 1....כך שלא תהיה לו ברירה.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
liranr

   20:37   18.08.03   
אל הפורום  
  3. אתה מתחמם, אבל זה לא ממש זה  
בתגובה להודעה מספר 2
 
   דבר ראשון מה תעשה אם הוא יוציא 3 מטבעות? תוציא 0?
דבר שני לפי האסטרטגיה שלך ב-3 יהיה תורו, ולא תורך, ואז הוא יוציא 3
וינצח.
דבר שלישי, מי אמר ש-N מתחלק ב-3?

אבל סך הכל אתה בדרך הנכונה, תמשיך לעבוד על זה


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
szargel

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
codmaster

   23:41   18.08.03   
אל הפורום  
  5. השאלה מוכרת ... :)  
בתגובה להודעה מספר 4
 
   ערכתי לאחרונה בתאריך 18.08.03 בשעה 23:54 בברכה, codmaster
 
היא הופיעה באחת התכניות של הישרדות (כן היא עדיין קיימת)
הפתרון מאוד חביב , אבל אני לא אענה ...(אלא אם כן אתם רוצים שאענה...)


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
liranr

   07:44   19.08.03   
אל הפורום  
  6. נכון מאוד :-) :-)  
בתגובה להודעה מספר 5
 
   משם נזכרתי בחידה ונתתי ל-dryice את הרעיון (את העיבוד לנסיך סעודי
הוא עשה בעצמו)

ול-szargel , נכון מאוד
רק כדי להשלים את התמונה (וזה די ברור), מה תעשה עם N מתחלק ב-4?

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
codmaster

   08:28   19.08.03   
אל הפורום  
  7. לא משנה , אל תתאכזב  
בתגובה להודעה מספר 6
 
   יישר כח , חידות כאלו מבורכות כאן בפורום.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
no1

   08:36   19.08.03   
אל הפורום  
  8. היה משחק מחשב כזה לפני 20 שנה שנקרא גפרורים  
בתגובה להודעה מספר 6
 
   אני יודע שלא נולדת אז
בכל מקרה הרעיון שלו היה זהה .


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Back Ofirus

   21:00   24.08.03   
אל הפורום  
  12. כשהייתי בכתה ד' פיצחתי את השיטה!  
בתגובה להודעה מספר 8
 
   שיעורי המחשב החופשיים היו המהנים ביותר בתקופה הזו :-))


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
blarg

   22:49   23.08.03   
אל הפורום  
  9. הרחבה  
בתגובה להודעה מספר 0
 
   שאלה מעניינת בהקשר לחידה: מה יקרה אם יש מגבלות אחרות על מספר המטבעות שאפשר לקחת? נניח מטבע אחד, שלושה מטבעות או ארבעה מטבעות. מה החוקיות אז?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
szargel

   01:21   24.08.03   
אל הפורום  
  10. בדיוק אותה חוקיות  
בתגובה להודעה מספר 9
 
   ערכתי לאחרונה בתאריך 24.08.03 בשעה 01:22 בברכה, szargel
 
לגבי מטבע 1 - ברור שהחידה לא יכולה להתקיים במצב כזה.
לגבי 2 מטבעות ומעלה החוקיות היא אותה חוקיות, נסמן בx את מספר המטבעות המקסימלי שאפשר לקחת בכל תור + 1, בa יהיה איזה שהוא מכפיל, וn יהיה מספר המטבעות שנשאר שלא מתחלק בx
יש לנו xa+n מטבעות, בתור הראשון ניקח n מטבעות, מה שישאיר לנו ax מטבעות.
בכל תור אחר, בהתאם למה שהנסיך יקח, ניקח x פחות מספר המטבעות שהוא לקח, ע"מ שבתור הבא שוב יהיה לנו ax מטבעות.
בתור האחרון - ישארו x מטבעות ויהיה תורו של הנסיך, מכיוון שהמספר המקסימלי של מטבעות שהוא יכול לקחת הוא x-1, הוא יפסיד.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
dryice

   14:08   24.08.03   
אל הפורום  
  11. אני חושש שלא הבנת נכון.  
בתגובה להודעה מספר 10
 
   הוא שאל מה יקרה אם אפשר לקחת בכל סיבוב 1,3 או 4 אבל
אי אפשר לקחת 2.

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

במקרה הנדון, 1,3,4 הניתוח הוא כזה:
אנו נרצה שבסוף בתורו של היריב יהיו 2 מטבעות בשביל שהוא
לא יוכל לנצח ואנו כן ננצח.
נרצה איפה שלמור על השמורה לגבי מספר המטבעות בתחילת תור היריב,
אבל זה לא כל-כך פשוט, אם בתור לפני כן יש לו 3 או 4, הוא מנצח,
אם לפני כן יש בתור של היריב5,6 הוא מנצח(לוקח 3,4). אם היו לו 7
הוא מפסיד. 8 הוא מנצח, 9 מפסיד. 10 מנצח. 11 מנצח.
12 מנצח,13 מנצח,14 מפסיד,15 מנצח.16 מפסיד.
נשים לב לנקודות ההפסד של היריב:
2,7,9,14,16
הסידרה היא בקפיצות של 5 ואז 2, וזה גם קל להסביר.
הבניה הרקורסיבית היא כזאת:
אם מנקודה אפשר להגיע לנקודת הפסד היא נקודת נצחון,
אם אפשר להגיע רק לנקודות נצחון בצעד בודד, זאת נקודת הפסד.

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

אנו יכולים לעשות אקסטרפולציה זריזה:
2,7,9,14,16,21,23,28,30
המחזוריות היא של 7, אם N mod 7=2,0 הפסדנו.
על כן אם מספר המטבעות ההתחלתיים היינו K mod 7=2,0 אנו נבחר
להיות שניים, אחרת נבחר להתחיל.

DRYICE


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
szargel

   07:00   25.08.03   
אל הפורום  
  13. יכול להיות שלא הבנתי נכון  
בתגובה להודעה מספר 11
 
   ועל זה כבר נאמר
...לנסח את השאלה נכון - זה אפילו יותר חשוב מהתשובה....

בכל אופן - תודה על ההרחבה.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
chatter 
חבר מתאריך 18.3.02
5472 הודעות
   18:46   29.08.03   
אל הפורום  
  14. משחק מוכר גם לא מהשרדות  
בתגובה להודעה מספר 0
 
   כמו שאמרו עם הגפרורים. הייתי משחק בזה עם אבא שלי


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

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net