There are k colors given. Every point in a 2 D plane carries exactly one of these k colors. what are the values of k, for which there will necessarily exist a rectangle with vertices having same color. In particular, what is maximum value of k.
for all finite k, u can find a rectangle with 4 vertices. For example, suppose k= 4, i.e. there are 4 clors.
draw 5 horizontal lines , and 41 vertical lines. Now each vertical line will intersect horizontal lines at 5 points.As there are only 4 colors, some 2 points have same color, this gives us , for each vertical line, a set {c,i,j} where c is a color and i,j denote the horizontal lines where the vertical line intersects at points colored c.
Total number of different sets {c,i,j} possible = 4 * 5C2= 4*10=40. As there are 41 vertcal lines, some two of these will give rise to same set {c,i,j}. Therefore, we get a rectangle with vertices of same color.
Above argument can be extended to any finite k. We need consider, (k+1) horizontal lines, and k* (k+1)C2 vertical lines.
for all finite k, u can find a rectangle with 4 vertices. For example, suppose k= 4, i.e. there are 4 clors.
ReplyDeletedraw 5 horizontal lines , and 41 vertical lines. Now each vertical line will intersect horizontal lines at 5 points.As there are only 4 colors, some 2 points have same color, this gives us , for each vertical line, a set {c,i,j} where c is a color and i,j denote the horizontal lines where the vertical line intersects at points colored c.
Total number of different sets {c,i,j} possible = 4 * 5C2= 4*10=40. As there are 41 vertcal lines, some two of these will give rise to same set {c,i,j}.
Therefore, we get a rectangle with vertices of same color.
Above argument can be extended to any finite k. We need consider, (k+1) horizontal lines, and k* (k+1)C2 vertical lines.