חידת המשך

[עריסטו]

חשבו את מספר המצולעים בעלי התכונות הבאות:

- אינם חוצים את עצמם.
- כל זוויותיהם כפולות של 90°.
- ניתן להניח אותם על מערכת צירים קרטזית כך, ששפתם (היקפם) תכיל את כל 400 הנקודות בעלות השיעורים השלמים מ-1 עד 20 כולל.
- היקפם שווה 400.
- דרישה חלשה יותר מהדרישה בחידה המקורית: סכום אורכי הקטעים המקבילים לציר x מתחלק ב-4.

 

[Lucifer LightBringer]

חשבו את מספר המצולעים בעלי התכונות הבאות:

- אינם חוצים את עצמם.
- כל זוויותיהם כפולות של 90°.
- ניתן להניח אותם על מערכת צירים קרטזית כך, ששפתם (היקפם) תכיל את כל 400 הנקודות בעלות השיעורים השלמים מ-1 עד 20 כולל.
- היקפם שווה 400.
- דרישה חלשה יותר מהדרישה בחידה המקורית: סכום אורכי הקטעים המקבילים לציר x מתחלק ב-4.

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

 

[עריסטו]

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

המצולע הוא עקומה סגורה פשוטה (לא חותכת את עצמה).
עקומה פשוטה: O
עקומה לא פשוטה: 8

 

[הפרבולה1]

אפשר רמז ?

 

[עריסטו]

תנסה עם מספרים קטנים יותר. למשל 8 במקום 20 ו-64 במקום 400. תנסה לשרטט מצולע עם צלעות מאוזנות ומאונכות שעובר דרך 64 הנקודות (ולכן היקפו 64) ובו סכום אורכי הצלעות המאוזנות מתחלק ב-4.

 

[בחשכת הלילה]

תנסה עם מספרים קטנים יותר. למשל 8 במקום 20 ו-64 במקום 400. תנסה לשרטט מצולע עם צלעות מאוזנות ומאונכות שעובר דרך 64 הנקודות (ולכן היקפו 64) ובו סכום אורכי הצלעות המאוזנות מתחלק ב-4.

חידה מעניינת. תודה
בינתיים טרם(?) הצלחתי להוכיח, אבל ראיתי שבכל מסלול דרך nXn נקודות (n - זוגי) מתקבל מספר אי-זוגי של צעדים בכל אחד מארבעת הכיוונים, ולפיכך, מספר הצעדים האופקיים ומספר הצעדים המאונכים הם מסוג 4k+2.

 

[בחשכת הלילה]

תנסה עם מספרים קטנים יותר. למשל 8 במקום 20 ו-64 במקום 400. תנסה לשרטט מצולע עם צלעות מאוזנות ומאונכות שעובר דרך 64 הנקודות (ולכן היקפו 64) ובו סכום אורכי הצלעות המאוזנות מתחלק ב-4.

מצולעים כאלה אינם קיימים גם עם 100, 36, 16, 4 נקודות. הראו לי הוכחה, המבוססת על זוגיות שיעורי ה-x של הנקודות.

 

[בחשכת הלילה]

במקרה הכללי של 2n×2n נקודות, סכום אורכי הצלעות האופקיות שווה 2 מודולו 4 (וכך גם סכום אורכי הצלעות המאונכות).
זה נובע ממשפט כללי יותר.

יהי P מצולע פשוט ששיעורי כל קודקודיו שלמים וצלעותיו מקבילות לצירים במערכת קואורדינטות קרטזית.
יהי G גרף שצמתיו מרכזי המשבצות שמהן מורכב המצולע, וקשתותיו מוגדרות לכל זוג משבצות סמוכות.
יהי A מספר הנקודות השלמות על היקף P ששיעורי x שלהן זוגיים, ו-B מספר הנקודות השלמות על היקף P ששיעורי x שלהן אי-זוגיים.
יהי h האורך הכולל של הצלעות האופקיות של P.

משפט
אם הגרף G הוא עץ, אזי:
h ≡ A - B + 2 (mod 4)

ההוכחה בדרך האינדוקציה לפי מספר המשבצות שמכיל P. הטענה נכונה כאשר P מכיל משבצת אחת. כאשר הוא מכיל n+1 משבצות, תולשים מהעץ G עלה אחד.

 

[בחשכת הלילה]

במקרה הכללי של 2n×2n נקודות, סכום אורכי הצלעות האופקיות שווה 2 מודולו 4 (וכך גם סכום אורכי הצלעות המאונכות).
זה נובע ממשפט כללי יותר.
צפה בקובץ המצורף 139223
יהי P מצולע פשוט ששיעורי כל קודקודיו שלמים וצלעותיו מקבילות לצירים במערכת קואורדינטות קרטזית.
יהי G גרף שצמתיו מרכזי המשבצות שמהן מורכב המצולע, וקשתותיו מוגדרות לכל זוג משבצות סמוכות.
יהי A מספר הנקודות השלמות על היקף P ששיעורי x שלהן זוגיים, ו-B מספר הנקודות השלמות על היקף P ששיעורי x שלהן אי-זוגיים.
יהי h האורך הכולל של הצלעות האופקיות של P.

משפט
אם הגרף G הוא עץ, אזי:
h ≡ A - B + 2 (mod 4)

ההוכחה בדרך האינדוקציה לפי מספר המשבצות שמכיל P. הטענה נכונה כאשר P מכיל משבצת אחת. כאשר הוא מכיל n+1 משבצות, תולשים מהעץ G עלה אחד.

המקור ברוסית: https://m.mathnet.ru/links/0c006fbf61479b1b8aa35a2e2f72bf01/mp70.pdf מדובר שם על צריח בלוח שחמט 8X8. זה מתאים לכל גודל זוגי. במקור, הם רצו להוכיח שסכום אורכי הצלעות האופקיות אינו יכול להיות שווה לסכום אורכי הצלעות המאונכות, אבל זה נכון רק לגבי n=4k, למשל 8X8. עבור לוח 6X6 זה לא נכון: שני סכומי האורכים יכולים להיות שווים 18 בו זמנית.

 

[הפרבולה1]

המקור ברוסית: https://m.mathnet.ru/links/0c006fbf61479b1b8aa35a2e2f72bf01/mp70.pdf מדובר שם על צריח בלוח שחמט 8X8. זה מתאים לכל גודל זוגי. במקור, הם רצו להוכיח שסכום אורכי הצלעות האופקיות אינו יכול להיות שווה לסכום אורכי הצלעות המאונכות, אבל זה נכון רק לגבי n=4k, למשל 8X8. עבור לוח 6X6 זה לא נכון: שני סכומי האורכים יכולים להיות שווים 18 בו זמנית.

אנסה להוכיח את הטענה האחרונה שלך - שני סכומי האורכים לא יכולים להיות שווים אם הלוח הוא באורך זוגי שמתחלק ב 4 .

לפי המשפט הכללי שהוכחתה
אורכי הצלעות האנכיות הוא 4n + 2
אורכי הצלעות האופקיות הוא 4m + 2
אורך הלוח הוא זוגי ושווה ל 2k
צריך להוכיח: אם n=m אז k אי זוגי

סכום כל האורכים האנכיות והאפקיות הוא zzz 4n+2 + 4m+2 = (2k)² = 4k² zzz

zzz 4 ( n + m ) + 4 = 4k² zzz
zzz n + m + 1 = k² zzz

כעת נציב n=m ונקבל

zzz 2m + 1 = k² zzz

לכן k הוא אי זוגי

 

[בחשכת הלילה]

אנסה להוכיח את הטענה האחרונה שלך - שני סכומי האורכים לא יכולים להיות שווים אם הלוח הוא באורך זוגי שמתחלק ב 4 .

לפי המשפט הכללי שהוכחתָ
אורכי הצלעות האנכיות הוא 4n + 2
אורכי הצלעות האופקיות הוא 4m + 2
אורך הלוח הוא זוגי ושווה ל 2k
צריך להוכיח: אם n=m אז k אי זוגי

סכום כל האורכים האנכיות והאפקיות הוא zzz 4n+2 + 4m+2 = (2k)² = 4k² zzz

zzz 4 ( n + m ) + 4 = 4k² zzz
zzz n + m + 1 = k² zzz

כעת נציב n=m ונקבל

zzz 2m + 1 = k² zzz

לכן k הוא אי זוגי

אכן, החלק הזה הוא יותר קל מהחידה של עריסטו. למשל כך. במקרה של טבלה 4k על 4k, האורך הכללי הוא 16k², ואם שני הסכומים שווים, אז כל אחד מהם שווה 8k².
או, בלשונך: 8n+4=16k².
במקרה של טבלה 6 על 6 עדיין כל אחד משני סכומי האורכים הוא מסוג 4k+2, אבל ב-550 מקרים מתוך סה"כ 1072 מצולעים המילטוניים שני האורכים זהים (שווים 18).

 

[בחשכת הלילה]

במקרה הכללי של 2n×2n נקודות, סכום אורכי הצלעות האופקיות שווה 2 מודולו 4 (וכך גם סכום אורכי הצלעות המאונכות).
זה נובע ממשפט כללי יותר.
צפה בקובץ המצורף 139223
יהי P מצולע פשוט ששיעורי כל קודקודיו שלמים וצלעותיו מקבילות לצירים במערכת קואורדינטות קרטזית.
יהי G גרף שצמתיו מרכזי המשבצות שמהן מורכב המצולע, וקשתותיו מוגדרות לכל זוג משבצות סמוכות.
יהי A מספר הנקודות השלמות על היקף P ששיעורי x שלהן זוגיים, ו-B מספר הנקודות השלמות על היקף P ששיעורי x שלהן אי-זוגיים.
יהי h האורך הכולל של הצלעות האופקיות של P.

משפט
אם הגרף G הוא עץ, אזי:
h ≡ A - B + 2 (mod 4)

ההוכחה בדרך האינדוקציה לפי מספר המשבצות שמכיל P. הטענה נכונה כאשר P מכיל משבצת אחת. כאשר הוא מכיל n+1 משבצות, תולשים מהעץ G עלה אחד.

כפי שהבנתי, אף אחד לא קרא את הפוסט! היתה לי שגיאה, ואף אחד לא שם לב. עכשיו תיקנתי. לצערי, השגיאה נגררה לתגובות שלי לעצמי. לתשומת לבכם: הנוסחה הנכונה היא: h≡A-B+2 mod(4)

 

[הפרבולה1]

במקרה הכללי של 2n×2n נקודות, סכום אורכי הצלעות האופקיות שווה 2 מודולו 4 (וכך גם סכום אורכי הצלעות המאונכות).
זה נובע ממשפט כללי יותר.
צפה בקובץ המצורף 139223
יהי P מצולע פשוט ששיעורי כל קודקודיו שלמים וצלעותיו מקבילות לצירים במערכת קואורדינטות קרטזית.
יהי G גרף שצמתיו מרכזי המשבצות שמהן מורכב המצולע, וקשתותיו מוגדרות לכל זוג משבצות סמוכות.
יהי A מספר הנקודות השלמות על היקף P ששיעורי x שלהן זוגיים, ו-B מספר הנקודות השלמות על היקף P ששיעורי x שלהן אי-זוגיים.
יהי h האורך הכולל של הצלעות האופקיות של P.

משפט
אם הגרף G הוא עץ, אזי:
h ≡ A - B + 2 (mod 4)

ההוכחה בדרך האינדוקציה לפי מספר המשבצות שמכיל P. הטענה נכונה כאשר P מכיל משבצת אחת. כאשר הוא מכיל n+1 משבצות, תולשים מהעץ G עלה אחד.

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

 

[בחשכת הלילה]

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

כמובן!