$ S\subset\mathbb N$ is called a square set, iff for each $ x,y\in S$, $ xy+1$ is square of an integer. a) Is $ S$ finite? b) Find maximum number of elements of $ S$.
Problem
Source: Iranian National Olympiad (3rd Round) 2003
Tags: number theory proposed, number theory
25.01.2009 03:24
Do you mean x is not equal to y? Because if it were, $ x^2+1$ would be a square, and that is clearly impossible.
01.02.2009 07:07
Of course you should consider $ x\neq y\in S$.
21.09.2019 23:00
a)The answer is no.Assume for country that an infinite such set exists let $a,b,c$ be three distinct elements from the set then $(ax+1)(bx+1)(cx+1)$ is a square for infinity many $x$ which contradicts Siegel's Theorem.
17.05.2020 21:16
as the user Taha sayd the first part can be done like that : i will just leave my proof here if anyone wants an elementary proof we claim the answer is $No$ for the sake of contradiction (god i love this sentence ) say we have infinite numbers on $S$ take 2 of them like $a , b$ with $ab=m^2 -1$ let $a+b=u , m^2 - 1 =w^2 $ remember that $u$ is integer but $w$ is not. now look at this polynomial $P(x)= (ax+1)(bx+1)$ as we all know if $x$ is an element of $S$ then $P$ is the square of an integer look more closely and get $ P(x)=(wx)^2 + ux + 1$ now lets construct 2 little polynomials $Q$ and $R$ such that $Q(x)= (wx + u/(2w) ) ^2 , R(x) = (wx + u/(2w) -1) ^2 $ after a little work and using $AM-GM$ we get $Q>P>R$ let $x$ be an element of $S$ we have$ wx + u/2w > sqrt(P(x))>wx + u/2w -1$ with this we have $sqrt(P(x))=floor_of (wx + u/2w) $ i dont know how to draw floor in here so im just gana say $g(x)$ is the floor function now let $S(x) = P(x) - (g(wx + u/2w) ^2) $ now let $S(x)=0$ and $S(x + 1/w) > 0 $ (we can get this by a little amount of work) so by inductive step we get $S(x + n/w) > S(x+ (n-1)/w) $ but since this should give us inifnite solutions as $S(x)=0$ is a contradiction and we are done . . . by the way $bump$ for part $b$
18.05.2020 02:32
Doesn't the question asks for if - Every two elements product increased by $1$ is a perfect square ? There are infinitely many if set $S$ has only $3$ elements.
18.05.2020 03:47
Alphatrion wrote: Doesn't the question asks for if - Every two elements product increased by $1$ is a perfect square ? There are infinitely many if set $S$ has only $3$ elements. The question asks among all possible sets $S$, what is the largest possible cardinality (Note that from $a)$ such maximum exist). If you claim that the answer is $k$, you must give an example of such $S$ with $k$ elements and prove that no such $S$ with $k+1$ elements exist.
18.05.2020 10:21
just to leave this here my proof for part $a$ also gives us that for part $b$ the $max$ cardinality is atmost 3 since if its 4 my proof gives by taking 2 of them and the smaller root of $S$ and using the inductive step i sayd we can get a contradiction so its atmost 3 and for an example $1,3,8$ work
20.05.2020 00:30
This is a relatively well-known problem and very difficult. Such sets are known as Diophantine $m$-tuples. The answer for part $b$ is 4: the above example $1,3,8$ can be extended into $1,3,8,120$. For reference, see A030063 on OEIS.
22.05.2020 10:49
then can someone point out the misstake in my solution?
22.05.2020 10:52
maybe the problem is with the number 1 it self? i dont know can some one give an example of 4 elements without number 1 in it?
02.08.2020 15:54
@above $\{n,n+2,4n+4,16n^3+48n^2+44n+12\}$ for $n \in \mathbb{N}$ works and there is no 1. and also Quote: after a little work and using $AM-GM$ we get $Q>P>R$ let $x$ be an element of $S$ we have$ wx + u/2w > \sqrt{P(x)}>wx + u/2w -1$ with this we have $\sqrt{P(x)}=\lfloor (wx + u/2w)\rfloor $ now let $S(x) = P(x) - (\lfloor(wx + u/2w)\rfloor ^2) $ now let $S(x)=0$ and $S(x + 1/w) > 0 $ (we can get this by a little amount of work) so by inductive step we get $S(x + n/w) > S(x+ (n-1)/w) $ but since this should give us inifnite solutions as $S(x)=0$ is a contradiction This is unclear to me And also isn't it a bit too hard for Iran 3rd round
02.08.2020 16:03
yes actually i found out the hole in my proof it still works for part a with a little editing but not for part 2
02.08.2020 16:11
maths ayoub