Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Četvrtak, 14. Jun 2018, 15:27
od Nastasjaa
Rečnik sadrži sve reči od [inlmath]5[/inlmath] slova koje se mogu obrazovati od tri različita slova skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath]. Ako je [inlmath]n[/inlmath] broj reči u tom rečniku, koliko iznosi [inlmath]n[/inlmath]?

Teško se snalazim sa kombinatorikom, problem mi je da uopšte krenem da sagledavam problem, da li bi neko mogao da mi pomogne?

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Četvrtak, 14. Jun 2018, 19:27
od Daniel
Tekst zadatka mi se čini prilično konfuzan i nisam siguran jesam li ga dobro razumeo, da li zaista tako glasi u originalu? Dakle, da li mi prvo iz skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath] biramo tri različita slova (npr. [inlmath]A[/inlmath], [inlmath]D[/inlmath] i [inlmath]F[/inlmath]), a zatim od ta tri različita slova formiramo reči od pet slova (npr. [inlmath]AADAF[/inlmath], [inlmath]DAFFD[/inlmath], [inlmath]FAFDF[/inlmath] itd.)? Znači, ako sam dobro razumeo, svako od tri različita slova mora u svakoj reči biti bar jednom iskorišćeno, tj. nisu dozvoljene npr. reči [inlmath]AFAAF[/inlmath] ili [inlmath]DDDDD[/inlmath]?

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Četvrtak, 14. Jun 2018, 19:55
od Daniel
Izguglah u međuvremenu taj zadatak, i zaista tako glasi. Mogli su baš malo preciznije da ga sroče. Mislim da je moja pretpostavka koju sam gore izneo tačna, jer radeći na taj način dobijem rezultat [inlmath]n=3000[/inlmath], što se uklapa u interval koji su naveli kao tačan, a koji glasi [inlmath]3000\le n<3500[/inlmath].

Haj'mo za početak, na koliko načina možemo iz skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath] odabrati tri različita slova? To bi trebalo da znaš.

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Četvrtak, 14. Jun 2018, 20:28
od diopo
Ja sam zbunjen takodje, zato nisam ni hteo da odgovorim da ne bih napravio zbrku, ali posle tvog odgovora moram da te pitam nesto.

Mozes li da objasnis sta ti je u tekstu dalo do znanja da svako slovo mora da bude upotrebljeno bar jednom, jer sam ga ja citao sto puta i i dalje me vuce da postoji mogucnost za reci tipa [inlmath]AAAAA[/inlmath], [inlmath]BBBBA[/inlmath], itd .. ? :/

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Četvrtak, 14. Jun 2018, 20:38
od Daniel
To sam pretpostavio na osnovu ovog crveno obeleženog:
Nastasjaa je napisao:Rečnik sadrži sve reči od [inlmath]5[/inlmath] slova koje se mogu obrazovati od tri različita slova skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath].

Ali, opet kažem, ne tvrdim sa stoprocentnom sigurnošću, jer je tekst zadatka bože sačuvaj. S ovom svojom pretpostavkom dobijam [inlmath]3000[/inlmath], što se uklapa u tačan rezultat, ali i kad bih uzeo u obzir i te primere koje si naveo, dobio bih [inlmath]3486[/inlmath], što se opet uklapa u interval koji je naveden kao tačan.

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Sreda, 13. April 2022, 18:17
od piglet993
Da li može neko da objasni ideju kako ovo treba da se reši?

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Petak, 24. Jun 2022, 19:23
od Mia
Ja bih ovo radila tako sto prvo od [inlmath]6[/inlmath] ponudjenih slova izaberem [inlmath]3[/inlmath] to je moguće uraditi na [inlmath]20[/inlmath] načina zatim od svih mogućih slučajeva oduzmemo one gde su izostavljeni [inlmath]1[/inlmath] ili [inlmath]2[/inlmath] slova u formiranju reči odnosno
[dispmath]{6\choose3}\cdot\left(3^5-{3\choose2}\cdot2^5+3\right)[/dispmath] plus [inlmath]3[/inlmath] bih objasnila s tim da kad smo oduzeli
[dispmath]{3\choose2}\cdot2^5[/dispmath] mi smo ustvari [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]XXXXX[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]ZZZZZ[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]YYYYY[/inlmath] gde su [inlmath]x,y,z[/inlmath] prvo, drugo, trece izabrano slovo dakle [inlmath]3[/inlmath] od tih [inlmath]6[/inlmath] nam je visak zato plus [inlmath]3[/inlmath]. Nadam se da je tacno i razumljivo :D

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Subota, 25. Jun 2022, 14:43
od Daniel
Mia je napisao:mi smo ustvari [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]XXXXX[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]ZZZZZ[/inlmath], [inlmath]2[/inlmath] puta oduzeli slucaj [inlmath]YYYYY[/inlmath] gde su [inlmath]x,y,z[/inlmath] prvo, drugo, trece izabrano slovo dakle [inlmath]3[/inlmath] od tih [inlmath]6[/inlmath] nam je visak zato plus [inlmath]3[/inlmath].

Tako je, to se zove princip uključenja i isključenja.

Re: Broj reči u rečniku – prijemni FON 2002.

PostPoslato: Utorak, 02. Avgust 2022, 13:49
od nadja
Pozdrav svima, evo kako sam ja razmišljala:
Dakle, kao što ste već rekli, od skupa [inlmath]\{A,B,C,D,E,F\}[/inlmath] se mogu načiniti [inlmath]{6\choose 3} = 20[/inlmath] podskupa od 3 elementa.
E sad, da bih izračunala koliko riječi možemo napraviti od ta 3 elementa koristila sam onu formulu za izračunavanje n-varijacija tipa
[inlmath](k_1,k_2...,k_m)[/inlmath] pri čemu je [inlmath]k_1 + k_2 + .... +k_m = n[/inlmath] koja glasi [dispmath]\frac{n!}{k_1!k_2!\cdots k_m!}[/dispmath]
Znači, uzmimo samo za primjer podskup [inlmath]\{A,B,C\}[/inlmath].
Prvi tip je [inlmath](5,0,0)[/inlmath], tj. [inlmath]A[/inlmath] se ponavlja 5 puta. Takvih varijacija ima [inlmath]\frac{5!}{5!} = 1[/inlmath]. S obzirom da ovu peticu gore možemo rasporediti na 3 načina (tj. imamo još tipove [inlmath](0,5,0)[/inlmath]-> B se ponavlja 5 puta i [inlmath](0,0,5)[/inlmath]-> C se ponavlja 5 puta), riječi gdje se svako slovo pojavljuje 5 puta [inlmath](AAAAA,\enspace BBBBB,\enspace CCCCC[/inlmath]) je 3.

Hajdemo dalje:
Sljedeći tip je [inlmath](1,4,0)[/inlmath]-> [inlmath]A[/inlmath] se pojavljuje 1, a [inlmath]B[/inlmath] 4 puta. Takvih rasporeda ima [inlmath]\frac{5!}{1!4!}=5[/inlmath]. S obzirom da gore navedenu jedinicu i četvorku možemo rasporediti na [inlmath]3!=6[/inlmath] načina(tj. imamo još ove tipove: (4,1,0), (1,0,4), (4,0,1) i sve ostale moguće varijacije), a za svaki tip imamo 5 riječi, ukupno imamo [inlmath]5\cdot6=30[/inlmath] riječi gdje se 1 slovo ponavlja 4 puta, drugo se pojavljuje samo jednom, a treće se uopšte ne pojavljuje.

Sljedeći tip je [inlmath](2,3,0)[/inlmath]. Ovakvih riječi imamo [inlmath]\frac{5!}{2!3!}=10[/inlmath]. Pošto ovakvih tipova (sa 2 i 3) imamo ukupno [inlmath]3!=6[/inlmath]. Imamo [inlmath]6\cdot10=60[/inlmath] ovakvih riječi.

Sljedeći tip je [inlmath](1,1,3)[/inlmath]. Ovakvih riječi je [inlmath]\frac{5!}{1!1!3!}=20[/inlmath]. Ovakih tipova(sa 2 jedinice i tricom) ima [inlmath]{3\choose1}=3[/inlmath]. Znači, ovakvih riječi imamo [inlmath]3\cdot20=60[/inlmath]

I ostao nam je još samo jedan tip [inlmath](1,2,2)[/inlmath]. Ovakvih riječi je [inlmath]\frac{5!}{1!2!2!}=30[/inlmath]. Ovakvih tipova (sa jedinicom i 2 dvice) ima [inlmath]{3\choose1}=3[/inlmath](tj. pored prve varijacije imamo još:[inlmath](2,1,2), (2,2,1)[/inlmath]). Znači ukupno ih ima: [inlmath]3\cdot30=90[/inlmath]

E sad dolazimo do najvažnijeg dijela: rezultata.
Ako se ne moraju sva slova iz podskupa pojaviti u riječi, onda ih imamo: [dispmath]20\cdot(90+60+60+30)=4800[/dispmath]
Ako to nije dozvoljno, onda imamo(kao što je Mia čini mi se izračunala): [dispmath]20\cdot(90+60)=3000[/dispmath]

Znam da je malo konfuzno, tako da me slobodno pitajte ako vam šta nije jasno, potrudiću se da što prije odgovorim. Pozdrav!