חידה

[טיקטי1]

חידה

יש לכם n (זוגי) נקודות שמסודרות במעגל כמה אפשרויות יש לחיבור קווים בין הנקודות כך שלא יהיו שתי קווים שחותכים אחד את השני וכל הנקודות מחוברות וכל נקודה מחוברת רק לנקודה אחת אין לי את הפתרון

 

[happy pineapple]

אמממ...אני לא מבינה חלק אחד

מסודרות במעגל זה מסודרות בצורת מעגל או בתוך מעגל? אם זה בצורת מעגל אז נראה לי שחצי N זאת התשובה...

 

[איייייל]

למה חצי n?

אני חושב שעבור n=6 יש 4 דרכים... לא? אסימפטוטית נראה לי שזה מתנהג בערך כמו n^n

 

[איייייל]

בעצם 5 דרכים (ל n=6)

כל נקודה יכולה להיות מחוברת לשכנה שלה (2 דרכים), לשכנה השניה (2 דרכים), או לנקודה שנמצאת מולה (דרך אחת)

 

[happy pineapple]

רגע אפשר כאילו שמכל נקודה

ייצאו כמה קווים?

 

[איייייל]

לא

התכוונתי ל 5 האפשרויות האלה:

 

[איייייל]

אופס, לא יצא טוב

 

[happy pineapple]

אהה אופס!!! חשבתי שהשאלה זה כמה

קווים ייחברו את הנקודות...לא שמתי לב שזה שואל כמה אפשרויות...

 

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

אם נאמר

שיש 2n נקודות, ומספר האפשרויות הוא (f(n, אזי מתקבלת סדרה מעניינת, שנראית לי מוכרת מאיזשהו מקום:

f(0) = 1 f(1) = 1 f(2) = 2 f(3) = 5 f(6) = 14 f(7) = 44 f = f(0)f(n-1) + f(1)f(n-2) + f(2)f(n-3) + . . . + ff(0)​

אבל מה הלאה?

 

[טיקטי1]

הנוסחה הסופית זה גם מה שאני הגעתי

אליו שאלתי בפורום מתמטיקה איך אפשר להפוך את זה לנוסחה "סופית" אבל עוד לא בדקתי אים ענו לי

 

[טיקטי1]

בעצם יצא לי דומה. למה עשית בסדרה גם

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

 

[טיקטי1]

"זוגי"="אי זוגי" וההיפך

 

[איייייל]

אני חושב שהוא התכוון

ש (f(n הוא מספר האפשרויות לחבר 2n נקודות. חוץ מזה, האיבר האחרון אמור להיות (f(0)f(n-1 ולא (f(0)f(n...

 

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

תודה על התיקון. ועל ההסבר. כמובן../images/Emo70.gif

טוב, הנוסחה הרקורסיבית די פשוטה, אבל מתחשקת "נוסחה סופית"

. זה לא משהו קשור עם קָטָלָן שנדב סיפר לנו? הסדרה נראית לי מה זה מוכרת...

 

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

ובכן, אלה הם בדיוק

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

K = (4n-2)!!!! / (n+1)! = = 2 * 6 * 10 * . . . * (4n-2) / (n+1)!​

לאונרד אוילר (1707-1783) מצא את הנוסחה הזאת, בדיוק לחידת 2n הנקודות על המעגל! אבל המספרים נקראים על שמו של מתמטיקאי בלגי מהמאה ה-19 אֶזֶ'ן-שָרל קָטָלָן (1814-1894).

 

[טיקטי1]

תודה רבה ואתה יודע במקרה איך הוא

הגיע לנוסחה הזאת?

 

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

לא. נסה לחפש CATALAN

או... לשאול את נדב

 

[טיקטי1]

תודה רבה ../images/Emo13.gif

 

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

תיקון נוסף: K(7)=42

 

[Dancer42]

התשובה

היא N/2 + 2 (N/2 זוגות נקודות יוצרות את החיבור באלכסונים + 2 דרכים לפתור על ההיקף) <><