בתשובה לצפריר כהן, 06/12/15 22:18
 |
|
 |
||
|
||||
 |
ואני אוסיף חידה מתימטית ששמעתי לאחרונה ומצאה חן בעיני: איזה מספר בין 1000 ל-2000 אינו יכול להיכתב כסכום של מספרים עוקבים? הערה: הסכום יכול להיות כמובן של יותר משני מספרים עוקבים, אבל הם חייבים להיות טבעיים. |
 |
 |
 |
|
|
|
||
|
||||
|
בלי לאשר או להכחיש, ההסבר למה יותר חשוב מהמספר (או הניחוש). | |
|
|
|
|
|
||
|
||||
|
אם המספר הוא אי זוגי אז הוא הסכום של שני המספרים העוקבים שסביב החצי שלו. אם הוא מתחלק למספר אי זוגי X אז הוא הסכום של X המספרים העוקבים שמסביב לתוצאת החלוקה של המספר ב-X. (לדוגמה: 1785 מתחלק ל-5, המנה היא 357, והוא הסכום של 355, 356, 357, 358, 359). המספר היחיד בתחום שהוא לא אי זוגי ולא מתחלק למספר אי זוגי הוא 1024. |
|
|
|
|
|
|
||
|
||||
|
יפה, אבל דומני שחסר לך פרט קטן, כי הראית שכל מי שמתחלק במספר אי זוגי הוא סכום של עוקבים. אבל לא הראית שמי שלא מתחלק למספר אי-זוגי אי-אפשר לכתוב ככה. קח למשל את 1004, אפשר לכתוב אותו כסכום של Y מספרים, כאשר Y הוא דוקא זוגי - בפרט עבור Y=8: 122+123+124+125+126+127+128+129 = 1004. או בניסוח אחר, נניח ולא הייתי מספר לך שיש מספר אחד כזה (ומאחר שפסלת את כל האחרים נשארת עם אחד), אזי נותרה עליך חובת ההוכחה שאת 1024 אי-אפשר לכתוב כסכום של עוקבים. |
|
|
|
|
|
|
||
|
||||
|
טוב, זה פשוט, סכום של n מספרים עוקבים שמתחילים במספר a הוא חצי המכפלה של n ב (2a+n-1) שהיא מכפלה של זוגי באי-זוגי ובפרט לא יכולה להיות חזקה של 2. | |
|
|
|
|
|
||
|
||||
|
בעצם חבל שכתבתי את התגובה הזו, התגובה שכתבתי אחריה מבהירה יותר את החסר בשיטה שלך, בעוד התגובה הזאת מצומצמת יותר ומוכוונת פתרון יותר. אתה כמובן צודק, אבל שים לב לתגובה הבאה. נראה לי שפתרון שלם מצריך גם תשובה אליה. | |
|
|
|
|
|
||
|
||||
|
ועוד דוגמה למה הטיעון שלך לא מספיק: כשהאי-זוגי הוא גדול מאד, אז אין סדרה חשבונית אורכה כל כך שמקיימת את תנאי הבעייה. קח למשל את 1994, שהוא 997*2. לפי השיטה שלך, היינו צריכים לבנות סדרה של 997 עוקבים סביב 2, וכזאת לא קיימת על פי תנאי הבעייה. ולכן גם 1994 לא ניתן להצגה כסכום של עוקבים על פי הטיעון שלך. (מאחר ו-997 הוא ראשוני, אין אי-זוגיים קטנים יותר לפירוק). |
|
|
|
|
|
|
||
|
||||
|
אני אשלים את הפתרון (הנכון) של easy, כי נראה לי שהצקתי לו מספיק. בנוסף לתנאי של איזי שמאפשר קיום סדרה חשבונית, קיים תנאי נוסף למי שנשאר: מי שמתחלק במספר זוגי N עם שארית של 1 (שזה אומר שהתוצאה היא X.5), ניתן לכתוב אותו כסכום של סדרה חשבונית בת N איברים שמתחילה ב-X-N/2+1 ונגמרת ב-X+N/2. למשל, בדוגמה הקודמת שלי, חלוקה של 1994 ב-4 תיתן 498.5, והסדרה העוקבת המתאימה תהיה 497,498,499,500. ז"א שמספר שלא ניתן לכתיבה כסכום של עוקבים צריך לקיים את שני התנאים: לא להתחלק באי-זוגי (קטן מספיק) ולא להשאיר שארית 1 בחלוקה בשום מספר זוגי (יותר מדויק בשום חזקה של שתיים, כי מספר זוגי אחר ניתן לפירוק לזוגי ואי-זוגי, שניהם קטנים ממנו, וזה כבר נכלל בתנאי הקודם). מאחר ו-1024 הוא חזקה של שתיים, אזי שום חלוקה שלו בחזקה של שתיים איננה מותירה שארית של 1, ולכן לא ניתן לכתוב אותו כסכום של 2 עוקבים. 1 לפיו מי שמתחלק במספר אי זוגי (ודייק: קטן מספיק כדי לאפשר את סדרת העוקבים החוקית), ניתן לכתוב אות כסכום של עוקבים |
|
|
|
|
|
|
||
|
||||
|
ואני אוסיף חידה שקיבלתי אתמול בתמורה לחידה שלך קבוצה של 30 תלמידים מקבלת 30 פיסות נייר ממוספרות מ 1 עד 30 בחדר הסמוך יש 30 קופסאות ממוספרות גם הן ובתוכן בסדר אקראי 30 פתקים ממוספרים כנ"ל. אחד אחד עוברים התלמידים לחדר הסמוך. כל תלמיד רשאי לבדוק רק 29 מתוך 30 הקופסאות, ואז יוצא החוצה לחדר שלישי. הקבוצה מנצחת רק אם כל אחד מחברי הקבוצה הצליח למצוא באחת הקופסאות את הפתק עם המספר הזהה לשלו. בנה אסטרטגיה לקבוצה שתמקסם את הסיכוי לנצחון. |
|
|
|
|
|
|
||
|
||||
|
מאחר וכבר פתרתי את החידה הזאת בעבר, אחכה כאן עם הפתרון. בינתיים אזכיר שתי גרסאות שאני מכיר - באחת כל תלמיד בודק רק 15 קופסאות, והמטרה זהה למוגדרת אצלך. בשנייה, התלמיד הראשון רשאי להחליף 2 פתקים בין הקופסאות. |
|
|
|
|
|
|
||
|
||||
|
אם פתרתי נכון, זאת גרסה חביבה לקושיה מפורסמת במדעי המחשב. אולי כדאי שהמתכנתים בקהל ימנעו מלחשוף את התשובה (היפה) כדי לתת גם לאחרים הזדמנות. | |
|
|
|
|
|
||
|
||||
|
הגרסה שאני קיבלתי היתה מתמטית אבל התשובה אכן מיד העלתה את האסוציאציה למדעי המחשב. | |
|
|
|
|
|
||
|
||||
|
החוקים לא כל כך ברורים לי. מותר להם להראות אחד לשני את הפתקים שלהם לפני שהראשון עובר לחדר השני? מותר להם לבחור את הסדר בו הם ייכנסו לחדר השני? מותר להם להזיז את הקופסאות בחדר השני? בכל מקרה, גם אם לא, זאת נראית לי שאלה טריויאלית - אם פתחת 29 קופסאות אתה יודע בוודאות מה יהיה בקופסא ה-30. |
|
|
|
|
|
|
||
|
||||
|
מה זה עוזר לך שאתה יודע מה יש בקופסא ה-30 אחרי שבחרת דוקא באחותה התאומה, הקופסא ה-29, וכל הקבוצה הפסידה את הפרס? | |
|
|
|
|
|
||
|
||||
|
למה "אחרי"? קודם תפתח את 29 הקופסאות שמותר לך, ואחר כך, אם לא מצאת את הקופסא המתאימה, תבחר את הקופסה ה-30 בלי לפתוח אותה. |
|
|
|
|
|
|
||
|
||||
|
מותר, מותר ומותר. אסור כמובן להוציא את הפתקים מהקופסאות. הקבוצה מנצחת רק אם כל אחד מחבריה מצא בפועל את הפתק התואם לשלו. |
|
|
|
|
|
|
||
|
||||
|
אני בטח מפספס משהו, החידה נראית לי טריויאלית, אני לא רואה איך הם יכולים שלא להצליח. | |
|
|
|
|
|
||
|
||||
|
בגלל זה עדיף לספר אותה כשבמקום 29 יש 15 או 17 או 20. | |
|
|
|
|
|
||
|
||||
|
נראה לי שאם במקום "כל תלמיד רשאי לבדוק רק 29 מתוך 30 הקופסאות" היה "התלמידים יכולים לבדוק 29 מתוך 30 הקופסאות בסך הכל" החידה היתה קצת יותר קשה (אבל אני בטח לא מבין את החידה). | |
|
|
|
|
|
||
|
||||
|
נראה לי שזה אותו דבר, לא? | |
|
|
|
|
|
||
|
||||
|
לא, משום שבניסוח הראשון כל תלמיד יכול לבדוק 29 קופסאות (ז"א לדעת מה יש בכל קופסא באופן בלתי תלוי בשאר התלמידים) ובניסוח השני אם התלמיד הראשון בדק 10 קופסאות והתלמיד השני בדק 12 קופסאות אז השלישי יוכל לבדוק רק 7 (ז"א שהם צריכים לשתף פעולה ולמצוא דרך להעביר מידע מאחד לשני)... | |
|
|
|
|
|
||
|
||||
|
נראה לי אם כך שבניסוח השני החידה היא פשוט בלתי אפשרית. ולכן הוא לא הניסוח אליו כיוון המשורר. | |
|
|
|
|
|
||
|
||||
|
אפשרית בלי המגבלה מכאן (די דומה לחידת שלושת המתגים). שנשאיר אותה איזה יום בלי פתרון? | |
|
|
|
|
|
||
|
||||
|
כל היפה בחידה הזאת שהיא לא נזקקת לטריקים מלוכלכים כמו חידת שלושת המתגים. | |
|
|
|
|
|
||
|
||||
|
הפתרון בין הקווים (זהירות, ספויילר לפתרון אפשרי של החידה הראשונה, מי שעדיין מחפש תשובה שלא יקרא). ══════════════════════════════════════════════════════ לפני שהתלמידים עובדים לחדר השני הם צריכים לבחור פראייר, תלמיד עם סבלנות ויכולת לספור עד 30. הפראייר נכנס לחדש השני ראשון, פותח את 29 הקופסאות הראשונות (ככה שהוא יודע איזה מספר מכילות כל הקופסאות) ומסדר אותן ככה שזאת עם 1 תהיה ראשונה, זאת עם 2 תהיה שניה וזאת עם 30 תהיה אחרונה (כמובן כולל כל הקופסאות באמצע). אחר כך הוא בוחר את הקופסא שמתאימה למספר שלו. התלמיד השני נכנס, סופר עד המספר שמופיע בפתק שלו, ובוחר בקופסא שנמצאת שם (בלי לפתוח אותה, הוא כבר יודע איזה מספר יש שם משום שהראשון עשה בשבילו את העבודה). התלמיד השלישי חוזר על אותו הדבר, וגם הרביעי והחמישי וכך הלאה. סה"כ נפתחו 29 קופסות (כולן על ידי התלמיד הראשון). ══════════════════════════════════════════════════════ לא הוגן, לא סימטרי, לא יעיל, אבל עובד. |
|
|
|
|
|
|
||
|
||||
|
אוקיי. ועכשיו פתרון בלי שניתן להעביר אינפורמציה אחורה. נניח שהקופסאות מקובעות לרצפה, וכל אחד מהתלמידים רשאי לפתוח 29 קופסאות. |
|
|
|
|
|
|
||
|
||||
|
תרשה לי וריאציה על החידה: תלמיד אחד, 30 קופסאות בטור, בכל קופסא פתק עם מספר סידורי 1-30. המספרים לא חוזרים על עצמם. התלמיד צריך לבחור את הקופסא המכילה את פתק מספר 7, מותר לו לנסות 29 פעמים. אם יכשל, הוא יוצא להורג בעינויים ולאחר הקבורה האריס ישיר מעל קיברו שירי היתולים. בחר אסטרטגיה עבור התלמיד (בהנחה שאתה רוצה למזער את ההסתברות להוצאתו להורג - קל וחומר למנוע מהאריס לשיר). |
|
|
|
|
|
|
||
|
||||
|
מה איכפת לו שישיר, הוא לא ישמע אותו. זאת שאלה אמיתית? יש אסטרטגיה טובה מפתיחת קופסאות אקראית, שתיתן סיכוי של 29/30 להישאר בחיים? |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח. בהנחה שהפתקים מחולקים בצורה אקראית, מה ההסתברות לשרשור מלא של כל שלושים הכדים? | |
|
|
|
|
|
||
|
||||
|
לא הבנתי את הכוונה "שרשור". הפתרון שלי לחידה שלך הוא שהתלמיד יבחר קופסה אחת שאותה לא יפתח, ואז יפתח את כל האחרות. ההסתברות שלרוע מזלו קלע דווקא לקופסה עם המספר 7 היא 1/30. |
|
|
|
|
|
|
||
|
||||
|
אאל"ט, ההסתברות לכך היא 1/30 ואין לי איסטרטגיה מנצחת עבור התלמיד האומלל. שיהיה לו בהצלחה. | |
|
|
|
|
|
||
|
||||
|
לא. בוא נניח שהטביעו את המספרים על תחתית הקופסאות. | |
|
|
|
|
|
||
|
||||
|
אם הראשון פתח 29 קופסאות והציץ בתוכנן ולא מצא את הפתק עם המספר הזהה לשלו, אז למרות שהוא יודע שהפתק נמצא בקופסה האחרונה הקבוצה הפסידה. אפשר לעשות את זה ממוכן אם יותר נוח לך - בכל קופסה יש סורק ברקוד, וכשאתה מציג לו את הפתק התואם נרשמת לך ההתאמה. אחרי 29 פתיחות הקופסאות ננעלות. |
|
|
|
|
|
|
||
|
||||
|
אופס - אם הסורק רק מהבהב ''מתאים'' או ''לא מתאים'', זה מאד משנה את הפתרון כפי שאני זוכר אותו. | |
|
|
|
|
|
||
|
||||
|
לא, לא. זה רק כדי לוודא שעמדו בתנאים לקבל את הפרס. המשתתפים רואים את המספרים כמובן. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |