חידה

[dim dim]

חידה

1. אדם עומד על לוח שח מט (בגודל 8*8) במשבצת A1. כמה דרכים יש לו להגיע למשבצת h8 אם מותר לו ללכת רק ימינה ולמעלה? 2. מהי הנוסחה המתמטית שתלויה אך ורק בגודל לוח השחמט n*n. כלומר נוסחה שתלויה רק ב-n.

 

[snogal]

תשובה

2 התשובה היא

2n!/(n!*n!*(n+1))​

את התשובה א' אפשר לקבל ע"י הצבה של 8

 

[snogal]

אופס חשבתי על משהו אחר

התשובה היא כמובן

(2n)!/(n!*n!)​

 

[dim dim]

יש לך טעות

ב2*2 יש 2 אפשרויות ואילו לפי הנוסחה שלך 6

 

[טלמון סילבר]

../images/Emo62.gif תיקון "קל"

במקום n צריך להיות כמובן n-1, כי דרושים סה"כ n-1)*2) מהלכים:

(2n-2)!/((n-1)!)²​

 

[dim dim]

דרך מחשבה?

 

[טלמון סילבר]

הדרך של נדב, כמובן.

מותר ללכת או ימינה או למעלה, ובכל מקרה ניאלץ לבצע בדיוק n-1 צעדים ימינה, ובדיוק n-1 צעדים למעלה, לא משנה באיזה סדר. השאלה היא, כמה סדרים אפשריים? שאלה זו שקולה כמובן למספר הסידורים של n-1 כדורים זהים, בשורה הכוללת גם n-1 כדורים זהים מסוג אחר, סה"כ 2n-2 כדורים, שזה שווה כמובן למספר הצירופים 2n-2 מעל n-1, והנוסחה ידועה, אם כי לא אכפת לי לספר עליה למי שעדין אינו מכיר (עוד לא למד).

 

[עריסטו]

חידת המשך

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

 

[snogal]

אגב,

את החלק התכנותי כבר סיימת?

 

[clocker]

אפשר להציע חידת המשך ?

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

 

[עריסטו]

תשובה (וחידת המשך...)

48639. רוצים למצוא את פתרון חידתו של clocker עבור כל הלוחות בגודל 1 עד n. כיצד ניתן לעשות זאת בסיבוכיות O ?

 

[clocker]

יש לי פתרון, בעזרת פונקציה יוצרת

לפחות לפי הפתרון שלי, קיבלתי שעבור נוסחאת הנסיגה an=(n-1)*an-1 + 1 הפונקציה היוצרת היא f(x)=-x(e^x)*~(e^(-x)/(x+x^2)dx כאשר ~ מסמן אינטגרל את הפתרון ניתן לקבל כעת לכל n על ידי an=d^n/dx * f(0)/n!1 או במילים, נגזרת nית של f בנקודה 0 חלקי n עצרת. מאחר וסיבוכיות גזירה היא oz וכך גם סיבוכיות של חישוב עצרת, סיבוכיות כל התהליך הוא oz

 

[clocker]

אגב, יצא לי תשובה אחרת ממך

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

 

[טלמון סילבר]

התשובה של עריסטו נכונה -

48639. חישוב פשוט במחשב:

rec(a,b) { if (a * b == 0) return (1); return (rec(a-1,b) + rec(a,b-1) + rec(a-1,b-1)); }​

(ניסיתי לתרגם ל-C, ואני מקווה שמובן).

 

[clocker]

או שלא הבנתי, או שנפלה בחלקנו טעות

אני אקרא לרקורסיה שלך REC כפי שקראת בקוד שלך Rec(a,b)=Rec(a-1,b-1)+Rec(a-1,b)+Rec(a,b-1)zzz ואני אקרא לרגרסיה שלי Reg Reg=(n-1)*Reg(n-1)+1 להלן הפלט הבא מתוכנת מחשב, מ1 ועד 8 N=1, Rec=1, Reg=1 N=2, Rec=3, Reg=2 N=3, Rec=13, Reg=5 N=4, Rec=63, Reg=16 N=5, Rec=321, Reg=65 N=6, Rec=1683, Reg=326 N=7, Rec=8989, Reg=1957 N=8, Rec=48639, Reg=13700 הפלט עבור המקרים הראשונים אמור להיות Ans(2)=2 Ans(3)=5 אפשר פשוט לספור ולראות על כן Rec לא יכולה להיות נכונה. מצד שני, עבור החידה המקורית (כאשר ניתן לנוע רק למעלה וימינה), הגענו למסקנה ש Ans(4)>20 על כן גם Reg שגויה, יש למישהו רעיון לנוסחאת נסיגה שעובדת ?

 

[טלמון סילבר]

לא הבנתי איך ספרת את Ans

n=2 1. a1 - b1 - b2 2. a1 - b2 3. a1 - a2 - b2 Ans(2) = 3 n=3 1. a1 - b1 - c1 - c2 - c3 2. a1 - b1 - c2 - c3 3. a1 - b1 - b2 - c2 - c3 4. a1 - b1 - b2 - c3 5. a1 - b1 - b2 - b3 - c3 6. a1 - b2 - c2 - c3 7. a1 - b2 - c3 8. a1 - b2 - b3 - c3 9. a1 - a2 - b2 - c2 - c3 10. a1 - a2 - b2 - c3 11. a1 - a2 - b2 - b3 - c3 12. a1 - a2 - b3 - c3 13. a1 - a2 - a3 - b3 - c3 Ans(3) = 13​

 

[clocker]

טעות שלי - חשבתי שיש הגבלה נוספת

חשבתי שאסור לחצות את האלכסון, וכך גם בניתי את נוסחאת הנסיגה

 

[snogal]

גם אני אציע משהו

(שכבר עלה בעבר בפורום אבל בניסוח שונה) נניח שישנו נהר מהמשבצת A1 ל H8 (או עד המשבצת העליונה ימנית , אם מדובר על לוח nXn) ברגע שהתחלת לצעוד לא תוכל לחצות את הנהר, כלומר אתה נשאר במשולש העליון או התחתון בלבד תלוי בצעד הראשון שלך.

 

[clocker]

לזה אני התייחסתי

אולם זה לא נכון, ניתן לעבור את האלכסון

 

[snogal]

אז בנוסח

הזה, אסור לך לחצות את האלכסון. השאלה היא , מה תהיה התשובה במקרה הזה.