A finite set $K$ consists of at least 3 distinct positive integers. Suppose that $K$ can be partitioned into two nonempty subsets $A,B\in K$ such that $ab+1$ is always a perfect square whenever $a\in A$ and $b\in B$. Prove that \[\max_{k\in K}k\geq \left\lfloor (2+\sqrt{3})^{\min\{|A|,|B|\}-1}\right\rfloor+1,\]where $|X|$ stands for the cartinality of the set $X$, and for $x\in \mathbb{R}$, $\lfloor x\rfloor$ is the greatest integer that does not exceed $x$.
Problem
Source: 2020 Taiwan TST Round 2 Mock Exam P5
Tags: number theory
TheThor
26.05.2020 09:51
Any solutions?
USJL
26.05.2020 10:22
Lemma. Let $a<c$ be two elements in $A$ and $b<d$ be two elements in $B$. Then
By the condition, we know that $ab+1, ad+1, bc+1, cd+1$ are all squares. Therefore $(ab+1)(cd+1)=abcd+ab+cd+1$ and $(ad+1)(bc+1)=abcd+ad+bc+1$ are both sqaures. The difference between them is $(ab+cd)-(ad+bc) = (c-a)(d-b)>0$. Since both squares are larger than $abcd$, the difference should be greater than $2\sqrt{abcd}$.
Now suppose that the elements in $A$ are $a_1<a_2<\cdots<a_m$ and $b_1<b_2<\cdots<b_n$ are the elements in $B$. Let $x=\min a_{i+1}/a_i$ and $y=\min b_{j+1}/b_j$. Then by the lemma, we have \[(x^{1/2}-x^{-1/2})(y^{1/2}-y^{-1/2})>2.\]WLOG $x\geq y$, then \[x^{1/2}-x^{-1/2}>\sqrt{2},\]which shows that \[x^2-4x+1>0,\]\[x>2+\sqrt{3}.\]Hence \[a_m>(2+\sqrt{3})^{m-1}.\]This shows the result.
Rickyminer
26.05.2020 11:42
Kinda similar to 2012 China TST, but a nicer bound!