Šta da se radi ako imamo [inlmath]n[/inlmath] boja?
Ja sam našao neko rešenje na engleskom.
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.
I preveo ga nekako na srpski.
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.
Možda prevod nije baš naj. Kapiram otprilike kako su zamislili algoritam, ali mi nije baš najjasnije zašto nakon konačno mnogo koraka zaključujemo da postoji pravougaonik (poslednja jedna/dve rečenice).
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.
Odakle izvadiše ove brojeve...