Find a set of infinite positive integers $ S$ such that for every $ n\ge 1$ and whichever $ n$ distinct elements $ x_1,x_2,\cdots, x_n$ of S, the number $ x_1+x_2+\cdots +x_n$ is not a perfect square.
Problem
Source: Central American Olympiad 2002, problem 5
Tags:
Icosahedroid
30.12.2009 09:36
3, 12, 48, 192, ... 3(4^n). If the first term is used, then a sum is equivalent to 3 mod 4. All perfect squares are equivalent to 1 mod 4 or 0 mod 4. If the second term is used, but not the first, then it is equivalent to 4(n) where n is equivalent to 3 mod 4. This can be factored into (2^2)n and n is not a perfect square. This process can be repeated indefinitely.
mahanmath
30.12.2009 10:43
It works too : $ {2 , 8 , 32 , 128 , ... , 2^{2n+1} , ....}$
dgreenb801
30.12.2009 16:34
We can use induction. Take the set that worked for $ k$ numbers and add another number $ m$ large enough such that both $ m$ and $ m$ plus all the $ k$ other numbers are in between two (large) consecutive squares. Now we have a set for $ k + 1$ numbers that works, because if the sum doesn't use $ m$, it can't be a square, but if it does, it must be between two consecutive squares and thus can't be a square. For example, suppose we have the set $ {3,5,7}$ so far. Note that $ 100^2 = 10000$ and $ 101^2 = 10201$. So we can add $ 10100$ to the set, because both $ 10100$ and $ 10100 + 3 + 5 + 7 = 10113$ are between two consecutive squares. So if the sum uses only the numbers $ 3,5,7$, it can't be a square, but if it uses $ 10100$, it must be between two squares and thus can't be a square. By the way, this is only a sketch, you can make it rigorous.
RobRoobiks
31.12.2009 04:13
1+2+3+4+5...+n=(n)(n+1)/2 2(1+2+3+4+5...+n)=(n)(n+1) n(n+1) will never be a perfect square so we have (2, 4, 6, 8, 10..) as our set How do you dem them apples!
Mewto55555
31.12.2009 05:08
Rob: But what if we take the subset 2,4,10? Then we get 16!
RobRoobiks
31.12.2009 17:24
Ah, I see. I thought the numbers are taken in order and you cannot take a subset
prasanna1712
02.01.2011 20:24
the sequence $a_{n}=(a_{n-1}+1)(a_{n-1})$ works as well.
RMACR7LP
21.06.2020 07:28
I think I have a particularly simple solution though is not a handy solution (meaning its essence is not applicable in many other problems, as the argument from @dgreenb801 is, cool idea btw makes a lot of sense approaching it this way to be honest). Consider the set $A=\{10, 1000, 100000, \cdots, 10^{2n+1} , \cdots \}$. Notice that no matter the choice of a subset of $A$, the sum of all the elements in the subset must end in an odd number of zeroes, hence it cannot be a perfect square.