Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI KOMBINATORIKA

Pravougaonik čiji su vrhovi iste boje

[inlmath]{n\choose k}=\frac{n!}{\left(n-k\right)!k!}[/inlmath]

Moderator: Corba248

  • +1

Pravougaonik čiji su vrhovi iste boje

Postod xyz » Nedelja, 29. Maj 2016, 16:26

Pozdrav, ako može pomoć oko zadatka.
Neka su sve tačke u ravni obojene u dvije boje. Dokazati da postoji pravougaonik čiji su vrhovi iste boje.

Nemam nikakvu ideju, samo znam da se postojanje jednakostraničnog trougla sa ovom osobinom može dokazati pomoću tjemena pravilnog šestougla i centra opisane kružnice oko njega.
xyz  OFFLINE
 
Postovi: 15
Zahvalio se: 5 puta
Pohvaljen: 12 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Pravougaonik čiji su vrhovi iste boje

Postod desideri » Nedelja, 29. Maj 2016, 19:04

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

Nejasno mi je.
Šta ako je samo jedna tačka obojena jednom bojom a sve ostale obojene drugom bojom?
Onda nema rešenja.
Drugo potpitanje je šta su "vrhovi pravougaonika"?
Nisam nikada čuo za to.
Šta ako okrenem pravougaonik, da li su tada "vrhovi" zapravo "dna" pravougaonika?
Po mom mišljenju ovo je neprecizno postavljen zadatak.
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1516
Lokacija: Beograd
Zahvalio se: 1087 puta
Pohvaljen: 836 puta

Re: Pravougaonik čiji su vrhovi iste boje.

Postod Onomatopeja » Nedelja, 29. Maj 2016, 19:18

Ovo je poznat zadatak. Samo, da bi formulacija bila dobra je potrebno zameniti rec „vrhovi“ sa „temena“ (i dobro, onda i „čiji“ u „čija“).

Ne bih odmah da otkrivam resenje (jedno od), posto verujem da i drugima moze biti zanimljiv sam zadatak. (@xyz: ako niko ne uskoci, pokazacu ja kako se radi (ne sve naravno, dovoljne su instrukcije))
 
Postovi: 588
Zahvalio se: 15 puta
Pohvaljen: 555 puta

Re: Pravougaonik čiji su vrhovi iste boje

Postod xyz » Nedelja, 29. Maj 2016, 20:30

Da, naravno, u pitanju su tjemena pravougaonika. Ako hoće neko od admina može da ispravi.
xyz  OFFLINE
 
Postovi: 15
Zahvalio se: 5 puta
Pohvaljen: 12 puta

Re: Pravougaonik čiji su vrhovi iste boje

Postod Daniel » Ponedeljak, 30. Maj 2016, 09:05

Mislim da nema potrebe.
Primetio sam da je dosad postavljeno dosta zadataka u kojima je upotrebljen izraz vrh u smislu teme, tako da sam malo pretražio i video na hrvatskoj Wikipediji sledeću definiciju pojma vrh:
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

Po ovoj drugoj definiciji pojma vrh, sasvim je u redu (makar na hrvatskom govornom području) reći vrh trougla, vrh pravougaonika, vrh mnogougla... Naravno, ima isto značenje kao i teme.



@Desideri, kada bi samo jedna tačka u ravni bila obojena jednom bojom a sve ostale tačke te iste ravni obojene drugom bojom, onda bi dokaz bio trivijalan – bilo bi dovoljno uočiti bilo koji pravougaonik u toj ravni čije se nijedno teme ne poklapa s tom jednom tačkom koja je različite boje.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7324
Lokacija: Beograd
Zahvalio se: 3808 puta
Pohvaljen: 3958 puta

  • +1

Re: Pravougaonik čiji su vrhovi iste boje

Postod xyz » Ponedeljak, 30. Maj 2016, 15:43

Provjerio sam predavanja iz geometrije. Prof. Vojislav Petrovič (PMF Novi Sad) spominje u svojim predavanjima izraz "teme(vrh)". Možete se uvjeriti i sami http://people.dmi.uns.ac.rs/~vojpet/Isp ... anja1.html pod predavanja.
xyz  OFFLINE
 
Postovi: 15
Zahvalio se: 5 puta
Pohvaljen: 12 puta

Re: Pravougaonik čiji su vrhovi iste boje

Postod desideri » Ponedeljak, 30. Maj 2016, 23:32

Nisam znao šta je "vrh" pravouganika.
Sada mi je jasno. :)
p.s. terminološki nesporazum. :(
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1516
Lokacija: Beograd
Zahvalio se: 1087 puta
Pohvaljen: 836 puta

  • +1

Re: Pravougaonik čiji su vrhovi iste boje

Postod xyz » Sreda, 01. Jun 2016, 13:00

Neka su sve tačke u ravni obojene u crvenu i plavu boju. Povucimo [inlmath]9[/inlmath] horizontalnih paralelnih pravih. Nakon toga povucimo [inlmath]3[/inlmath] okomite prave na date prave i posmatrajmo presjeke tj. posmatrajmo presječne tačke. Na svakoj od [inlmath]9[/inlmath] horizontalnih pravih imamo po [inlmath]3[/inlmath] presječne tačke. Formirajmo skup [inlmath]S[/inlmath] svih mogučih varijacija [inlmath]2[/inlmath] boje ([inlmath]C[/inlmath] i [inlmath]P[/inlmath]) na tri tačke. Tada je
[inlmath]S=\{CCC,CCP,CPC,PCC,PPC,PCP,CPP,PPP\}[/inlmath]. Imamo [inlmath]8[/inlmath] mogućih različitih rasporeda boja na tri tačke a [inlmath]9[/inlmath] paralelnih horizontalnih pravih pa prema Dirihleovom principu zaključujemo da će bar dvije horizontalne prave imati presječne tačke iste boje. Prema tome zbog konstrukcije ovakvih pravih imamo pravougaonik čija su tjemena iste boje.
xyz  OFFLINE
 
Postovi: 15
Zahvalio se: 5 puta
Pohvaljen: 12 puta

Re: Pravougaonik čiji su vrhovi iste boje

Postod nkole » Utorak, 04. Septembar 2018, 18:39

Š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...
nkole  OFFLINE
 
Postovi: 12
Zahvalio se: 4 puta
Pohvaljen: 1 puta


Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 12 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 15. Novembar 2018, 19:31 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs