Show that there exist distinct positive integers $a,b,c,d$ such that all of these three conditions are satisfied simultaneously.

107 Views Asked by At

Question: Let $n\in\mathbb{N}$. We colour every positive integer by one of $n$ colours. Show that there exist distinct positive integers $a,b,c,d$ such that:

(i) they are of same colour

(ii) $ad=bc$

(iii) $\frac{b}{a}$ is a power of $2$ and $\frac{c}{a}$ is a power of $3$

holds simultaneously.

Solution: Observe that $\frac{b}{a}=2^k,$ for some $k\in\mathbb{N}\iff b=2^ka,$ for some $k\in\mathbb{N}$ and $\frac{c}{a}=3^{k'},$ for some $k'\in\mathbb{N}\iff c=3^{k'}a,$ for some $k'\in\mathbb{N}.$ Thus (iii) is satisfied only when $b=2^ka$ and $c=3^{k'}a,$ for some $k,k'\in\mathbb{N}.$

Thus $ad=bc$ and $b=2^ka,c=3^{k'}a\iff b=2^ka,c=3^{k'}a$ and $d=2^k3^{k'}a,$ for some $k,k'\in\mathbb{N}$.

This implies that both (ii) and (iii) are satisfied only when $b=2^ka, c=3^{k'}a$ and $d=2^k3^{k'}a$, for some $k,k'\in\mathbb{N}$. Observe that in such case $a,b,c,d$ are mutually distinct too.

Thus, in order to solve the problem, let us select any arbitrary positive integer $a'$ and let $S:=\{2^x3^ya'|x,y\in\mathbb{N}\}$. Now let us define a bijection $f:S\to \mathbb{N}^2$, such that $$f(2^x3^ya')=(x,y), \forall x,y\in\mathbb{N}.$$

For a better understanding, consider the below mentioned arrangement of the elements in $S$. It is the similar to how $f$ maps $S$ to $\mathbb{N}^2$. \begin{array}{|c|c} \vdots & \vdots &\vdots & .^{.^.}\\\hline 2^4.3^1a' & 2^4.3^2a' & 2^4.3^3a' & \cdots\\\hline 2^3.3^1a' & 2^3.3^2a' & 2^3.3^3a' & \cdots\\\hline 2^2.3^1a' & 2^2.3^2a' & 2^2.3^3a' & \cdots\\\hline 2^1.3^1a' & 2^1.3^2a' & 2^1.3^3a' & \cdots\\\hline \end{array} Also let us colour each point $(x,y)\in\mathbb{N}^2$ by the same colour as that of the pre-image $2^x3^ya'\in S$.

Claim: If we color each point $(x,y)\in\mathbb{N}^2$ by the same colour as that of the pre-image $2^x3^ya'\in S$, then, there exists a rectangle such that each of its four vertices are of same colour and its sides are parallel to the X and Y axes.

The proof to this claim is pretty similar to the proof to the problem that I have stated here: Show that there exists a rectangle such that each of its four vertices are of same colour and its sides are parallel to the X and Y axes.

Now let $ABCD$ be the rectangle under consideration, such that $A=(x_1,y_1), B=(x_1,y_2), C=(x_2,y_2)$ and $D=(x_2,y_1)$, where $x_2>x_1$ and $y_2>y_1$.

Now let $$a=f^{-1}(A)=f^{-1}(x_1,y_1)=2^{x_1}3^{y_1}a', \\b=f^{-1}(D)=f^{-1}(x_2,y_1)=2^{x_2}3^{y_1}a', \\c=f^{-1}(B)=f^{-1}(x_1,y_2)=2^{x_1}3^{y_2}a'\text{, and}\\d=f^{-1}(C)=f^{-1}(x_2,y_2)=2^{x_2}3^{y_2}a'.$$

Firstly observe that $a,b,c,d$ are all of the same colour, since $A,B,C,D$ are all of the same colour. Thus (i) is satisfied.

Secondly, $ad=2^{x_1+x_2}3^{y_1+y_2}(a')^2$ and $bc=2^{x_1+x_2}3^{y_1+y_2}(a')^2$, which implies that $ad=bc$. Thus (ii) is also satisfied.

Thirdly, $\frac{b}{a}=2^{x_2-x_1}$ and $\frac{c}{a}=3^{y_2-y_1}$, where $x_2-x_1>0$ and $y_2-y_1>0$. Thus (iii) is also satisfied.

Also, it is easy to observe that $a,b,c,d$ are all mutually distinct.

Thus we can conclude that $\exists$ distinct $a,b,c,d\in\mathbb{N}$ such that all of (i), (ii) and (iii) are satisfied simultaneously.

Is this solution correct and rigorous enough? If yes, then, is there a better solution?