האם זה אפשרי?

[amir y]

האם זה אפשרי?

להעביר קווים מכל נקודה לשלושת המרובעים שמתחתיה מבלי שהקווים יגעו אחד בשני? אני לא הצלחתי. מישהו מכיר?

 

[jaXon]

בלתי אפשרי

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

 

[amir y]

תודה על התגובה

באמת שברתי את הראש על זה...

 

[jaXon]

בוא נציג זאת כחידת הוכחה

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

 

[yatir]

מותר לקפל?