|
[quote="Anđelčić"]2)U ravnini je dano n>4 točaka u općem položaju. Dokažite da postoji barem (n-3) povrh 2 konveksnih četverokuta sa vrhovima u tim točkama.
Kakvu ulogu u prebrojavanju igra konveksnost?[/quote]
Može se dogoditi da četiri točke određuju konveksni četverokut, tj. konveksna ljuska im je konveksni četverokut.
Ali može se dogoditi i da je konveksna ljuska trokut, tj. tri točke su vrhovi trokuta, a četvrta je unutar njega.
Dakle, nije da svaka četvorka točaka čini vrhove konveksnog četverokuta.
Meni pada na pamet recimo ovakvo rješenje:
Konveksna ljuska tog skupa točaka je neki mnogokut i neka su A,B,C tri uzastopna vrha tog mnogokuta.
(Dobro bi došla skica.)
Među preostalih n-3 točaka ima (n-3 povrh 2) neuređenih parova. Svaki takav par točaka {X,Y} zajedno s nekim (bar jednim) parom {A,B}, {A,C}, {B,C} čini konveksni četverokut.
Zašto je tome tako?
Evo pokušaja skice:
[code:1] B
A C
ostale točke su
negdje ovdje[/code:1]
Ako je npr. X izvan trokuta ABC, onda A,B,C,X čine vrhove konv.čet.
Isto tako i za Y.
Ako su i X i Y unutar trokuta ABC, onda X,Y i još dvije točke iz {A,B,C} čine konv.čet. (Nacrtaj sliku.)
Dakle, konv. četverokuta ima barem koliko parova {X,Y}, tj. (n-3 povrh 2).
[quote="Anđelčić"]3)Dokažite (n+1)|(2n povrh n),neIN[/quote]
Primijetimo da je
(2n+1)/(n+1) * (2n povrh n) = (2n+1 povrh n+1)
što možemo pisati
(2n+1)*(2n povrh n) = (n+1)*(2n+1 povrh n+1)
Dakle n+1 dijeli lijevu stranu jednakosti.
Ali n+1 i 2n+1 su relativno prosti zbog
2(n+1)-(2n+1)=1 (tj. njihova mjera dijeli 1)
pa n+1 dijeli (2n povrh n)
Inače, brojevi (2n povrh n)/(n+1) se zovu Catalanovi brojevi i imaju kombinatornu interpretaciju iz koje se vidi da su to cijeli brojevi. Ali o tome ne bih.
| Anđelčić (napisa): | 2)U ravnini je dano n>4 točaka u općem položaju. Dokažite da postoji barem (n-3) povrh 2 konveksnih četverokuta sa vrhovima u tim točkama.
Kakvu ulogu u prebrojavanju igra konveksnost? |
Može se dogoditi da četiri točke određuju konveksni četverokut, tj. konveksna ljuska im je konveksni četverokut.
Ali može se dogoditi i da je konveksna ljuska trokut, tj. tri točke su vrhovi trokuta, a četvrta je unutar njega.
Dakle, nije da svaka četvorka točaka čini vrhove konveksnog četverokuta.
Meni pada na pamet recimo ovakvo rješenje:
Konveksna ljuska tog skupa točaka je neki mnogokut i neka su A,B,C tri uzastopna vrha tog mnogokuta.
(Dobro bi došla skica.)
Među preostalih n-3 točaka ima (n-3 povrh 2) neuređenih parova. Svaki takav par točaka {X,Y} zajedno s nekim (bar jednim) parom {A,B}, {A,C}, {B,C} čini konveksni četverokut.
Zašto je tome tako?
Evo pokušaja skice:
| Kod: | B
A C
ostale točke su
negdje ovdje |
Ako je npr. X izvan trokuta ABC, onda A,B,C,X čine vrhove konv.čet.
Isto tako i za Y.
Ako su i X i Y unutar trokuta ABC, onda X,Y i još dvije točke iz {A,B,C} čine konv.čet. (Nacrtaj sliku.)
Dakle, konv. četverokuta ima barem koliko parova {X,Y}, tj. (n-3 povrh 2).
| Anđelčić (napisa): | | 3)Dokažite (n+1)|(2n povrh n),neIN |
Primijetimo da je
(2n+1)/(n+1) * (2n povrh n) = (2n+1 povrh n+1)
što možemo pisati
(2n+1)*(2n povrh n) = (n+1)*(2n+1 povrh n+1)
Dakle n+1 dijeli lijevu stranu jednakosti.
Ali n+1 i 2n+1 su relativno prosti zbog
2(n+1)-(2n+1)=1 (tj. njihova mjera dijeli 1)
pa n+1 dijeli (2n povrh n)
Inače, brojevi (2n povrh n)/(n+1) se zovu Catalanovi brojevi i imaju kombinatornu interpretaciju iz koje se vidi da su to cijeli brojevi. Ali o tome ne bih.
|
Baš je super ovaj forum! Dobiješ odgovor dok kažeš "keks"!
