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

האם קיימת קבוצה אינסופית של מספרים טבעיים, כך שבכל תת-קבוצה סופית לא ריקה שלה סכום האיברים אינו ריבוע של מספר שלם?

פתרון

פתרון ראשון

קבוצה כזו קיימת, למשל - החזקות של 10 עם מעריך אי-זוגי: 10, 1000, 100000, 10000000,... סכום האיברים בכל תת-קבוצה לא ריקה מסתיים במספר אי-זוגי של אפסים. לעומת זאת ריבוע של שלם מסתיים במספר זוגי של אפסים (כי מספר האפסים מכפיל את עצמו בעת העלאה בריבוע).

פתרון שני

נגדיר סדרה של מספרים טבעיים באופן רקורסיבי באופן הבא: $a_{1}=2,a_{n+1}=a_{n}^{2}+1$ . כל מספר בקבוצה הזו הוא מצורה $k^{2}+1$ . עבור כל תת-קבוצה סופית שנבחר נסתכל על המספר הגדול ביותר בה, שנסמנו $a_{max}=k^{2}+1$ . ברור שסכום המספרים המרבי האפשרי של התת-קבוצה שווה למספר הגדול ביותר בקבוצה ועוד כל המספרים בסדרה שהגדרנו שקטנים ממנו. כיוון ש- $a_{max}>k^{2}$ , אם נצליח להוכיח שסכום המספר הגדול בקבוצה וכל המספרים בסדרה שהגדרנו שקטנים ממנו קטן מ- $(k+1)^{2}=(k^{2}+1)+2k=a_{max}+2k$ , אז "חסמנו" למעשה את הסכום בין שני ריבועים עוקבים, ולכן הוא לא יכול להיות ריבוע. מספיק להוכיח למעשה שסכום כל המספרים בתת-קבוצה פרט למספר הגדול ביותר בה ( $k^{2}+1$ ) והמספר השני הגדול ביותר בה ( $k$ ) הינו קטן מ- $k$ . לכל אוסף של מספרים שגדולים או שווים ל-2 מכפלתם גדולה או שווה לסכומם. לכן אם נוכיח שמכפלת כל האיברים בתת-קבוצה פרט לשני האיברים הגדולים ביותר בה קטנה מ-k אז ההוכחה הסתיימה. מתקיים בסדרה: $a_{n-1}<{\sqrt {a_{n}}}$ , ולכן: $a_{n-i}<a_{n}^{\frac {1}{2^{i}}}$ . מכפלת כל המספרים הללו היא לפיכך קטנה מ- $k^{1/2+1/4+1/8+...+1/(2^{k-1})}<k$ (התוצאה האחרונה נובעת מכך שסכום הסדרה ההנדסית שבמעריך תמיד קטן מ-1).

מ.ש.ל