kombinatorni zadatak

Neka je S skup tacaka (x, y) u koordinatnoj ravni qije su koordinate celi
brojevi koji zadovoljavaju 0<=x<=9, 0<=y<=4 i neka je odabrana 21 tacka
iz S. Dokazati da postoji pravougaonik cija su temena medju odabranim
tackama, a stranice paralelne koordinatnim osama

Vrednost za x kojoj odgovara n odabranih tačaka zvaću kolonom sa n tačaka.

Prvi slučaj je da imamo bar jednu kolonu sa 4 tačke. Ako pritom postoji još jedna kolona sa bar 3 tačke, problem je rešen. U protivnom postoji još bar 7 kolona sa po bar dve tačke. I taj slučaj se lako rešava.

Ako nema ni jedne kolone sa bar 4 tačke, onda postoji bar jedna kolona sa 3 tačke. Ako ima još bar dve takve kolone, problem je rešen. Ako nema drugih kolona sa 3 tačke, onda preostalih 9 kolona sadrže po 2 tačke. Taj slučaj takođe nije teško rešiti.

Preostao je slučaj sa dve kolone sa po 3 tačke, a bez kolona sa više od 3 tačke. Tada imaš 7 kolona sa 2 tačke, a i tada se lako rešava.

Ovo je naravno uputstvo. Rešenje kompletiraj sam.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.