Točno
25. ožujka 2016. 17:25 (8 godine, 3 mjeseci)
Korisnik: dpaleka
Zadatak: Simulacija državnog 2016. za prvi razred zadatak 5. (Sakrij tekst zadatka)
Zadatak: Simulacija državnog 2016. za prvi razred zadatak 5. (Sakrij tekst zadatka)
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Kliknite ovdje kako biste prikazali rješenje.
Ekvivalentan zadatak: U ravnini je dano
točaka tako da su svake dvije udaljene barem za
. Dokažite da je točke moguće obojati u 4 boje tako da nijedan par točaka iste boje nije udaljen točno za
.
Neka se dvije točke dodiruju ako su udaljene točno za
.
Vršimo indukciju po
. Baza je trivijalna.
Promatrajmo konveksnu ljusku
zadanog skupa točaka.
Ako je ona pravac, tvrdnja je trivijalna, inače postoji
takav da je
.
Kao u ostalim rješenjima, zbrajanjem kuteva lako se dobije da se
dodiruje s najviše
točke.
Po pretpostavci indukcije, možemo valjano obojati sve točke osim
zanemarivši boju
. Pošto se
dodiruje s najviše
točke, postoji boja u koju je možemo obojati,
.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
Neka se dvije točke dodiruju ako su udaljene točno za
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
Vršimo indukciju po
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Promatrajmo konveksnu ljusku
![P_1P_2\ldots P_k](/media/m/6/7/c/67c816dfe3095eec38f1af0907d89c14.png)
Ako je ona pravac, tvrdnja je trivijalna, inače postoji
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![\angle P_{i-1}P_iP_{i+1} < 180^{\circ}](/media/m/a/0/7/a0708e9e79a391229b4294f910abf85c.png)
Kao u ostalim rješenjima, zbrajanjem kuteva lako se dobije da se
![P_i](/media/m/5/2/a/52aac5a799a979529859020a68515b1b.png)
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
Po pretpostavci indukcije, možemo valjano obojati sve točke osim
![P_i](/media/m/5/2/a/52aac5a799a979529859020a68515b1b.png)
![P_i](/media/m/5/2/a/52aac5a799a979529859020a68515b1b.png)
![P_i](/media/m/5/2/a/52aac5a799a979529859020a68515b1b.png)
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
![\text{QED}](/media/m/9/c/b/9cb2a0097a7b6bf76d08352436fe93b3.png)