Kombinatorika

Pozdrav vsem,

rešujem naloge iz kombinatorike pa mi nekatere niso jasne in prosim za pomoč.

1. Manca ima v denarnici precej kovancev po 1, 2 in 5 evrov in bankovec za 10 evrov. Na koliko načinov lahko plača izdelek, ki stane 17 evrov? (Rešitev: 23)

Nimam pojma, kako naj se je sploh lotim drugače kot brute force da štejem na roke.

2. Vnuki so stari mami kupili mobilni telefon. Da bi si laže zapomnila PIN-kodo so se domenili, da si izbere 4 števke iz svojega rojstnega datuma 24. 11. 1922. Koliko PIN-kod z različnimi števkami si lahko izbere? (Rešitev: 24)

Moje razmišljanje:

Števke: {2, 4, 1, 1, 1, 9, 2, 2}

Če bi bile števke različne, ne bi bilo problema: za 1. mesto bi imeli 8 možnosti, drugo 7, tretje 6 in četrto 5. Produkt teh bi bila končna rešitev.
V tej nalogi pa se števili 1 in 2 ponovita 3x. Na pamet mi padejo variacije s ponavljanjem (variacije, ker razporejamo n elementov na r mest in velja r < n)... od tod naprej pa ne znam več.

3. Na koliko načinov lahko med sestre Katarino, Uršo in Mojco razdelimo 7 knjig, če dobi vsaka vsaj eno knjigo? (Rešitev: 462)

Možne porazdelitve knjig so:
1-2-4
1-3-3
2-2-3
1-5-1

Kako sedaj prešteti možnosti?

4. Republiška maturitetna komisija za matematiko je v maturitetnem katalogu objavila 260 vprašanj: 65 iz 1. letnika, 68 iz drugega, 62 iz tretjega in 71 iz četrtega. Komisija vsako leto pripravi listke s po 3 vprašanji, vsak iz svojega letnika. Koliko različnih listkov bi lahko pripravili vsako leto? (Rešitev: 1 173 326)

Variacije in elementi se ponavljajo. Imamo 6 različnih možnosti za izbiro letnikov (3 * 2 * 1), vendar kako sedaj naprej?

5. Na koliko načinov lahko iz števk 0, 1, 2, 3, 5 in 7 sestavimo trimestno sodo število? (Rešitev: 60)

Da bo sodo, mora biti na koncu 0 ali 2.

_ _ 0 razporejamo preostalih 5 števk na 2 mesti, torej je teh možnosti = 5! / 3! (po formuli za variacije brez ponavljanja) = 20

_ _ 2 naredimo enako, samo da odštejemo tiste možnosti, ki se začnejo z 0, torej 5! / 3! - 4 = 16

Skupaj je 36, vendar ni prav... What am I doing wrong?

Se že vnaprej zahvaljujem za kakršnokoli pomoč!

Mah ja, sej v bistvu mam ta predmet na faxu, ampak preden se lotim tistih nalog, sem šla ponavljat vse iz gimnazije. Načeloma mi ne povzroča toliko težav, ker ostalih cca 90 sem znala rešit. Bodo pa tiste iz faxa dosti večji zalogaj, sploh v kombinaciji z verjetnostjo. :S

Na hitr

2) na voljo imaš 4 različne cifre (1,2,4,9)
Sestaviti moraš kombinacijo iz samih različnih, torej daš na prvo mesto lahko 4 cifre, nad drugo 3, na tretje 2, na zadnje 1.
4 3 2 1 => 4*3*2*1=24

5) 0, 1, 2, 3, 5 in 7
Imaš trimestno število. Na prvem mestu je lahko katerakoli cifra izmed (0, 1, 2, 3, 5 in 7), razen 0, torej je 5 možnosti, na drugem mestu je lahko katerakoli cifra, torej 6 možnosti in na zadnjem le 0 ali 2, torej 2 možnosti.
5 6 2 => 5*6*2=60

4)Izmed 4 razredov izbereš 3, torej = 4!/3!(4-3)! možnosti = 4
To so:
1 2 3 = 65*68*62=274040 (Vsakič izbereš eno vprašanje izmed 65/68/62/71), torej 65!/1!(65-1)!=65 in enako za ostale cifre
1 2 4 = 65*68*71=313820
1 3 4 = 65*62*71=286130
2 3 4 = 68*62*71=299336

Sešteješ te možnosti = 274040+313820+286130+299336=1173326

hehe, mogoče bo Math Freak vedel ...

Tudi meni pride 1806 s pomočjo programiranja:

def fakulteta(x):
    if x == 1:
        return x
    else:
        return x*fakulteta(x-1)

def knjige():
    total = 0
    subTotal = 0
    for Katarina in range(1,6):
        for Ursa in range(1,6): 
            for Mojca in range(1,6):
                if Mojca + Katarina + Ursa == 7:
                    subTotal = (fakulteta(7)//(fakulteta(Mojca)*fakulteta(Katarina)*fakulteta(Ursa)))
                    total += subTotal
                    print("Katarina:",Katarina,"Ursa:",Ursa,"Mojca:",Mojca,"Vseh možnosti:",subTotal)
    print("Vse možnosti skupaj:",total)
knjige()

Rezultat:

Katarina: 1 Ursa: 1 Mojca: 5 Vseh možnosti: 42
Katarina: 1 Ursa: 2 Mojca: 4 Vseh možnosti: 105
Katarina: 1 Ursa: 3 Mojca: 3 Vseh možnosti: 140
Katarina: 1 Ursa: 4 Mojca: 2 Vseh možnosti: 105
Katarina: 1 Ursa: 5 Mojca: 1 Vseh možnosti: 42
Katarina: 2 Ursa: 1 Mojca: 4 Vseh možnosti: 105
Katarina: 2 Ursa: 2 Mojca: 3 Vseh možnosti: 210
Katarina: 2 Ursa: 3 Mojca: 2 Vseh možnosti: 210
Katarina: 2 Ursa: 4 Mojca: 1 Vseh možnosti: 105
Katarina: 3 Ursa: 1 Mojca: 3 Vseh možnosti: 140
Katarina: 3 Ursa: 2 Mojca: 2 Vseh možnosti: 210
Katarina: 3 Ursa: 3 Mojca: 1 Vseh možnosti: 140
Katarina: 4 Ursa: 1 Mojca: 2 Vseh možnosti: 105
Katarina: 4 Ursa: 2 Mojca: 1 Vseh možnosti: 105
Katarina: 5 Ursa: 1 Mojca: 1 Vseh možnosti: 42
Vse možnosti skupaj: 1806

Še vse premutacije za recimo 1,1,5:

k1 k2 k3 k4 k5
k1 k2 k3 k4 k6
k1 k2 k3 k4 k7
k1 k2 k3 k5 k6
k1 k2 k3 k5 k7
k1 k2 k3 k6 k7
k1 k2 k4 k5 k6
k1 k2 k4 k5 k7
k1 k2 k4 k6 k7
k1 k2 k5 k6 k7
k1 k3 k4 k5 k6
k1 k3 k4 k5 k7
k1 k3 k4 k6 k7
k1 k3 k5 k6 k7
k1 k4 k5 k6 k7
k2 k3 k4 k5 k6
k2 k3 k4 k5 k7
k2 k3 k4 k6 k7
k2 k3 k5 k6 k7
k2 k4 k5 k6 k7
k3 k4 k5 k6 k7

Skupaj pride 21. Drugima dvema ostaneta le dve knjigi na izbiro. Torej če ena izbere eno -> bo druga izbrala drugo -> torej ostane še kar isto -> to je 21 možnosti. Če pa ti dve osebi zamenjata knjigi dobimo še dodatnih 21 možnosti -> skupaj pride 42. Upam da ti je kaj jasno =p. tale verjetnost zna bit zakomplicirana.

Če ne misliš podati rešitve ne bo šel nihče reševati.

Razdeliš 9 ljudi v 5 nadstropij => torej vsakega od 9 v eno od 5 nadstropij (hint: vključitev). Teh možnosti je 5⁹.
Odšteješ možnosti, pri katerih si vse razvrstil v 4 nadstropja - takrat je 1 nadstoprje prazno (hint: izključitev). Teh možnosti je 4⁹.
Izključiš še možnosti da si vse razdelil v 3,2 in 1 nadstropje.
Rešitev:
5⁹ - 4⁹ - 3⁹ - 2⁹ - 1⁹ = 1670785.

Edit: nisem čisto prepričan, ampak ne vidim drugega načina.

Človek ni kroglica, zato je pomembno ali je oseba A v 1. nadstropuj ali je oseba A. v drugem nadstropju. Tu še moraš permutirat osebe. Vsaj mi smo meli pri matematiki dogovor, da ko je bila naloga z ljudmi, smo morali razlikovat med njimi. Pri tej nalogi je smiselno vprašanje za tistega ki jo je zastavil, če moramo razlikovati med osebami ali ne. Če ne, potem se naloga prevede na problem: Na koliko načinov lahko seštejemo 5 števil da dobimo vsoto 9, kar je stipy rešil in zračunal.