n פעמים n
- פותח הנושא עריסטו
- פורסם בתאריך
עריסטו
Active member
לא מובן!!!
"הפעולה הזאת מבוצעת פעמיים (שני זוגות של 4), שאחר כך מחברים אותם ומחלקים שוב ב-4" - מי אמר לך שדווקא כך "ממזגים" את המספרים? אסביר שוב את החידה: בכל צעד בוחרים שני מספרים כלשהם, מוחקים אותם, ובמקומם כותבים רבע מסכומם. צריך להוכיח שלא משנה איזה מספרים נבחרו בכל שלב, התוצאה הסופית תהיה תמיד גדולה או שווה ל - 1.
"הפעולה הזאת מבוצעת פעמיים (שני זוגות של 4), שאחר כך מחברים אותם ומחלקים שוב ב-4" - מי אמר לך שדווקא כך "ממזגים" את המספרים? אסביר שוב את החידה: בכל צעד בוחרים שני מספרים כלשהם, מוחקים אותם, ובמקומם כותבים רבע מסכומם. צריך להוכיח שלא משנה איזה מספרים נבחרו בכל שלב, התוצאה הסופית תהיה תמיד גדולה או שווה ל - 1.
רשמתי כבר
ההוכחה שלי היא רק חלקית, ומתאימה למספרים מהצורה z 2^x z, שעבורם, תמיד ניתן לחלק לזוגות באופן דומה לחילוק ה-4 לזוגות. אם כוונתך היא שגם עבור המספרים מהצורה z 2^x z, צריך להוכיח גם עבור מקרים שהזוגות הנבחרים אינם מהצורה שרשמתי, אז מצטער, הפתרון (החלקי) שלי באמת לא נכון גם במקרה הזה, אבל זה לא ממש השתמע מהחידה.. אנסה שוב עוד מעט..
ההוכחה שלי היא רק חלקית, ומתאימה למספרים מהצורה z 2^x z, שעבורם, תמיד ניתן לחלק לזוגות באופן דומה לחילוק ה-4 לזוגות. אם כוונתך היא שגם עבור המספרים מהצורה z 2^x z, צריך להוכיח גם עבור מקרים שהזוגות הנבחרים אינם מהצורה שרשמתי, אז מצטער, הפתרון (החלקי) שלי באמת לא נכון גם במקרה הזה, אבל זה לא ממש השתמע מהחידה.. אנסה שוב עוד מעט..
אבל..
אבל בכל מקרה, המצב שתיארתי (כלומר, בחירת המספרים לפי חלוקה לזוגות כל פעם) הוא מצב קיצון מינימלי, שהרי כל פעם לוקחים את המספר הקטן ביותר שניתן להשיג בפעולה אחת, מוסיפים לו אותו מספר (הקטן ביותר שניתן להשיג...), ומחלקים ב-4. כך שברור שאם ניקח את המספר הקטן ביותר שניתן להשיג בפעולה אחת, ונחבר לו את n לדוגמא, ואחר כך נחלק ב-4, נקבל מספר גדול יותר מהמספר שקיבלנו במצב הקודם, שהרי n/2+n/2<n/2+n.. אני חושב.. יכול להיות שהיה לי איזשהו בלבול..
אבל בכל מקרה, המצב שתיארתי (כלומר, בחירת המספרים לפי חלוקה לזוגות כל פעם) הוא מצב קיצון מינימלי, שהרי כל פעם לוקחים את המספר הקטן ביותר שניתן להשיג בפעולה אחת, מוסיפים לו אותו מספר (הקטן ביותר שניתן להשיג...), ומחלקים ב-4. כך שברור שאם ניקח את המספר הקטן ביותר שניתן להשיג בפעולה אחת, ונחבר לו את n לדוגמא, ואחר כך נחלק ב-4, נקבל מספר גדול יותר מהמספר שקיבלנו במצב הקודם, שהרי n/2+n/2<n/2+n.. אני חושב.. יכול להיות שהיה לי איזשהו בלבול..
עריסטו
Active member
אני לא חושב שזו הוכחה
העובדה שבכל צעד אתה עושה את הפעולה האופטימלית באופן מקומי אינה מוכיחה שהתוצאה הסופית היא האופטימלית (כלומר מינימלית), כי מה שאתה עושה בכל צעד משפיע על הצעדים הבאים - הרי אתה "מייצר" מספר שתשתמש בו אחר כך. מי אמר לך שאתה לא יכול "לבזבז" בצעד מסויים, כלומר לא לעשות את הצעד האופטימלי, ובהמשך תרוויח מזה?
העובדה שבכל צעד אתה עושה את הפעולה האופטימלית באופן מקומי אינה מוכיחה שהתוצאה הסופית היא האופטימלית (כלומר מינימלית), כי מה שאתה עושה בכל צעד משפיע על הצעדים הבאים - הרי אתה "מייצר" מספר שתשתמש בו אחר כך. מי אמר לך שאתה לא יכול "לבזבז" בצעד מסויים, כלומר לא לעשות את הצעד האופטימלי, ובהמשך תרוויח מזה?
הנה פתרון, אם הבנתי את החידה נכון
נראה פשוט, לא? הנה הניסיון שלי: NNNNNNNN....NN אנחנו מניחים שיש מספר זוגי של איברים כי אם היה מס' אי זוגי התוצאה הסופית גדולה בכל מקרה מN ועובדה היא שN>1. אם ישנו מס' זוגי של איברים, הרי שמבצעים את הפעולה האמורה (חיבור שני איברים סמוכים וחילוקם בארבע) N/2 פעמים. מכאן ש: N/2*N/4 זהו חישוב של הפעולה שאנחנו מבצעים כפול מס' הפעמים שמבצעים אותה. למעשה, זהו חיבור כל האיברים לאחר פעולת החיבור והחילוק. התוצאה היא N*N/4. מכיוון שהנחת היסוד ביחס למס' איברים זוגי - המס' המינימלי של N הוא 2. לפי N=2 התוצאה של כל החיבור חילוק חיבור הזה היא 1. אם N גדול מ2, התוצאה גדולה מ1. הנה הוכחה. מצטער שהניסוח הוא מילולי ומסורבל. בכתיב מתמטי נורמלי זה שתי שורות, אבל אני לא יודע איך לכתוב את זה כן במחשב.
נראה פשוט, לא? הנה הניסיון שלי: NNNNNNNN....NN אנחנו מניחים שיש מספר זוגי של איברים כי אם היה מס' אי זוגי התוצאה הסופית גדולה בכל מקרה מN ועובדה היא שN>1. אם ישנו מס' זוגי של איברים, הרי שמבצעים את הפעולה האמורה (חיבור שני איברים סמוכים וחילוקם בארבע) N/2 פעמים. מכאן ש: N/2*N/4 זהו חישוב של הפעולה שאנחנו מבצעים כפול מס' הפעמים שמבצעים אותה. למעשה, זהו חיבור כל האיברים לאחר פעולת החיבור והחילוק. התוצאה היא N*N/4. מכיוון שהנחת היסוד ביחס למס' איברים זוגי - המס' המינימלי של N הוא 2. לפי N=2 התוצאה של כל החיבור חילוק חיבור הזה היא 1. אם N גדול מ2, התוצאה גדולה מ1. הנה הוכחה. מצטער שהניסוח הוא מילולי ומסורבל. בכתיב מתמטי נורמלי זה שתי שורות, אבל אני לא יודע איך לכתוב את זה כן במחשב.
נסיון
נשים לב שניתן להוציא את המספר N כאילו מבחוץ לסוגרים ולשאול את השאלה כך- יהיו 1+1+1+1+1+1...N פעמים האם ניתן בעזרת אינטרקציה (שנכתבה בשאלה) להגיע למספר קטן יותר מ- 1 חלקי N? עכשיו נחזור לשאלה המקורית-- ונניח-- כי קיים N כך שכל המספרים שמתחתיו מקיימים את השאלה, ונחלק את הקבוצה הגדולה של ה-Nים לשתי קבוצות- 1-> N N N N ... פעמים-A 2-> N N N N פעמים -N-A על פי ההנחה שלמעלה והמשפט שבתחילת ההודעה שלי ניתן להגיד כי לקבוצה 1 יש לפחות (בכל דרך של אינטראקציות) N חלקי A. ולקבוצה 2 N חלקי (N-A) ולכן באינטראקציה הסופית נקבל (N/A+N/(N-A)/4 (לא מסתדר לי הכתיבה אז פשוט תעשו אינטראקציה לערך המינימאלי של כל קבוצה) ונבדוק מתי הערך הזה יהיה גדול או שווה ל-1 N^2>=4NA-4A^2 (N-2A)^2>=0 כאשר N>A ואז כאשר בודקים ל-1 נובע שזה נכון ל-2 וכו.
נשים לב שניתן להוציא את המספר N כאילו מבחוץ לסוגרים ולשאול את השאלה כך- יהיו 1+1+1+1+1+1...N פעמים האם ניתן בעזרת אינטרקציה (שנכתבה בשאלה) להגיע למספר קטן יותר מ- 1 חלקי N? עכשיו נחזור לשאלה המקורית-- ונניח-- כי קיים N כך שכל המספרים שמתחתיו מקיימים את השאלה, ונחלק את הקבוצה הגדולה של ה-Nים לשתי קבוצות- 1-> N N N N ... פעמים-A 2-> N N N N פעמים -N-A על פי ההנחה שלמעלה והמשפט שבתחילת ההודעה שלי ניתן להגיד כי לקבוצה 1 יש לפחות (בכל דרך של אינטראקציות) N חלקי A. ולקבוצה 2 N חלקי (N-A) ולכן באינטראקציה הסופית נקבל (N/A+N/(N-A)/4 (לא מסתדר לי הכתיבה אז פשוט תעשו אינטראקציה לערך המינימאלי של כל קבוצה) ונבדוק מתי הערך הזה יהיה גדול או שווה ל-1 N^2>=4NA-4A^2 (N-2A)^2>=0 כאשר N>A ואז כאשר בודקים ל-1 נובע שזה נכון ל-2 וכו.
עריסטו
Active member
../images/Emo127.gif פשוט נהדר!
זו לא ההוכחה שלי אבל זו הוכחה יפהפיה.
להלן אנסה לנסח את הוכחתך בצורה ברורה יותר. ____________________________________________ נוכיח טענה שונה מעט מהטענה שבשאלה: אם מתחילים מ - n מספרים שכל אחד מהם שווה ל - m, אזי התוצאה הסופית היא לפחות m/n. הוכחה - באינדוקציה על n. אם n=1 הטענה נכונה. אם n>1: נניח שהטענה נכונה עבור כל n חיובי וקטן מ - k מסויים (עבור כל m) ונוכיח בהסתמך על ההנחה שהטענה נכונה עבור n=k (עבור כל m), כלומר שכאשר מתחילים מ-k מספרים שכל אחד מהם שווה ל-m התוצאה הסופית היא לפחות m/k. פעולת המיזוג האחרונה מתבצעת בין תוצאת המיזוג של a מספרים שכל אחד מהם שווה ל - m ותוצאת המיזוג של k-a מספרים שכל אחד מהם שווה ל - m. מכיוון ש - a ו- k-a קטנים מ-k, ניתן להשמתמש בהנחת האינדוקציה שלפיה תוצאת המיזוג של a המספרים היא לפחות m/a ותוצאת המיזוג של k-a המספרים היא לפחות Z m/(k-a) Z לכן תוצאת המיזוג הסופי היא לפחות Z mk/(4a*(k-a)) Z המונה והמכנה של הביטוי האחרון חיוביים תמיד, לכן ערך הביטוי מינימלי כאשר ערך המכנה מקסימלי. זה קורה כאשר a=k/2, ואז ערך הביטוי הוא m/k, כדרוש.
זו לא ההוכחה שלי אבל זו הוכחה יפהפיה.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.