PDA

צפה בגרסה המלאה : חידה נחמדה.



Adi
12-08-2008, 15:29
מלך רוצה למצוא חתן לביתו הנסיכה , לשם כך הוא מפרסם הודעה בכל רחבי הממלכה..
להפתעתו מגיעים כ 10,000 אנשים ואין מושג איך לבחור מבינהם.
המלך מוצא פיתרון ומחליט לסדר את כל ה 10,000 במעגל [כל אחד במקום שלו בהתאמה] להרוג אחד כן אחד לא עד שישאר האחד שיתאים.
הכוונה שלי היא נגיד היו באים רק 10 אנשים אז
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10
אחד חי , שני מת , שלישי חי , רביעי מת , חמישי חי , שישי מת , שביעי חי , שמיני מת , תשיעי חי , עשירי מת
הלאה , נשארו האנשים 1,3,5,7,9
אחד חי שלישי מת , חמישי חי , שביעי מת, תשיעי חי
נשארו 1,5,7 והלאה עד שישאר היחידי.
הכוונה היא ברורה , אחד חי אחד מת רק כשיש 10000 אנשים.
החידה בעצם היא איזה מקום יישאר אחרון [כוונה יותר ברורה - איזה איש ייזכה בנסיכה]

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

sivan1233210
12-08-2008, 16:06
לפי דעתי 1.
כי לפי הדוגמא שאתה נתת אם תשים לב תמיד האחד נשאר אז נראלי זה לא כ"כ משנה כמה אנשים יש. כל עוד אתה מתחיל שהראשון חי אז מספר 1 ישאר החי.
אני לא בטוחה בתשובה. זה רק מה שנראה לי הגיוני.
מעניין אותי איך הגעת ל - 4979 (כי אם אני אומרת 1 ואתה 4979 אז נראלי שאני לא הבנתי את החידה).

sivan1233210
12-08-2008, 17:15
בכל אופן, תשאל אם זאת התשובה.

עשהאל
12-08-2008, 17:43
בס"ד

לא ברור אם הכוונה היא שכשמסיימים לעבור על כל האנשים, מתחילים שוב מ-1, והוא חי, או שממשיכים במעגל (ויכול להיות ש-1 ימות).
לפי האפשרות הראשונה, זה 1. לפי האפשרות השנייה, זה מספר אחר (אבל ברור שזה לא 4979, כי הוא ייהרג בסיבוב השני).

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

Adi
12-08-2008, 17:59
בס"ד

לא ברור אם הכוונה היא שכשמסיימים לעבור על כל האנשים, מתחילים שוב מ-1, והוא חי, או שממשיכים במעגל (ויכול להיות ש-1 ימות).
לפי האפשרות הראשונה, זה 1. לפי האפשרות השנייה, זה מספר אחר (אבל ברור שזה לא 4979, כי הוא ייהרג בסיבוב השני).

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


אני מתקן את התשובה שלי.. 9979
לא מתחילים שוב מ1 אחרת מה הטעם , זה מתמשך במעגל
והתשובה 1 זה לא.
הדרך חשיבה שלי כזאת :
יש לנו בהתחלה 10,000 מתחילים מ -1 [רק בתחילת הספירה !] והורגים את 2 , את 3 לא ,ואת 4 כן, וכן הלאה.. ניתן לראות שבסיבוב הראשון של ההריגה כל המספרים הזוגיים אוטומטית מתים ! לכן גם 10000 מת .
מי שנשארו אלו 5000 מקומות שכל אחד מיצג את אחד המספרים האי זוגיים בין 1-10,000 .
מכיוון ש 10,000 נפל [זוגי] ואנחנו ממשיכים הרי ששוב יוצא לנו ש 1 נשאר חי אבל הפעם הסידרה היא ככה:
1,3,5,7.....................9999 [5000 מקומות,כאשר במקום ה5000 ממוקם 9999]
עכשיו.. הגעתי למסקנה [או יותר נכון ניחשתי] שכל סיבוב כזה המספר האחרון ייפול.
בהריגה הראשונה 10,000 נפל בגלל היותו אי זוגי , בהריגה השנייה 9999 ייפול מתוך 5000 מספרים.. בהריגה השלישית 9997 ייפול מתוך 2500 מספרים וכן הלאה [כל סיבוב כמות המספרים הנותנה קטנה פי 2]
אם מורידים ככה כל סיבוב חצי מהמקומות והמספר האחרון נופל , בסופו של דבר מגיעים למצב שיש 0.66 מקומות [יענו מקום 1 , נדמה לי.. בגלל שחילוק כל הזמן ב 2 לא ייתן לי מספר שלם.. בסופו של דבר מגיע לשבר אז אפשר להסיק שנשאר מספר אחד] והמספר במקום הזה הוא 9979

עשהאל
12-08-2008, 18:01
בס"ד

ובכן (אין לי משהו יותר מהיר):
בהתחלה היו 10000 אנשים.
אחרי הסיבוב הראשון, נותרו אלו מהצורה 2n-1, שהם 5000.
אחרי הסיבוב השני, נותרו אלו מהצורה 4n-3, שהם 2500.
אחרי הסיבוב השלישי, נותרו אלו מהצורה 8n-7, שהם 1250.
אחרי הסיבוב הרביעי, נותרו אלו מהצורה 16n-15, שהם 625.
אחרי הסיבוב החמישי, נותרו אלו מהצורה 32n-31, שהם 313.
אחרי הסיבוב הששי, נותרו אלו מהצורה 64n-31, שהם 156.
אחרי הסיבוב השביעי, נותרו אלו מהצורה 128n-95, שהם 78.
אחרי הסיבוב השמיני, נותרו אלו מהצורה 256n-223, שהם 39.
אחרי הסיבוב התשיעי, נותרו אלו מהצורה 512n-479, שהם 20.
אחרי הסיבוב העשירי, נותרו אלו מהצורה 1024n-479, שהם 10.
אחרי הסיבוב ה-11, נותרו אלו מהצורה 2048n-479, שהם 5.
אחרי הסיבוב ה-12, נותרו אלו מהצורה 4096n-479, שהם 2.
אחרי הסיבוב ה-13, נותרו אלו מהצורה 8192n-4575, שהם 1.

לסיכום, זה שנשאר הוא ה-3617.

Adi
12-08-2008, 18:09
משהו קצת מתפקשש לי בדברים שלך:

"אחרי הסיבוב השלישי, נותרו אלו מהצורה 8n-7, שהם 1250"
אם כך , יוצא שהאחרון היינו 9992 מה שלא יכול להיות - מספר זוגי.

ולא הבנתי את המעבר שלך מ 8n-7 בשורה שלישית לשורה רביעית בה כתוב 16n-15

עשהאל
12-08-2008, 19:30
בס"ד

למה האחרון הוא 9992? 8\cdot 1250-7=9993.
והמעבר הוא פשוט - במקום n, הצבתי 2n-1.

והמסקנה שלך, שבכל סיבוב האחרון ייפול, היא כמובן שגוייה.
למשל, אם יש 10 אנשים, בסיבוב הראשון הזוגיים נופלים, ובסיבוב השני 3,7 נופלים, ו-9, שהוא האחרון, נשאר.

Adi
12-08-2008, 21:31
אוקיי טעות שלי , אך למה מהסיבוב התשיעי עד ל 12 ה -479 לא משתנה ?
אם סתם לדוגמא בסיבוב 9 :
512n-479

מציבים במקום N , 2N-1 [הפוך]
הרי סיבוב הבא אמור להיות
1024n - 991

עשהאל
13-08-2008, 00:10
בס"ד

כי בסיבובים האלה, הורגים את האי-זוגיים, ומשאירים את הזוגיים, ולכן מציבים 2n, ולא 2n-1.

Adi
13-08-2008, 00:51
בס"ד

כי בסיבובים האלה, הורגים את האי-זוגיים, ומשאירים את הזוגיים, ולכן מציבים 2n, ולא 2n-1.


מה ? כבר בסיבוב הראשון כל הזוגיים מתו. או שאתה מתכוון למיספור ?

עשהאל
13-08-2008, 00:58
בס"ד

הכוונה לאי-זוגיים מבין אלה שנשארו (כלומר, הראשון מאלה שנשארו, השלישי מאלה שנשארו, וכו').

Adi
13-08-2008, 02:11
הבנתי , אני אבדוק את התשובה ..

עשהאל
13-08-2008, 03:56
בס"ד

אגב, בדקתי במחשב, וזה באמת ה-3617.

עשהאל
13-08-2008, 05:08
בס"ד

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