טבלה
- פותח הנושא עריסטו
- פורסם בתאריך
אני לא בטוח...
אבל יש פה נדמה לי עקרון שובך היונים. אם נניח יש כוכבית אחת בכל עמודה, אז באחת או יותר מן השורות חייבת להיות יותר מכוכבית אחת. כל עוד נוסיף כוכביות בעמודה שבה יש את הכוכבית עם היותר כוכביות בשורתה מבעמודתה, הכוכבית החדשה תעלה את מספר הכוכביות בשורה של עצמה. אני כמעט בטוח שלא הוכחתי נכון, אבל לפחות ניסיתי.. .
אבל יש פה נדמה לי עקרון שובך היונים. אם נניח יש כוכבית אחת בכל עמודה, אז באחת או יותר מן השורות חייבת להיות יותר מכוכבית אחת. כל עוד נוסיף כוכביות בעמודה שבה יש את הכוכבית עם היותר כוכביות בשורתה מבעמודתה, הכוכבית החדשה תעלה את מספר הכוכביות בשורה של עצמה. אני כמעט בטוח שלא הוכחתי נכון, אבל לפחות ניסיתי.. .
The6thAngel
New member
../images/Emo62.gif
נתחיל לשבץ כוכביות בעמודות. בכל עמודה נשתמש בשורה שונה, עד שנשבץ M כוכביות, כל כוכבית בשורה שונה ועמודה שונה. כשנגיע לכוכבית M+1 (ומכיוון ש-N גדול מ-M, קיימת כוכבית M+1) היא תהיה חייבת להיות הכוכבית השנייה באותה שורה. מסקנה: יש לפחות שורה אחת עם 2 כוכביות. אם נוסיף לעמודה מסויימת כוכבית שניה, זה אומר שבאותה שורה יהיו כבר לפחות 2 כוכביות, כשהכוכבית הנמצאת באותה שורה תהיה היחידה בעמודתה, עם לפחות 2 כוכביות בשורה, וכך מקיימת את התנאי. וכך כל פעם שנוסיף כוכביות, "נפתור" בעיה של כוכבית אחת, אבל תהיה לנו בעיה עם הכוכבית החדשה... וככה נוסיף עוד ועוד כוכביות, עד שנמלא את כל המשבצות כוכביות, ומכיוון שיש יותר עמודות משורות - בשורה יהיו יותר כוכביות מבעמודה. המקרה היחיד של איזון בין מספר הכוכביות בעמודות ובשורות יהיה כש M=N, וזה לא המקרה... זה נחשב הוכחה? קצת מסובך להסביר...
נתחיל לשבץ כוכביות בעמודות. בכל עמודה נשתמש בשורה שונה, עד שנשבץ M כוכביות, כל כוכבית בשורה שונה ועמודה שונה. כשנגיע לכוכבית M+1 (ומכיוון ש-N גדול מ-M, קיימת כוכבית M+1) היא תהיה חייבת להיות הכוכבית השנייה באותה שורה. מסקנה: יש לפחות שורה אחת עם 2 כוכביות. אם נוסיף לעמודה מסויימת כוכבית שניה, זה אומר שבאותה שורה יהיו כבר לפחות 2 כוכביות, כשהכוכבית הנמצאת באותה שורה תהיה היחידה בעמודתה, עם לפחות 2 כוכביות בשורה, וכך מקיימת את התנאי. וכך כל פעם שנוסיף כוכביות, "נפתור" בעיה של כוכבית אחת, אבל תהיה לנו בעיה עם הכוכבית החדשה... וככה נוסיף עוד ועוד כוכביות, עד שנמלא את כל המשבצות כוכביות, ומכיוון שיש יותר עמודות משורות - בשורה יהיו יותר כוכביות מבעמודה. המקרה היחיד של איזון בין מספר הכוכביות בעמודות ובשורות יהיה כש M=N, וזה לא המקרה... זה נחשב הוכחה? קצת מסובך להסביר...
יאיר של תמר
New member
נסיון חלקי
אם Rx הוא מספר הכוכביות בשורה x. ו - Cx הוא מספר הכוביות בשורה y. יש לנו R1 + R2 + ... + Rn = C1 + C2 + ... + Cm מצד שמאל של המשוואה יש פחות מחוברים מאשר בצד ימין (ואף אחד מהם לא 0). אם כל אחד מהמחוברים בצד ימין היה גדול או שווה מכל אחד מהמחוברים בצד שמאל אז, לא היה מתקבל שוויון. הוכחתי שקיימת שורה שיש בה יותר כוכביות מאחת העמודות - אך לא התייחסתי לדרישה, שבאותו השורה והעמודה תהיה כוכבית - כמתבקש בשאלה. ניתן להעמיק יותר, ולהגיע לזה..- אבל עוד לא מצאתי משהו אלגנטי..
אם Rx הוא מספר הכוכביות בשורה x. ו - Cx הוא מספר הכוביות בשורה y. יש לנו R1 + R2 + ... + Rn = C1 + C2 + ... + Cm מצד שמאל של המשוואה יש פחות מחוברים מאשר בצד ימין (ואף אחד מהם לא 0). אם כל אחד מהמחוברים בצד ימין היה גדול או שווה מכל אחד מהמחוברים בצד שמאל אז, לא היה מתקבל שוויון. הוכחתי שקיימת שורה שיש בה יותר כוכביות מאחת העמודות - אך לא התייחסתי לדרישה, שבאותו השורה והעמודה תהיה כוכבית - כמתבקש בשאלה. ניתן להעמיק יותר, ולהגיע לזה..- אבל עוד לא מצאתי משהו אלגנטי..
יאיר של תמר
New member
טעות*
- Cx הוא מספר הכוביות בעמודה x .
- Cx הוא מספר הכוביות בעמודה x .
יאיר של תמר
New member
כיוון להעברת הבעייה ל"מקום" אחר...
אבל אני חייב לרוץ...אז אולי מישהו רוצה להמשיך.... אפשר להעביר את הבעייה לתורת הגרפים...
אבל אני חייב לרוץ...אז אולי מישהו רוצה להמשיך.... אפשר להעביר את הבעייה לתורת הגרפים...
נסיון
ברור שיש שורה עם לפחות שני כוכביות. נבחר את השורה עם הכי הרבה כוכביות (אחת מהן). בכל אחת מהעמודות המתאימות לכוכביות הנ"ל יש לפחות את מספר הכוכביות שיש בשורה הזאת.!! נמחוק את השורה הנ"ל ואת העמודה עם מספר הכוכביות הגדול ביותר.( אחת מהן אם יש כמה). חזרנו לבעיה המקורית אלא שהורדנו שורה אחת ועמודה אחת. עדיין הטבלה חייבת לקיים שבכל עמודה יש לפחות כוכבית אחת. (יש לפחות שורה אחת עם שני כוכביות). נמשיך בתהליך. מש"ל.
ברור שיש שורה עם לפחות שני כוכביות. נבחר את השורה עם הכי הרבה כוכביות (אחת מהן). בכל אחת מהעמודות המתאימות לכוכביות הנ"ל יש לפחות את מספר הכוכביות שיש בשורה הזאת.!! נמחוק את השורה הנ"ל ואת העמודה עם מספר הכוכביות הגדול ביותר.( אחת מהן אם יש כמה). חזרנו לבעיה המקורית אלא שהורדנו שורה אחת ועמודה אחת. עדיין הטבלה חייבת לקיים שבכל עמודה יש לפחות כוכבית אחת. (יש לפחות שורה אחת עם שני כוכביות). נמשיך בתהליך. מש"ל.
הסבר
אם הכוונה היא לשורה השלישית הזאת: בכל אחת מהעמודות המתאימות לכוכביות הנ"ל יש לפחות את מספר הכוכביות שיש בשורה הזאת.!! אם קיימת עמודה (שבה יש כוכבית בשורה המקסימלית) שבה מספר הכוכביות קטן ממספר הכוכביות שבשורה הנ"ל יתקיים התנאי שיש שורה כזאת (השורה המקסימלית המתאימה לכוכבית הנ"ל) שיש בה יותר כוכביות מאשר בעמודה שלה. כלומר נסתכל על הכוכבית בשורה המקסימלית, שמספר הכוכביות בעמודה המתאימה לה קטן מזה שבשורה המקסימלית ויתקיים מה שרצית להוכיח.
אם הכוונה היא לשורה השלישית הזאת: בכל אחת מהעמודות המתאימות לכוכביות הנ"ל יש לפחות את מספר הכוכביות שיש בשורה הזאת.!! אם קיימת עמודה (שבה יש כוכבית בשורה המקסימלית) שבה מספר הכוכביות קטן ממספר הכוכביות שבשורה הנ"ל יתקיים התנאי שיש שורה כזאת (השורה המקסימלית המתאימה לכוכבית הנ"ל) שיש בה יותר כוכביות מאשר בעמודה שלה. כלומר נסתכל על הכוכבית בשורה המקסימלית, שמספר הכוכביות בעמודה המתאימה לה קטן מזה שבשורה המקסימלית ויתקיים מה שרצית להוכיח.
עריסטו
Active member
טוב, הבה נראה
אם הבנתי נכון, ההוכחה היא כך: נבחר את השורה עם מספר הכוכביות המקסימלי. נניח שזו שורה p, שהכוכביות נמצאות בטורים a,b,c,...,z, ושמספר הכוכביות הוא x. יש שתי אפשרויות: א. אם באחד הטורים האלה יש פחות מ-x כוכביות - סיימנו. ב. אחרת, נבחר מבין הטורים האלה את הטור בו מספר הכוכביות מקסימלי. נניח שזה טור a. נמחק מהטבלה את שורה p ואת טור a. קיבלנו טבלה חדשה, קטנה מהקודמת, שגם בה מספר הטורים גדול ממספר השורות (זה ברור) וגם בה יש כוכבית בכל טור (אני חושב שגם זה נכון). נמשיך באותו תהליך עם הטבלה החדשה. בשלב כלשהו תתקיים לראשונה אפשרות א', שהרי בטבלה בעלת שורה אחת היא מתקיימת. (עכשיו מגיע מה שלא מובן לי) למה זה אומר משהו על הטבלה המקורית?
אם הבנתי נכון, ההוכחה היא כך: נבחר את השורה עם מספר הכוכביות המקסימלי. נניח שזו שורה p, שהכוכביות נמצאות בטורים a,b,c,...,z, ושמספר הכוכביות הוא x. יש שתי אפשרויות: א. אם באחד הטורים האלה יש פחות מ-x כוכביות - סיימנו. ב. אחרת, נבחר מבין הטורים האלה את הטור בו מספר הכוכביות מקסימלי. נניח שזה טור a. נמחק מהטבלה את שורה p ואת טור a. קיבלנו טבלה חדשה, קטנה מהקודמת, שגם בה מספר הטורים גדול ממספר השורות (זה ברור) וגם בה יש כוכבית בכל טור (אני חושב שגם זה נכון). נמשיך באותו תהליך עם הטבלה החדשה. בשלב כלשהו תתקיים לראשונה אפשרות א', שהרי בטבלה בעלת שורה אחת היא מתקיימת. (עכשיו מגיע מה שלא מובן לי) למה זה אומר משהו על הטבלה המקורית?
יאיר של תמר
New member
פיתרון (מקווה!) אך לא אלגנטי להחריד...
OK... הוכחה - לא אלגנטית. המצב ההתחלתי המינימלי הוא שישנה כוכבית אחת בכל עמודה.לאחר מכן, ניתן להוסיף כוכביות בכל מקום. במצב ההתחלתי קיימת שורה שיש בה 2 כוכביות, ובכל השורות האחרות כוכבית אחת. במצב ההתחלתי המינימלי : עבור כל כוכבית במיקום x,y - סכום העמודה (מספר הכוכביות בעמודה שיסומן Cx) הוא 1. וסכום השורה (שיסומן ב Ry) הוא 1. למעט שתי כוכביות שעבורן Ry הוא 2 (Cx עדיין 1). הוספת כוכבית: הוספת כוכבית במיקום x,y מוסיפה 1 לעמודה Cx ומוסיפה 1 לשורה Ry. הטענה | סדגש| בכל זמן נתון, קיימות 2 כוכביות שעבורן R>C. ועבור האחרות R>=C במצב ההתחלתי המינימלי שתי הכוכביות שעבורן R>C נמצאות באותה השורה (הוזכרו למעלה)...וכל האחרות C=R=1 נניח שהכוכביות האלה נמצאות במיקום i,j ו - k,l. נוסיף כוכבית במיקום x,y. אם הכוכבית איננה בשורה l או j, ולא בעמודה i או k, אז פשוט Cx ו-Ry גדלים ב-1, והם עדיין שווים. הוספת כוכבית בעמודה j (או k), הופכת את הכוכבי(ו)ת באותה השורה (וחייבות להיות שם כוכביות, כי בכל שורה ישנה לפחות כוכבית אחת) שהיו עד עתה בסטטוס של C=R ל- C<R (כי R גדל ב-1). הוספת כוכבית בשורה i (או k), ברור שרק מגדילה את הפער בין C ל-R (לטובת R) עבור כוכבית i,j (או k,l). למעשה הראנו, שיש שתי כוכביות במצב הרצוי, והוספת כוכבית יכולה להחליפם בכוכביות אחרות רצויות, או להשאיר את המצב כמות שהוא.
OK... הוכחה - לא אלגנטית. המצב ההתחלתי המינימלי הוא שישנה כוכבית אחת בכל עמודה.לאחר מכן, ניתן להוסיף כוכביות בכל מקום. במצב ההתחלתי קיימת שורה שיש בה 2 כוכביות, ובכל השורות האחרות כוכבית אחת. במצב ההתחלתי המינימלי : עבור כל כוכבית במיקום x,y - סכום העמודה (מספר הכוכביות בעמודה שיסומן Cx) הוא 1. וסכום השורה (שיסומן ב Ry) הוא 1. למעט שתי כוכביות שעבורן Ry הוא 2 (Cx עדיין 1). הוספת כוכבית: הוספת כוכבית במיקום x,y מוסיפה 1 לעמודה Cx ומוסיפה 1 לשורה Ry. הטענה | סדגש| בכל זמן נתון, קיימות 2 כוכביות שעבורן R>C. ועבור האחרות R>=C במצב ההתחלתי המינימלי שתי הכוכביות שעבורן R>C נמצאות באותה השורה (הוזכרו למעלה)...וכל האחרות C=R=1 נניח שהכוכביות האלה נמצאות במיקום i,j ו - k,l. נוסיף כוכבית במיקום x,y. אם הכוכבית איננה בשורה l או j, ולא בעמודה i או k, אז פשוט Cx ו-Ry גדלים ב-1, והם עדיין שווים. הוספת כוכבית בעמודה j (או k), הופכת את הכוכבי(ו)ת באותה השורה (וחייבות להיות שם כוכביות, כי בכל שורה ישנה לפחות כוכבית אחת) שהיו עד עתה בסטטוס של C=R ל- C<R (כי R גדל ב-1). הוספת כוכבית בשורה i (או k), ברור שרק מגדילה את הפער בין C ל-R (לטובת R) עבור כוכבית i,j (או k,l). למעשה הראנו, שיש שתי כוכביות במצב הרצוי, והוספת כוכבית יכולה להחליפם בכוכביות אחרות רצויות, או להשאיר את המצב כמות שהוא.
יאיר של תמר
New member
תיקונים קלים*
הנחתי N=M+1 אבל ניתן בקלות להכליל ל N=M+Q. מצטער ש"התפקששו" לי ההדגשות
הנחתי N=M+1 אבל ניתן בקלות להכליל ל N=M+Q. מצטער ש"התפקששו" לי ההדגשות
יאיר של תמר
New member
קבל ביטול - אוף!!!!
שכחתי שניתן לשים את כל הכוכביות באותה שורה, ולא חייבים לחלק אותם בין השורות!!!!
שכחתי שניתן לשים את כל הכוכביות באותה שורה, ולא חייבים לחלק אותם בין השורות!!!!
עריסטו
Active member
מצאתי שתי טעמות חזקות יותר
מצאתי שתי דרכים לחזק את הטענה שבחידה: א. הטענה נכונה גם אם מותר שתהיה במשבצת יותר מכוכבית אחת. ב. גם בחידה המקורית וגם ב"חידה המחוזקת" שבסעיף הקודם, למעשה יש לפחות n-m+1 כוכביות המקיימות את הטענה (קל להראות שאי אפשר להחליף את המספר n-m+1 במבפר גדול יותר). נסו להוכיח...
מצאתי שתי דרכים לחזק את הטענה שבחידה: א. הטענה נכונה גם אם מותר שתהיה במשבצת יותר מכוכבית אחת. ב. גם בחידה המקורית וגם ב"חידה המחוזקת" שבסעיף הקודם, למעשה יש לפחות n-m+1 כוכביות המקיימות את הטענה (קל להראות שאי אפשר להחליף את המספר n-m+1 במבפר גדול יותר). נסו להוכיח...
The6thAngel
New member
ניסיון נוסף
קודם כל אני אשבץ מינימום כוכביות כדי לקיים את התנאי של כוכבית לכל עמודה. את M הכוכביות הראשונות אני אשבץ כוכבית אחת בכל שורה, כדי שלא יהיה מצב של יותר כוכביות בשורות מעמודות. את כוכבית ה-M+1 (שהוכחתי שקיימת בפעם הקודמת) אני אהיה חייבת לשבץ בשורה שכבר קיימת בה כוכבית (כי כל השורות כבר מלאות), ובעמודה ריקה (כי אני צריכה למלא את כל העמודות). כלומר יש שתי משבצות, הנמצאות באותה שורה, כל אחד מהן יחידה בעמודתה, ושתיהן מקיימות את התנאי (זה במקרה של מינימום כוכביות ומינימום הפרש בין עמודות לשורות ומקיים N-M+1 כוכביות, כלומר 2 במקרה זה, שמקיימות את התנאי. נמשיך הלאה. כל עמודה נוספת שקיימת, תוסיף למאזן הכוכביות (כי כאמור, אין שורות ריקות מכוכביות, אבל כל עמודה נוספת היא ריקה), ועדיין תהיה כוכבית אחת בכל עמודה ולכן ככל שההפרש בין העמודות לשורות יקטן, ככה יהיו פחות כוכביות שמקיימות את התנאי. נראה איך אנחנו יכולים להוסיף כוכביות לעמודה כדי לבטל את התנאי. כאמור, יש 2 כוכביות שמקיימות את התנאי. נקרא להן X ו-Y. נוסיף לאחת מהן (נניח X) כוכבית נוספת בעמודה. עדיין מתקיים התנאי ל-2 כוכביות - כוכבית Y, והכוכבית שנמצאת באותה שורה עם הכוכבית החדשה (מכיוון שאמרנו שבכל שורה יש לפחות כוכבית אחת). אפשר להמשיך להוסיף כוכביות, כדי לאזן 2 כוכביות בכל שורה, אבל בסוף תישאר כוכבית אחת שאי אפשר לאזן, כי חסרה שורה, ואז תהיה שורה אחת של 3 כוכביות בשורה (ו-2 בעמודה). ואז לנסות לאזן ל-3, ושוב תהיה חסרה שורה ונעבור ל-4. וכו וכו עד שנגיע למצב שכל העמודות מלאות כוכביות, אבל עדיין השורות ארוכות יותר, ולכן תהיה כוכבית עם יותר כוכביות בשורה מאשר בעמודה. כל ניסיון להוסיף כוכבית לאותה משבצת יהיה מיותר. הוא אמנם יגדיל את מספר הכוכביות בעמודה, אבל כך גם את מספר הכוכביות בשורה, ועדיין תהיה חסרה כוכבית... אגב, יש לך טעות. זה לא N-M+1, זה רק N-M (הוכחתי מקרה שזה לא מתקיים...)
קודם כל אני אשבץ מינימום כוכביות כדי לקיים את התנאי של כוכבית לכל עמודה. את M הכוכביות הראשונות אני אשבץ כוכבית אחת בכל שורה, כדי שלא יהיה מצב של יותר כוכביות בשורות מעמודות. את כוכבית ה-M+1 (שהוכחתי שקיימת בפעם הקודמת) אני אהיה חייבת לשבץ בשורה שכבר קיימת בה כוכבית (כי כל השורות כבר מלאות), ובעמודה ריקה (כי אני צריכה למלא את כל העמודות). כלומר יש שתי משבצות, הנמצאות באותה שורה, כל אחד מהן יחידה בעמודתה, ושתיהן מקיימות את התנאי (זה במקרה של מינימום כוכביות ומינימום הפרש בין עמודות לשורות ומקיים N-M+1 כוכביות, כלומר 2 במקרה זה, שמקיימות את התנאי. נמשיך הלאה. כל עמודה נוספת שקיימת, תוסיף למאזן הכוכביות (כי כאמור, אין שורות ריקות מכוכביות, אבל כל עמודה נוספת היא ריקה), ועדיין תהיה כוכבית אחת בכל עמודה ולכן ככל שההפרש בין העמודות לשורות יקטן, ככה יהיו פחות כוכביות שמקיימות את התנאי. נראה איך אנחנו יכולים להוסיף כוכביות לעמודה כדי לבטל את התנאי. כאמור, יש 2 כוכביות שמקיימות את התנאי. נקרא להן X ו-Y. נוסיף לאחת מהן (נניח X) כוכבית נוספת בעמודה. עדיין מתקיים התנאי ל-2 כוכביות - כוכבית Y, והכוכבית שנמצאת באותה שורה עם הכוכבית החדשה (מכיוון שאמרנו שבכל שורה יש לפחות כוכבית אחת). אפשר להמשיך להוסיף כוכביות, כדי לאזן 2 כוכביות בכל שורה, אבל בסוף תישאר כוכבית אחת שאי אפשר לאזן, כי חסרה שורה, ואז תהיה שורה אחת של 3 כוכביות בשורה (ו-2 בעמודה). ואז לנסות לאזן ל-3, ושוב תהיה חסרה שורה ונעבור ל-4. וכו וכו עד שנגיע למצב שכל העמודות מלאות כוכביות, אבל עדיין השורות ארוכות יותר, ולכן תהיה כוכבית עם יותר כוכביות בשורה מאשר בעמודה. כל ניסיון להוסיף כוכבית לאותה משבצת יהיה מיותר. הוא אמנם יגדיל את מספר הכוכביות בעמודה, אבל כך גם את מספר הכוכביות בשורה, ועדיין תהיה חסרה כוכבית... אגב, יש לך טעות. זה לא N-M+1, זה רק N-M (הוכחתי מקרה שזה לא מתקיים...)
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.