Let positive real numbers $ a,b$ satisfy $ b - a > 2.$ Prove that for any two distinct integers $ m,n$ belonging to $ [a,b),$ there always exists non-empty set $ S$ consisting of certain integers belonging to $ [ab,(a + 1)(b + 1))$ such that $ \frac {\displaystyle\prod_{x\in S}}{mn}$ is square of a rational number.
Problem
Source: Chinese TST 2009 P4
Tags: combinatorics proposed, combinatorics
06.01.2010 04:03
Well, i can't remember detail proof. This is what my teacher taught me. let $ T = \{x|a\le x \le [b] + 1\}$ and if $ x,y \in T$ satisfy above condition(in problem). Then we connect $ x$ and $ y$ Clain) these $ x,y$s set consists connected graph But it is not difficult to prove it. and then, we are done
28.07.2014 23:20
Any full solution for this problem, please !!!
19.09.2014 12:02
I think, the hint, though pretty unclear, could be carried out. The idea is to show existence of a chain of integers $m=r_0, r_1,\ldots, r_j=n$, with $r_j\in [a,b)$ and $r_i r_{i+1}\in[ab,(a+1)(b+1))\,, i=0,\ldots,i-1$. For example, the plan of proving it might be carried like that: Assume $m<n$ and start with $r_0=m$. If $r_0 n \in [ab,(a+1)(b+1)) $ we are done, else set $r_1$ to be the closest to $n$ integer in $[a,b)$ that keep $r_0r_1$ in this interval. Then proceed with $r_1$ instead with $r_0$ and so on. Eventually we should arrive at $n$. Finally there is one more obstacle: some of the products $r_i r_{i+1}$ may be the same. In that case we omit all of the equal ones if their number is even or leave just one of them if their number is odd.
16.07.2016 06:27
Let $m \sim n$ be the relation $ \frac {\displaystyle\prod_{x\in S} x}{mn}$ is a rational square. I claim that $\sim$ is an equivalence relation. Denote $[ab, (a+1)(b+1))$ as $\textit{the big interval}$ henceforth, and $[a, b)$ as $\textit{the little interval}$ henceforth. Symmetry is immediate, and we can evidently prove reflexiveness by showing that there is at least one perfect square in $\textit{the big interval}$. Observe that there exists a real $0 \le r < 1$ such that $\sqrt{ab} + r$ is an integer. I claim that this, when squared, is less than $(a+1)(b+1)$. This computation is simple, observe that \[ (\sqrt{ab} + r)^2 = ab + r + 2r\sqrt{ab} < ab + 1 + 2\sqrt{ab} < ab + a + b + 1 = (a+1)(b+1) \]The next step is to show transitivity, which is slightly more nontrivial. Assume $a \sim b$ and $b \sim c$. Then, let $S_1$ be the associated set with the first one and $S_2$ be the associated set with the second one. Then, it is clear $S_1 \oplus S_2$ (where $\oplus$ denotes symmetric difference) is a working subset. (if the symmetric difference is empty, we have $ac$ perfect square, so just take the perfect square in $\textit{the big interval}$. Now that we have proven $\sim$ is simply an equivalence relation, it remains to show that all elements are equivalent to each other. Fortunately, this turns out to be not that hard. I claim that $x \sim (x+1)$ for all integers $x$ in the little interval, which will show the result by definition. This proof turns out to be rather easy; observe that $x \sim y$ if $xy$ is in $\textit{the big interval}$, for obvious reasons. So all we need to do is find an integer $y$ such that \[ ab \le xy \le (x+1)(y) < (a+1)(b+1) \]and we will be done since $x \sim y \sim (x+1)$. This process is relatively easy. Note that we can lose here only if we have some $y$ for which \begin{align*} xy &< ab \\ (x+1)(y + 1) &\ge (a+1)(b+1) \end{align*}This is of course ludicrous; subtracting the equations gives $x + y > a + b$, but $a \le x \le y < b$, so this is impossible.
18.06.2019 05:10
simplyconnected43 wrote: Let $m \sim n$ be the relation $ \frac {\displaystyle\prod_{x\in S} x}{mn}$ is a rational square. I claim that $\sim$ is an equivalence relation. Denote $[ab, (a+1)(b+1))$ as $\textit{the big interval}$ henceforth, and $[a, b)$ as $\textit{the little interval}$ henceforth. Symmetry is immediate, and we can evidently prove reflexiveness by showing that there is at least one perfect square in $\textit{the big interval}$. Observe that there exists a real $0 \le r < 1$ such that $\sqrt{ab} + r$ is an integer. I claim that this, when squared, is less than $(a+1)(b+1)$. This computation is simple, observe that \[ (\sqrt{ab} + r)^2 = ab + r + 2r\sqrt{ab} < ab + 1 + 2\sqrt{ab} < ab + a + b + 1 = (a+1)(b+1) \]The next step is to show transitivity, which is slightly more nontrivial. Assume $a \sim b$ and $b \sim c$. Then, let $S_1$ be the associated set with the first one and $S_2$ be the associated set with the second one. Then, it is clear $S_1 \oplus S_2$ (where $\oplus$ denotes symmetric difference) is a working subset. (if the symmetric difference is empty, we have $ac$ perfect square, so just take the perfect square in $\textit{the big interval}$. Now that we have proven $\sim$ is simply an equivalence relation, it remains to show that all elements are equivalent to each other. Fortunately, this turns out to be not that hard. I claim that $x \sim (x+1)$ for all integers $x$ in the little interval, which will show the result by definition. This proof turns out to be rather easy; observe that $x \sim y$ if $xy$ is in $\textit{the big interval}$, for obvious reasons. So all we need to do is find an integer $y$ such that \[ ab \le xy \le (x+1)(y) < (a+1)(b+1) \]and we will be done since $x \sim y \sim (x+1)$. This process is relatively easy. Note that we can lose here only if we have some $y$ for which \begin{align*} xy &< ab \\ (x+1)(y + 1) &\ge (a+1)(b+1) \end{align*}This is of course ludicrous; subtracting the equations gives $x + y > a + b$, but $a \le x \le y < b$, so this is impossible. Hi, The idea of showing an equivalence relation is indeed excellent. But isn't there a mistake in your last step? if you are trying to show that there is a $y$ in $[a,b)$ such that both $xy$ and $(x+1)y$ are in $[ab,ab+a+b+1)$, your last step is not sufficient, as it doesn't cover the case that only one of them is in the interval.