בעיות מתימטיות

[DadleFish]

בעיות מתימטיות

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

אז הנה השאלות של השבוע הראשון להנאתכם.

 

[DadleFish]

שאלה ראשונה

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

 

[עריסטו]

פתרון

השחקן השני משאיר תמיד שתי ערימות שוות ומנצח.

 

[DadleFish]

../images/Emo45.gif

 

[DadleFish]

שאלה שניה

הוכיחו כי לא ניתן להרכיב לוח של 4x7 משבצות משבע הצורות השונות של משחק הטטריס.

 

[עריסטו]

הדרכה

ציבעו את הלוח בתבנית לוח שחמט.

 

[DadleFish]

שאלה שלישית

בכמה אפסים מסתיימת ההצגה העשרונית של המקדם הבינומי (128 מעל 64)?

 

[עריסטו]

פתרון

במכפלת המספרים מ-65 עד 128 יש: 13 מספרים המתחלקים ב-5 3 מספרים המתחלקים ב-25 1 מספר המתחלק ב-125 לכן המכפלה מכילה את הגורם 5 בסך הכל 17 פעמים. ברור שהיא מכילה את הגורם 2 יותר מ-17 פעמים. לכן התשובה היא 17.

 

[עריסטו]

החיפזון מה - ../images/Emo190.gif

שכחתי את המכנה (64 עצרת). במכפלת המספרים 1 עד 64 יש: 12 מספרים המתחלקים ב - 5 2 מספרים המתחלרים ב-25. לכן 64 עצרת מכיל את הגורם 5 בסך הכל 14 פעמים. מצמצמים עם 17 הפעמים שהוא מופיע במונה ומקבלים שהתשובה היא 3.

 

[DadleFish]

../images/Emo31.gifשכחת בדיוק את מה שאני שכחתי ../images/Emo13.gif

 

[גיל14]

../images/Emo58.gif פתרון

ע"י נייר ועפרון, נמצא שערכו של המקדם הבינומי הוא 23951146041928082866135587776380551750 ולכן הוא מסתיים, כמובן, באפס יחיד. דרך נוספת: הקריטריון למספר הפעמים בו מקדם בינומי n מעל k מתחלק במספר ראשוני p, הוא מספר הנשאים בחיבור k + n-k, המבוצע בבסיס p (הוכח!). 64 הוא כמובן חזקה של 2 ולכן יש נשא יחיד (מהעמודה התשיעית מימין, אל העשירית) - והמקדם מתחלק ב2 פעם אחת. כלומר מספיק להראות שהמקדם מתחלק ב-5 לפחות פעם אחת. 64 בבסיס 5 הוא 244, ומתקיים 244+244 = 1003 (כל הנ"ל בבסיס 5), כלומר שני נשאים. לכן המקדם הבינומי מתחלק ב10 פעם אחת בדיוק, כלומר, יש 0 אחד בלבד בערכו.

 

[DadleFish]

יפה. ../images/Emo45.gif

נייר ועיפרון?!?! איך בכל זאת חישבת את זה?

 

[גיל14]

יש הרבה דרכים

כל שפת תכנות/סקריפט נפוצה עם חבילת bignum כלשהי תשמש. אבל אני השתמשתי במייפל.

 

[DadleFish]

אחלה, תודה ../images/Emo13.gif

 

[גיל14]

אגב,

לא צריך לרוץ למספרים ענקיים כמו 128 עצרת - ניתן ביעילות הרבה יותר גדולה להתעסק עם מספרים יחסית קטנים באמצעות נוסחת משולש פסקל, האומרת ש n מעל k שווה ל n-1 מעל k ועוד n-1 מעל k-1.

 

[DadleFish]

שאלה רביעית

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

 

[עריסטו]

הדרכה

נחלק את הערים לצמדים באופן כלשהו ונמצא מסלול (שאינו עובר על אותו כביש פעמיים) בין חברות כל אחד מהצמדים. יהיו A ו - B שתי ערים חברות צמד, ו - C,D גם הן צמד. אם יש למסלול AB ולמסלול CD קטע משותף, נסו למצוא דרך "להיפטר" ממנו. הראו שתהליך ההיפטרות מהקטעים המשותפים אינו יכול להימשך לנצח.

 

[DadleFish]

../images/Emo13.gif יפה מאוד. עכשיו נחכה לפותרים.

 

[עריסטו]

לחלופין,

במקום לבצע את התהליך הנ"ל ניתן להתחיל מייד מדרך יצירת הצמדים בה "משהו" מקבל ערך קיצוני (מהו אותו "משהו"?) ולהראות שבדרך זו אין קטעי כביש משותפים.

 

[DadleFish]

שאלה חמישית

עליכם לגלות מספר שנבחר מבין המספרים 4000,...,1,2,3 בעזרת סדרת שאלות "כן או לא", כאשר מחיר השאלה תלוי בתשובה: 10 שקלים אם התשובה חיובית, 20 שקלים אם התשובה שלילית. מהו סכום הכסף שאתם חייבים להכין אם ברצונכם להבטיח שתגלו את המספר?