Comb

For discussing Olympiad Level Combinatorics problems
User avatar
Nadim Ul Abrar
Posts:244
Joined:Sat May 07, 2011 12:36 pm
Location:B.A.R.D , kotbari , Comilla
Comb

Unread post by Nadim Ul Abrar » Tue Jan 22, 2013 12:00 am

$22$ points are chosen from the $7×7$ grid of points $(i,j)$, where $1≤ i≤ 7$
and $1≤ j≤ 7$. Prove that four of the chosen points are the vertices
of a rectahgle with horizontal and vertical sides. Show that this might
not be the case, if $21$ vertices are chosen.
$\frac{1}{0}$

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Comb

Unread post by Phlembac Adib Hasan » Tue Jan 22, 2013 2:36 pm

Part A:
Think about the $7$ columns of points. From Pigeon Hole Principle, there must be a column from where at least four points are chosen. Name these point $A,B,C,D$. Now let these points are situated at $A',B',C',D'$ row, respectively. Note that on each of other six columns, we can chose at most one other point on some of $A',B',C',D'$, for not getting a rectangle. In the figure below, I tried to show an example.
Figure_1.png
If we choose two points on the same column then we get an rectangle.
Figure_1.png (18.81KiB)Viewed 2662 times
So till now (at most) ten points have found their places. But we still have (at least) $22-10=12$ other points. We'll try to place them in such a way so that all the $22$ points follow the given rule. Then we'll show that it's impossible to distribute the last $12$ points.
Notice that these $12$ points can't be placed in any of $A',B',C',D'$. So they should be placed in the other three rows. Name them $E',F',G'$.
Two cases:
Case 1: Where each of the columns has at leat one of the last 12 points.
From Pigeon Hole Principle, there will be at least three columns have at least $2$ points. To follow the conditions they will be situated in positions like given in figure 2. I mean each of $E',F',G'$ will get exactly 2 from these six points. (Shown in the figure)
Figure_2.png
Figure_2.png (18.94KiB)Viewed 2662 times
Also remember here each of the columns has at least one point. So excluding these three columns who have already two points, the other four colums has at least four point in total. Hence at least one of $E',F',G'$ has at least four points.(From php) So these ten points have been well-distributed. Now it's time to remember the other two points.
Now note that from $E',F',G'$, we can get rectangles in three ways: $2$ points from $E'$ and $2$ points from $F'$, $2$ points from $G'$ and $2$ points from $F'$ and $2$ points from $E'$ and $2$ points from $G'$. Look at the figure. you will see for each case there is a pair parallel to the vartices. (We are talking about $(P,Q),(S,R),(U,T)$). Also we at leas one point on each other columns. So at every possible place there are three vertices of a rectangle is made. Therefore whenever you put a point from the last two, it will finish the job resulting a rectangle.

Case 2: Where at least one of the columns has none of the last 12 points.
From Pigeon Hole Principle, there will be at least five columns have at least $2$ points. ( We can not place three points each on two columns at the same time. Can you explain why?) But since $\displaystyle \binom {3}{2}=3$, there will be two pairs having same phase, I mean horizontally lying on the same pair of lines. So they will always make a rectangle.
Done....... :D
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply