|
[quote="krcko"]Evo jednog zadatka nakon seminara. Negdje sam procitao da se ovo zove Transilvanijski loto, ali nemojte me pitati organizira li grof Drakula upravo ovakvu igru...
Biraju se 3 broja od 14. Zadatak je odrediti minimalni broj trojki koje garantiraju pogadjanje bar 2 izvucena broja.
Prema teoremu iskazanom na seminaru treba uplatiti barem 14 trojki. U ovom slucaju to je i dovoljno - pokusajte naci 14 trojki koje garantiraju bar 2 pogotka! Svi sastojci rjesenja dani su na seminaru, samo ih treba prepoznati i primijeniti na pravi nacin :)[/quote]
BSOMP (bez smanjenja opcenitosti mozemo pretpostaviti) da su brojevi prikazani sortiranim trojkama.
Pretpostavimo da svaka od 14 trojki pocinje razlicitim brojem, tj. da i-ta pocinje brojem i.
Tada izaberemo i=1, pa imamo samo jednu trojku (i,x,y). Neka je a<>i,x,y. Tada postoji jedinstveni (a,w,z). Neka je b<>1,x,y,a,w,z (njih ima 6, pa takav postoji). Tvrdimo da (1,a,b) ne zadovoljava tvrdnju zadatka (prilicno ocito).
Pretpostavimo sada da postoji i takav da ne postoji (i,x,y). Uzmimo a<>i,x,y i to takav da trojki (a,w,z) ima najmanje. Biramo b kao gore (razlicit sa svim brojevima u igri). Ako takav b postoji, onda je (i,a,b) trazena trojka.
Ako takav b ne postoji, to znaci da ima barem 5 trojki koje pocinju sa a. No, a biramo iz skupa {1..14}\{i,a,x} koji ima 11 elemenata. Kako smo a izabrali po kriteriju "najmanje takvih", to ce reci da ima 11 a-ova takvih da 5 trojki pocinje s njima. To je 55 trojki... :)
Ako nisam bas jako promasio, reklo bi se da moramo uzeti vise od 14 trojki.
Ja mislim da je rjesenje 26. Imam i neko klimavo objasnjenje, ali pustit cu druge. Do tada, evo jedne 26-orke:
[code:1]1,2,3
1,4,13
1,5,10
1,6,9
1,7,8
1,11,12
2,4,9
2,5,12
2,6,7
2,8,10
2,11,13
3,4,11
3,5,14
3,6,8
3,7,9
3,10,12
4,5,6
4,7,10
4,8,12
5,7,11
5,8,9
6,10,11
6,12,13
7,12,14
8,11,14
9,10,13
[/code:1]
Pozdrav svima!
| krcko (napisa): | Evo jednog zadatka nakon seminara. Negdje sam procitao da se ovo zove Transilvanijski loto, ali nemojte me pitati organizira li grof Drakula upravo ovakvu igru...
Biraju se 3 broja od 14. Zadatak je odrediti minimalni broj trojki koje garantiraju pogadjanje bar 2 izvucena broja.
Prema teoremu iskazanom na seminaru treba uplatiti barem 14 trojki. U ovom slucaju to je i dovoljno - pokusajte naci 14 trojki koje garantiraju bar 2 pogotka! Svi sastojci rjesenja dani su na seminaru, samo ih treba prepoznati i primijeniti na pravi nacin  |
BSOMP (bez smanjenja opcenitosti mozemo pretpostaviti) da su brojevi prikazani sortiranim trojkama.
Pretpostavimo da svaka od 14 trojki pocinje razlicitim brojem, tj. da i-ta pocinje brojem i.
Tada izaberemo i=1, pa imamo samo jednu trojku (i,x,y). Neka je a<>i,x,y. Tada postoji jedinstveni (a,w,z). Neka je b<>1,x,y,a,w,z (njih ima 6, pa takav postoji). Tvrdimo da (1,a,b) ne zadovoljava tvrdnju zadatka (prilicno ocito).
Pretpostavimo sada da postoji i takav da ne postoji (i,x,y). Uzmimo a<>i,x,y i to takav da trojki (a,w,z) ima najmanje. Biramo b kao gore (razlicit sa svim brojevima u igri). Ako takav b postoji, onda je (i,a,b) trazena trojka.
Ako takav b ne postoji, to znaci da ima barem 5 trojki koje pocinju sa a. No, a biramo iz skupa {1..14}\{i,a,x} koji ima 11 elemenata. Kako smo a izabrali po kriteriju "najmanje takvih", to ce reci da ima 11 a-ova takvih da 5 trojki pocinje s njima. To je 55 trojki...
Ako nisam bas jako promasio, reklo bi se da moramo uzeti vise od 14 trojki.
Ja mislim da je rjesenje 26. Imam i neko klimavo objasnjenje, ali pustit cu druge. Do tada, evo jedne 26-orke:
| Kod: | 1,2,3
1,4,13
1,5,10
1,6,9
1,7,8
1,11,12
2,4,9
2,5,12
2,6,7
2,8,10
2,11,13
3,4,11
3,5,14
3,6,8
3,7,9
3,10,12
4,5,6
4,7,10
4,8,12
5,7,11
5,8,9
6,10,11
6,12,13
7,12,14
8,11,14
9,10,13
|
Pozdrav svima!
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
Nesto ocito ne stima.
