Let $S$ be a set of positive integers such that $\lfloor \sqrt{x}\rfloor =\lfloor \sqrt{y}\rfloor $ for all $x, y \in S$. Show that the products $xy$, where $x, y \in S$, are pairwise distinct.
Problem
Source: Danube 2014 p2
Tags: floor function, set, algebra, Product
22.07.2019 15:46
Let $k=\lfloor \sqrt{x}\rfloor=\lfloor \sqrt{y}\rfloor \geq 1$. It's easy to prove $S=\lbrace k^2,k^2+1,...,k^2+2k\rbrace$ Let $x=k^2+i$, $y=k^2+j$, $z=k^2+m$, $w=k^2+n$, $0\leq i,j,m,n\leq 2k$ $xy=zw$ $\Leftrightarrow$ $k^2(i+j-m-n)=ij-mn$ hence $ij-mn$ has to be an integer multiple of $k^2$. Wlog $ij>mn$ (we can't have $i+j-m-n=ij-mn=0$ because this implies $(i,j)$, $(m,n)$ are the same couples). $ij-mn\leq 4k^2$ hence $ij-mn=ak^2$, $a\in\lbrace 1,2,3,4\rbrace$ Thus we have $i+j-m-n=a$ and $ij-mn=ak^2$ that is $i+j=m+n+a$ and $ij=ak^2+mn$. The polynomial of degree 2 whose roots are $i,j$ is $x^2-(m+n+a)x+ak^2+mn$. $\Delta =(m+n+a)^2-4ak^2-4mn=((m-n)^2-4ak^2)-a(2(m+n)-a)$ $ij\geq mn+k^2\geq k^2$ thus by AM-GM $i+j\geq 2\sqrt{ij}\geq 2k$. Then $m+n\geq i+j+1\geq 2k+1$ and $(i-j)^2<4k^2\leq 4ak^2$. Hence $\Delta <-a(2(i+j)-a)\leq -a(2(2k+1)-a)\leq -a(6-a)<0$ thus $i,j$ cannot be integer. That's the desired contradiction
01.10.2020 18:13
paperinikk wrote: Let $k=\lfloor \sqrt{x}\rfloor=\lfloor \sqrt{y}\rfloor \geq 1$. It's easy to prove $S=\lbrace k^2,k^2+1,...,k^2+2k\rbrace$ Let $x=k^2+i$, $y=k^2+j$, $z=k^2+m$, $w=k^2+n$, $0\leq i,j,m,n\leq 2k$ $xy=zw$ $\Leftrightarrow$ $k^2(i+j-m-n)=ij-mn$ hence $ij-mn$ has to be an integer multiple of $k^2$. Wlog $ij>mn$ (we can't have $i+j-m-n=ij-mn=0$ because this implies $(i,j)$, $(m,n)$ are the same couples). $ij-mn\leq 4k^2$ hence $ij-mn=ak^2$, $a\in\lbrace 1,2,3,4\rbrace$ Thus we have $i+j-m-n=a$ and $ij-mn=ak^2$ that is $i+j=m+n+a$ and $ij=ak^2+mn$. The polynomial of degree 2 whose roots are $i,j$ is $x^2-(m+n+a)x+ak^2+mn$. $\Delta =(m+n+a)^2-4ak^2-4mn=((m-n)^2-4ak^2)-a(2(m+n)-a)$ $ij\geq mn+k^2\geq k^2$ thus by AM-GM $i+j\geq 2\sqrt{ij}\geq 2k$. Then $m+n\geq i+j+1\geq 2k+1$ and $(i-j)^2<4k^2\leq 4ak^2$. Hence $\Delta <-a(2(i+j)-a)\leq -a(2(2k+1)-a)\leq -a(6-a)<0$ thus $i,j$ cannot be integer. That's the desired contradiction $\Delta =((m-n)^2-4ak^2)+a(2(m+n)+a) \neq ((m-n)^2-4ak^2)-a(2(m+n)-a)$