MATEMANIJA

xyz je napisao:Neka su sve tačke u ravni obojene u dvije boje. Dokazati da postoji pravougaonik čiji su vrhovi iste boje.

Wikipedija je napisao:Vrh može značiti:

osnovno značenje

• vrh, npr. vrh planine
• vrh (geometrija), točka u kojoj se sijeku stranice nekog lika

Putnam and Beyond: Razvan Gelca, Titu Andreescu je napisao:Pick two infinite families of lines, [inlmath]\{A_i,\;i\geq1\}[/inlmath], and [inlmath]\{B_j,\;j\geq1\}[/inlmath], such that for any [inlmath]i[/inlmath] and [inlmath]j[/inlmath], [inlmath]A_i[/inlmath] and [inlmath]B_j[/inlmath] are orthogonal. Denote by [inlmath]M_{i,j}[/inlmath] the point of intersection of [inlmath]A_i[/inlmath] and [inlmath]B_j[/inlmath]. By the pigeonhole principle, infinitely many of the [inlmath]M_{1j}[/inlmath]’s, [inlmath]j\geq1[/inlmath], have the same color. Keep only the lines [inlmath]B_j[/inlmath] corresponding to these points, and delete all the others. So again we have two families of lines, but such that [inlmath]M_{1,j}[/inlmath] are all of the same color; call this color [inlmath]c_1[/inlmath].
Next, look at the line [inlmath]A_2[/inlmath]. Either there is a rectangle of color [inlmath]c_1[/inlmath], or at most one point [inlmath]M_{2,j}[/inlmath] is colored by [inlmath]c_1[/inlmath]. Again by the pigeonhole principle, there is a color [inlmath]c_2[/inlmath] that occurs infinitely many times among the [inlmath]M_{2,j}[/inlmath]’s. We repeat the reasoning. Either at some step we encounter a rectangle, or after finitely many steps we exhaust the colors, with infinitely many lines [inlmath]A_i[/inlmath] still left to be colored. The impossibility to continue rules out this situation, proving the existence of a rectangle with vertices of the same color.

Posmatramo dva beskonačna skupa pravih [inlmath]\{A_i,\;i\geq1\}[/inlmath] i [inlmath]\{B_j,\;j\geq1\}[/inlmath], tako da su prave [inlmath]A_i[/inlmath] i [inlmath]B_j[/inlmath] normalne za [inlmath]\forall i,j[/inlmath]. Sa [inlmath]M_{i,j}[/inlmath] označimo tačku preseka pravih [inlmath]A_i[/inlmath] i [inlmath]B_j[/inlmath]. Na osnovu Dirihleovog principa beskonačno mnogo tačaka [inlmath]M_{1,j}[/inlmath], [inlmath]j\geq1[/inlmath] ima istu boju [inlmath]c_1[/inlmath]. Zadržimo samo odgovarajuće prave [inlmath]B_j[/inlmath], a sve ostale obrišimo. Ako postoje bar dve tačke [inlmath]M_{2,j}[/inlmath] koje imaju boju [inlmath]c_1[/inlmath], uočavamo pravouganik. Ako nema, na osnovu Dirihleovog principa uočavamo beskonačno mnogo tačaka [inlmath]M_{2,j}[/inlmath] obojene u [inlmath]c_2[/inlmath]. Ponavljamo postupak. U jednom trenutku moramo uočiti pravougaonik jer ako nastavimo ovako nakon konačno mnogo koraka ćemo ostati bez boja a imaćemo beskonačno mnogo pravih [inlmath]A_i[/inlmath] koje treba obojiti.

Putnam and Beyond: Razvan Gelca, Titu Andreescu je napisao:Here is another solution. Consider a [inlmath](p+1)\times\Bigl(n{p+1\choose2}+1\Bigr)[/inlmath] rectangular grid. By the pigeonhole principle, each of the [inlmath]n{p+1\choose2}+1[/inlmath] horizontal segments contains two points of the same color. Since there are at most [inlmath]n{p+1\choose2}[/inlmath] possible configurations of such monochromatic pairs, two must repeat. The two pairs are the vertices of a monochromatic rectangle.