Rješenja zadatka "Simulacija općinskog 2016. za prvi razred zadatak 5." korisnika "ikicic"

Točno

11. siječnja 2016. 00:50 (8 godine, 10 mjeseci)

Korisnik: ikicic
Zadatak: Simulacija općinskog 2016. za prvi razred zadatak 5. (Sakrij tekst zadatka)

Svaki od $n$ kuhara zna dio nekog recepta za kolač (i svi znaju različite dijelove recepta, a zajedno znaju čitav recept). Dopušteno im je razmjenjivanje svih informacija koje znaju preko telefona, ali tako da u jednom telefonskom razgovoru sudjeluju točno dva kuhara i tijekom tog razgovora točno jedan od njih govori. Odredite najmanji broj telefonskih poziva potrebnih da bi svi kuhari znali čitav recept.

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Namjanji broj poziva je $2n - 2$ , uz sljedeći niz poziva ( $a \to b$ označava da kuhar broj $a$ zove kuhara broj $b$ te mu govori sve što zna).
$1 \to 2, 2 \to 3, \ldots, n - 1 \to n$ ,
$n \to 1, n \to 2, \ldots, n \to n - 1$ .

Da bismo dokazali da nije moguće u manje koraka izmjeniti sve informacije, dovoljno je primijetiti da nakon $n - 1$ postoji barem jedan kuhar koji nikoga još nije nazvao. Da bi se njegov dio recepta prenio do ostalih, potrebno je obaviti barem $n - 1$ poziva. Ukupno, dakle $2n - 2$ .

Školjka

Ocjene: (1)