שאלה בתורת הגרפים, בערך.
האם ניתן לחלק ריבוע שאורך צלעו 3000 למלבנים זרים בזוגות, כך שעבור כל מלבן אורך צלעו הגדולה היא 9 ואורך צלעו הקצרה היא 5? לדעתי צריך לפתור את השאלה על ידי שימוש בטענה הבאה: אם אינטרוול מחולק לתת-אינטרוולים וקצותיו מסומנים ב1,2 וכל נקודת ביניים מסומנת ב1 או 2, אז מספר האינטרוולים הקטנים שקצותיהם מסומנים ב1,2 הוא אי זוגי. הכיוון שלי בינתיים הוא כזה: כאשר מחלקים את הריבוע למלבנים כאלו, מקבלים חלוקות של צלעות הריבוע על ידי המלבנים הסמוכים להן (ז"א, המלבנים שיש להם צלע משותפת עם הריבוע). עבור כל צלע, נסמן את נקודות הביניים בחלוקה הזו ב1 או 2 באופן הבא: נסמן משמאל לימין. נתחיל ב1 ונמשיך לסמן ב1 כל עוד אין שינוי באורך של תת-האינטרוולים. ברגע שיש שינוי באורך (מ5 ל9 או מ9 ל5) נשנה את המספור ל2 ונמשיך לסמן ב2 כל עוד אין שינוי באורך של תת-האינטרוולים. ברגע שיש שינוי נוסף נשנה את המספור שוב ל1 ונמשיך באותו אופן. לדוגמא:
|- - - - - - - - -|- - - - - - - - -|- - - - -|- - - - -|- - - - - - - - -|- - - - -|- - - - - - - - -|- - - - -|- - - - -|- - - - -| 1 1 2 2 1 2 1 2 2 2 2 9 9 5 5 9 5 9 5 5 5
שמתי לב לזה שאורכם של תת-האינטרוולים הקטנים שקצותיהם מסומנים ב1 ו2 מתחלף - אם אורכו של הראשון הוא 9, אז אורכו של השני יהיה 5, אורכו של השלישי יהיה 9, אורכו של הרביעי יהיה 5 וכן הלאה. לפי הטענה שציטטתי מספרם אי זוגי, לכן סכום כל אורכיהם משאיר שארית 5 או 9 בחלוקה ל14. לצערי אני רחוק מלראות את הפתרון מכאן (אם הכיוון הזה בכלל נכון). האם הכיוון שלי נכון? מישהו יכול לתת רמז איך להמשיך מכאן או להציע כיוון אחר אם הכיוון שלי לא נכון? תודה מראש.