Every natural number is coloured in one of the $ k$ colors. Prove that there exist four distinct natural numbers $ a, b, c, d$, all coloured in the same colour, such that $ ad = bc$, $ \displaystyle \frac b a$ is power of 2 and $ \displaystyle \frac c a$ is power of 3.
Problem
Source: Croatia TST 2009
Tags: geometry, rectangle, analytic geometry, combinatorics unsolved, combinatorics
16.04.2009 17:18
Any ideas please
17.04.2009 18:17
No body interest this problem ? I think it's very nice
17.04.2009 19:41
I agree with you but I can't give you any idea because I spent about an hour thinking but with no result.
17.04.2009 21:16
I'll give you the hint: consider only the numbers in the form $ 2^a \cdot 3^b$. You can arrange them in the 2D table...
19.04.2009 17:06
Indeed a very nice problem. Let a be any positive integer. Fix a and label the lattice points of the first quadrant of the Cartesian plane as follows: (x,y) is labelled with $ 2^x\cdot 3^y \cdot a$, for x,y nonnegative integers. Colour each of these points with the colour of the number it represents. Then we simply need a monochromatic rectangle with sides parallel to the x and y axes. Define a segment starting at (x,y) to be the collection of points (x,y+i) for i=0,1,2,...,k. Since there are k+1 points every segment contains two points of the same colour. Furthermore for n sufficiently large some two of the segments starting at (0,0), (0,1), (0,2),...,(0,n) are coloured in exactly the same way, i.e. each pair of corresponding points have the same colour. Now these two segments contain a rectangle because each segment contains two points of the same colour, and the two segments are coloured in exactly the same way.
11.05.2016 19:31
I don't understand the question. What does it mean when it discusses the colors? I can find $4$ natural numbers that satisfy the given conditions ($1,2,3,$ and $6,$ for example) but I know it must be more difficult than that. The colors are a bit confusing....
11.05.2016 20:44
We prove the stronger result that $a,b,c,d$ exist where $\{a,b,c,d\}\subset\mathbb{S}= \{2^x3^y|(x,y)\in\mathbb{N}_0^2\}$. Coordinatize the plane such that the point in the first quadrant with coordinates $(x,y)$ corresponds to the number $2^x3^y$. Then the condition $ad=bc$ is equivalent to $a,b,c,d$ corresponding to a rectangle with $a,d$ at opposite corners. Given a monochromatic rectangle in the coordinate plane, we can easily construct $a,b,c,d$ as follows. [asy][asy] import cse5; import olympiad; pathpen = black; pointpen = black; size(14cm); pair O=origin, D=dir(30), A=dir(210), B=dir(150), C=dir(-30); DPA(A--B--D--C--cycle, red); D("a",A,A); D("c",B,B); D("b",C,C); D("d",D,D); [/asy][/asy] So it suffices to prove the existence of a monochromatic rectangle if we color the lattice points in the first quadrant with $k$ colors. Consider the $k+1\times k^{k+1}+1$ grid with lower left corner $(0,0)$ and upper right corner $(k,k^{k+1})$. There are $k^{k+1}$ different colorings of a row consisting of $k+1$ points, so by pigeonhole principle two rows in this grid are identical. Consider one of these rows. There are $k$ possible colors in a row, so there are two points in this row that are the same color. But these points and the corresponding points in the identical row give a monochromatic rectangle so we are done. This also gives the trivial bound that there exist $a,b,c,d\le k^{k+1}$.
01.04.2021 01:02
The condition $ad=bc$, implies that $a=xy$,$d=zw$,$b=xz$ and $c=yw$, for some $x,y,z,w \in \mathbb{N}$. The other conditions imply that $x=3^hw$ and $y=2^tz$, where $t$ and $h$ are some natural numbers. Thus giving us $a=3^h2^tzw$, $b=3^hzw$, $c=2^tzw$ and $d=zw$. So now obviously we must have at least one coloring that contains $\infty$ composite numbers. Because of this fact we can set $z,w,t,h$ so that $a,b,c,d$ are of the same color. (Alternately we could have went on case by case on the specific situations and forms of $a,b,c,d$ in terms of coloring).
07.05.2022 19:19
Place each number of the form $2^x3^y$ in the lattice point $(x,y)$ of the Cartesian coordinate plane. Then, it is sufficient to find a monochromatic rectangle. Now, there are two ways to show one exists: 1) By infinite pigeonhole (twice) there are an infinite number of columns with the same color an infinite number of times. Now, if no monochromatic rectangle is present, that means that of the remaining numbers in these columns, painted of the other $k-1$ colors, there are an infinite number of columns with the same color an infinite number of times. Continuing with this logic (with an induction argument), we eventually reach inifinite number of columns of the same color, which obviously contain a rectangle. 2) Consider the first $k+1$ numbers in a row. There is a finite amount of ways to color them. Hence, if we look at sufficiently many rows, there are two colored in the exact same way. Since there are $k+1$ numbers, at least $2$ are of the same color, and this gives the desired rectangle. $\blacksquare$