חידה יפה מספר
- פותח הנושא אלעדדדדד
- פורסם בתאריך
נניח ש
בכל ה 1000! סידורים שונים יש תמיד חיתוכים. ניקח את הסידור שנותן סכום מינימלי של אורכי הקטעים ( קים כזה בגלל המספר הסופי של הסידורים ). בסידור המינימלי הזה ניקח זוג קטעים שחותכים זה את זה, קטע אחד מחבר בין נקודה אדומה R1 לנקודה כחולה B1 ונקודה והקטע השני שחותך אותו מחבר בין נקודה אדומה R2 לנקודה כחולה B2 . כעת נשנה את החיבור כך ש R1 יחובר לB2 וR2 ל B1קיבלנו סידור חדש שבו 2 הקטעים החדשים כבר לא חותכים זה את זה ובנוסף סכום אורכיהם קטן מאורכי 2 הקטעים בסידור הקודם ( סכום זוג צלעות נגדיות במרובע קטן מסכום אורכי האלכסונים באותו מרובע ). בגלל שקיצרנו את אורכי 2 קטעים בסידור החדש לעומת הסידור הקודם קיבלנו סידור חדש שסכום קטעיו קטן מהסידור הקודם בסתירה לעובדה שבחרנו מקודם את הסידור המינימלי. הסבר נוסף: נתחיל מסידור כלשהוא, על כל זוג קטעים נחתכים נצליב את החיבורים כך שזוג הקטעים החדש כבר לא יחתוך אחד את השני ( אם כי כל אחד מהם עדין יכול לחתוך קטעים אחרים ). בכל שלב שנבצע פעולה כזו יוקטן הסכום הכולל של הקטעים. כיוון שקים סכום מינימלי ( בגלל המספר הסופי של הסידורים ) אי אפשר להמשיך בפעולות אלו בלי סוף ולכן באיזשהוא שלב נגיע לסידור ללא חיתוכים
בכל ה 1000! סידורים שונים יש תמיד חיתוכים. ניקח את הסידור שנותן סכום מינימלי של אורכי הקטעים ( קים כזה בגלל המספר הסופי של הסידורים ). בסידור המינימלי הזה ניקח זוג קטעים שחותכים זה את זה, קטע אחד מחבר בין נקודה אדומה R1 לנקודה כחולה B1 ונקודה והקטע השני שחותך אותו מחבר בין נקודה אדומה R2 לנקודה כחולה B2 . כעת נשנה את החיבור כך ש R1 יחובר לB2 וR2 ל B1קיבלנו סידור חדש שבו 2 הקטעים החדשים כבר לא חותכים זה את זה ובנוסף סכום אורכיהם קטן מאורכי 2 הקטעים בסידור הקודם ( סכום זוג צלעות נגדיות במרובע קטן מסכום אורכי האלכסונים באותו מרובע ). בגלל שקיצרנו את אורכי 2 קטעים בסידור החדש לעומת הסידור הקודם קיבלנו סידור חדש שסכום קטעיו קטן מהסידור הקודם בסתירה לעובדה שבחרנו מקודם את הסידור המינימלי. הסבר נוסף: נתחיל מסידור כלשהוא, על כל זוג קטעים נחתכים נצליב את החיבורים כך שזוג הקטעים החדש כבר לא יחתוך אחד את השני ( אם כי כל אחד מהם עדין יכול לחתוך קטעים אחרים ). בכל שלב שנבצע פעולה כזו יוקטן הסכום הכולל של הקטעים. כיוון שקים סכום מינימלי ( בגלל המספר הסופי של הסידורים ) אי אפשר להמשיך בפעולות אלו בלי סוף ולכן באיזשהוא שלב נגיע לסידור ללא חיתוכים
עריסטו
Active member
גירסה שונה מעט להסבר הנוסף
נתחיל מסידור כלשהוא, על כל זוג קטעים נחתכים נצליב את החיבורים כך שזוג הקטעים החדש כבר לא יחתוך אחד את השני ( אם כי כל אחד מהם עדין יכול לחתוך קטעים אחרים ). בכל שלב שנבצע פעולה כזו יוקטן הסכום הכולל של הקטעים. לכן לא ייתכן שנגיע לסידור שכבר היינו בו. בגלל המספר הסופי של הסידורים אי אפשר להמשיך בפעולות אלו בלי סוף ולכן באיזשהוא שלב נגיע לסידור ללא חיתוכים
נתחיל מסידור כלשהוא, על כל זוג קטעים נחתכים נצליב את החיבורים כך שזוג הקטעים החדש כבר לא יחתוך אחד את השני ( אם כי כל אחד מהם עדין יכול לחתוך קטעים אחרים ). בכל שלב שנבצע פעולה כזו יוקטן הסכום הכולל של הקטעים. לכן לא ייתכן שנגיע לסידור שכבר היינו בו. בגלל המספר הסופי של הסידורים אי אפשר להמשיך בפעולות אלו בלי סוף ולכן באיזשהוא שלב נגיע לסידור ללא חיתוכים
fistuktheking
New member
או שהשאלה לא ברורה
או שהפתרון ממש פשוט עיגול 0---x 0----- X 0----------X X 0 --------X x 0------X 0---X יצא קצת עקום אבל הבנת את הכוונה אני משער שלא זאת החידה?
או שהפתרון ממש פשוט עיגול 0---x 0----- X 0----------X X 0 --------X x 0------X 0---X יצא קצת עקום אבל הבנת את הכוונה אני משער שלא זאת החידה?
הוכחה נוספת באינדוקציה
הבדיקה נכונה עבור נקודה אחת אדומה ואחת כחולה וגם עבור 2 מכל צבע. נניח שניתן לחבר עבור עד N נקודות אדומות ו N כחולות ונוכיח עבור N+1. לאחר שחיברנו את N הנקודות משני הצבעים נוסיף נקודה אדומה ואחת כחולה. נחבר את הנקודה החדשה האדומה לנקודה הכחולה החדשה (נקרא לישר זה L). נסתכל על הקטע הנחתך (מבין החיבורים הקודמים) הקרוב ביותר לישר L לנקודה האדומה החדשה. ננתק את הקטע הנחתך ונחבר את הנקודה הכחולה שלו לנקודה האדומה החדשה. קטע זה אינו חותך קטעים קודמים בדף. באותה צורה נחבר את הנקודה האדומה מהקטע החיתוך הקרוב לנקודה הכחולה החדשה. גם קטע זה אינו נחתך על ידי הקטעים הקודמים. ננתק את שאר הקטעים שנחתכו ע"י הישר L. (נשאיר את שני הקטים האחרונים שחיברנו לנקודות החדשות) לכל היותר יש N נקודות מכל צבע שנתקנו. (מבין הקטעים שנחתכו ע"י הישר L). לפי הנחת האינדוקציה ניתן לחברם בקטעים שאינם נחתכים. חיבור נקודות אלו לא יחתוך קטעים שלא נחתכו ע"י הישר L.(החיבור יעשה כך: לאחר חיבור שני הקטעים לשתי הנקודות החדשות נחבר את הנקודה הכחולה שנותקה מהקטע לנקודה האדומה שנותקה מהקטע שלה נסתכל על הקטעים שנחתכים על ידי ישר החיבור כמו שתיארנו קודם ונחבר את הקטעים החדשים כפי שתואר קודם). ולכן ניתן לחבר כל כמות בת מניה של נקודות משני צבעים שאין שלושה על ישר אחד. ההסבר קצת עילג אך נכון. (כדאי לצייר כדי להשתכנע)
הבדיקה נכונה עבור נקודה אחת אדומה ואחת כחולה וגם עבור 2 מכל צבע. נניח שניתן לחבר עבור עד N נקודות אדומות ו N כחולות ונוכיח עבור N+1. לאחר שחיברנו את N הנקודות משני הצבעים נוסיף נקודה אדומה ואחת כחולה. נחבר את הנקודה החדשה האדומה לנקודה הכחולה החדשה (נקרא לישר זה L). נסתכל על הקטע הנחתך (מבין החיבורים הקודמים) הקרוב ביותר לישר L לנקודה האדומה החדשה. ננתק את הקטע הנחתך ונחבר את הנקודה הכחולה שלו לנקודה האדומה החדשה. קטע זה אינו חותך קטעים קודמים בדף. באותה צורה נחבר את הנקודה האדומה מהקטע החיתוך הקרוב לנקודה הכחולה החדשה. גם קטע זה אינו נחתך על ידי הקטעים הקודמים. ננתק את שאר הקטעים שנחתכו ע"י הישר L. (נשאיר את שני הקטים האחרונים שחיברנו לנקודות החדשות) לכל היותר יש N נקודות מכל צבע שנתקנו. (מבין הקטעים שנחתכו ע"י הישר L). לפי הנחת האינדוקציה ניתן לחברם בקטעים שאינם נחתכים. חיבור נקודות אלו לא יחתוך קטעים שלא נחתכו ע"י הישר L.(החיבור יעשה כך: לאחר חיבור שני הקטעים לשתי הנקודות החדשות נחבר את הנקודה הכחולה שנותקה מהקטע לנקודה האדומה שנותקה מהקטע שלה נסתכל על הקטעים שנחתכים על ידי ישר החיבור כמו שתיארנו קודם ונחבר את הקטעים החדשים כפי שתואר קודם). ולכן ניתן לחבר כל כמות בת מניה של נקודות משני צבעים שאין שלושה על ישר אחד. ההסבר קצת עילג אך נכון. (כדאי לצייר כדי להשתכנע)
עריסטו
Active member
כן, אתה טועה
כפי שאמרתי, אם מוסיפים זוג, ועוד זוג, ועוד זוג,... מספר הזוגות עדיין |סופי|. רק הוכחת שלכל מספר |סופי| של זוגות ניתן לחבר. שים לב שלפי מה שאתה כותב, כל טענה שניתן להוכיח את נכונותה לכל קבוצה סופית על ידי אינדוקציה - הינה נכונה גם לקבוצה שעוצמתה א0. אבל קל למצוא טענות שלגביהן זה לא נכון.
כפי שאמרתי, אם מוסיפים זוג, ועוד זוג, ועוד זוג,... מספר הזוגות עדיין |סופי|. רק הוכחת שלכל מספר |סופי| של זוגות ניתן לחבר. שים לב שלפי מה שאתה כותב, כל טענה שניתן להוכיח את נכונותה לכל קבוצה סופית על ידי אינדוקציה - הינה נכונה גם לקבוצה שעוצמתה א0. אבל קל למצוא טענות שלגביהן זה לא נכון.
../images/Emo62.gif לחידת ההמשך
נמספר את הנקודות האדומות מ- 1 ועד אינסוף, ונמספר גם את הנקודות הכחולות באותו אופן. נגדיר עץ אינסופי באופן הבא: ברמה ה- N של העץ יהיו קודקודים כל הדרכים לחבר את נקודות 1..N הכחולות לנקודות 1..N האדומות ללא חיתוכים. ע"פ ההוכחה למקרה הסופי, זו קבוצה לא ריקה. ויש חיבור מקודקוד ברמה ה- N לקודקוד ברמה ה- 1+N אם אין סתירה ביניהם (כלומר נקודות 1..N מחוברות באותו האופן). זהו עץ אינסופי וקשיר, שבו לכל קודקוד יש מספר סופי של בנים- לכן ע"פ הלמה של קניג, יש בו מסלול אינסופי- ומסלול זה מגדיר את העברת הקווים המבוקשת.
נמספר את הנקודות האדומות מ- 1 ועד אינסוף, ונמספר גם את הנקודות הכחולות באותו אופן. נגדיר עץ אינסופי באופן הבא: ברמה ה- N של העץ יהיו קודקודים כל הדרכים לחבר את נקודות 1..N הכחולות לנקודות 1..N האדומות ללא חיתוכים. ע"פ ההוכחה למקרה הסופי, זו קבוצה לא ריקה. ויש חיבור מקודקוד ברמה ה- N לקודקוד ברמה ה- 1+N אם אין סתירה ביניהם (כלומר נקודות 1..N מחוברות באותו האופן). זהו עץ אינסופי וקשיר, שבו לכל קודקוד יש מספר סופי של בנים- לכן ע"פ הלמה של קניג, יש בו מסלול אינסופי- ומסלול זה מגדיר את העברת הקווים המבוקשת.
MelodicTruth
New member
פתרון פשוט (למקרה הסופי והאינסופי)
נצייר פרבולה, ונחצה אותה באמצע. נבחר 1000 ערכים של y, ונסמן את כל ה-x המתאימים בצד אחד באדום, ובשני בכחול. נחבר כל שתי נקודות בעלות ערך זהה של y, ונקבל 1000 קווים שאינם חוצים אחד את השני, וקל לראות שאין שלוש נקודות על אותו ישר. קל לראות כי הפתרון תקף עבור כל א0^2>k נקודות.
נצייר פרבולה, ונחצה אותה באמצע. נבחר 1000 ערכים של y, ונסמן את כל ה-x המתאימים בצד אחד באדום, ובשני בכחול. נחבר כל שתי נקודות בעלות ערך זהה של y, ונקבל 1000 קווים שאינם חוצים אחד את השני, וקל לראות שאין שלוש נקודות על אותו ישר. קל לראות כי הפתרון תקף עבור כל א0^2>k נקודות.
MelodicTruth
New member
אופס, לא קראתי בעיון את השאלה.
תתעלמו
תתעלמו
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.