פורטל:מתמטיקה/חידה/49

נתון מערך בן $\ n$ איברים, שבו שובצו $\ n$ מספרים טבעיים שונים, מתוך הטווח 1 ועד $\ n+1$ . יש למצוא את המספר הטבעי בטווח זה שלא שובץ, וזאת במעבר אחד בלבד על המערך.

פתרון

במעבר על המערך מסכמים את כל המספרים הרשומים בו, ואת התוצאה מפחיתים מסכום הטור

\ 1...n+1

(שאותו נחשב לפי הנוסחה לסכום טור חשבוני). התוצאה היא המספר המבוקש.

וכעת לחידת בונוס:

נתון מערך בן $\ n$ איברים, שבו שובצו $\ n$ מספרים טבעיים שונים, מתוך הטווח 1 ועד $\ n+2$ . יש למצוא את שני המספרים הטבעיים בטווח זה שלא שובצו, וזאת במעבר אחד בלבד על המערך.

פתרון

במעבר על המערך מסכמים את כל המספרים הרשומים בו, ואת התוצאה מפחיתים מסכום הטור

\ 1...n+2

(שאותו נחשב לפי הנוסחה לסכום טור חשבוני). ההפרש הוא סכום שני המספרים המבוקשים. בנוסף לכך, באותו מעבר גם מכפילים את איברי המערך זה בזה, והתוצאה תחלק את

\ (n+2)!

. המנה היא מכפלת שני המספרים המבוקשים. קיבלנו שתי משוואות בשני נעלמים, שפתרונן ייתן את שני המספרים המבוקשים.

וישנו גם פתרון נוסף, שאינו מצריך חישובים עם מספרים גדולים. נסמן את המספרים החסרים ב- $\ a,b$ . במעבר על המערך נחשב את הסכום וכן את סכום הריבועים של כל המספרים המופיעים בו. אם נחסר אותם בהתאמה מסכום כל המספרים ומסכום כל ריבועי המספרים בטווח $\ 1...n+2$ , נקבל את $\ a+b$ ואת $\ a^{2}+b^{2}$ בהתאמה. כידוע, $\ (a+b)^{2}+(a-b)^{2}=2*(a^{2}+b^{2})$ , ומכאן ניתן לדעת גם את ההפרש בין המספרים. קיבלנו שתי משוואות פשוטות - סכום המספרים והפרשם. מכאן ניתן לדעת את ערכם המדויק.