חידה

[snogal]

ובכן

מספר קודקודים

2^n​

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

n*2^(n-1)​

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

 

[1אברהם]

תשובה

בקוביה N ממדית יש

2^N​

קודקודים

 

[1אברהם]

המשך

ויש

N*(2^(N-1))​

מקצועות ומספר הפאות הוא

(N*(N-1)/2) *2^(N-2)​

ובאופן כללי מספר הפאות ה M ממדי הוא

(M,N)*2^(N-M)​

כאשר (M,N) הוא מספר הצרופים M מתוך N וגם M קטן שווה לN

 

[snogal]

תוכל , בבקשה , להסביר את

הנוסחה שבה חישבת את מספר הפיאות? תודה

 

[1אברהם]

הסבר

הקודינטות של קוביה N ממדית שקולות למספק בינרי עם N ביטים. הביט הראשון מציון אם הנקודה למעלה או למטה (כלומר מיקומה בציר X למשל ), השני אם הנקודה בצד ימין או שמאל ( (כלומר מיקומה בציר Y למשל ) השלישי אם היא קדימה או אחורה ((כלומר מיקומה בציר Z למשל ) וכך הלאה. כל נקודה מתאימה לצרוף יחיד של מספר בינרי (2בחזקת N אפשרויות ) כל מקצוע מתאים ל2 מספרים בינרים שנבדלים רק בשינוי ביט אחד, ולכן מספר המקצועוצ הוא בחירה של הביט השונה (N מקרים ) כאשר שאר N-1 הביטים יכולים לקבל 2 בחזקת N-1 אפשרויות כל פאה דו ממדית היא 4 מספרים בינרים שנבדלים אחד מהשני רק בשוני של 2 ביטים (ולכן יש 4 נקודות בפאה שהם 2 בחזקת 2 ), כל בחירה של 2 ביטים מתוך ה N 2 ( שתי צרופים מתוך N) מגדירה 2 בחזקת N-2 פאות ( כי שאר N-2 הביטים נותנים 2 בחזקת N-2 מקרים ) כל פאה M ממדית מוגדרת על יד 2 בחזקת M מספרים בינרים ( נקודות ) אשר נבדלים אחד מהשני בשוני של M ביטים מתוך ה N במילים אחרות פאה ממימד M מוגדרת על ידי בחירה של M ביטים שערכם יהיה "dont care" ויש M מתוך N אפשרויות לבחור את אותם M ביטים. אחרי שבחרנו את אותם M ביטים יש לקבוע ערך קבוע לשאר N-M הביטים וכאן יש 2 בחזקת N-M אפשרויות

 

[snogal]

תודה

 

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

יפה מאוד.

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

x1 = 0 x1 = 1 x2 = 0 x2 = 1 . . . xn = 0 xn = 1​

כאשר x1, x2, x3,... הם שמות הצירים (במקום x,y,z). טוב, אבל לא פתרנו את החידה עצמה

 

[1אברהם]

../images/Emo62.gifתשובה כללית לחידה

נתונות N נקודות במרחב ( לא משנה מימדו ) ומכל אחד יוצא קו אחד או יותר אל נקודות אחרות (כלומר מספר הקווים שיוצא מכל נקודה הוא בתחום 1...N-1 ). נסמן ב K את מספר הנקודות שלהם מספר אי זוגי של קווים שיוצאים מהם, אז: 1) K הוא מספר זוגי 2)ניתן לעבור על הקווים "במשיכת קולמוס אחד" אם ורק אם K=0 או K=2 3) ניתן לעבור "במשיכת קולמוס אחד" כאשר מתחילים וגומרים באותה נקודה אם ורק אם K=0 לגבי 1 יש לי הוכחה פשוטה לגבי 2 ו3 קל להוכיח את הכיוון השני כלומר לא ניתו להעביר במשיכת קולמוס אחד אם K אינו 0 או 2 ולא ניתן לגמור באותה נקודה אם K אינו 0 לגבי הכיוון הראשון אני כמעט בטוח שזה נכון ואני אחשוב על הוכחה בחידה יש קוביה ( 8 נקודות ) כאשר מכל קודקוד יוצאים 3 קווים לכן K=8 ולא ניתן לעבור במשיכת קולמוס אחד

 

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

לא הבנתי,

בקוביה 4-מימדית אפשר לעבור על כל המקצועות "במשיכת קולמוס אחת", או אי אפשר?

 

[1אברהם]

במחשבה שניה

אני כבר לא בטוח שמה שאמרתי נכון בכיוון הראשון (K=0 => משיכת קולמוס אחד לאותה נקודה ) ולכן לגבי מימד זוגי של קוביה אני עדין לא יודע אם אפשר או לא. מה שכן אם מימד הקוביה הוא אי זוגי אז אי אפשר כי מכל קודקוד יוצאים מספר אי זוגי (כמספר המימד) של מקצועות.