| Luet Solmun keskustelupalstan arkistoa. Uusia viestejä ei voi enää kirjoittaa. |
 |
| Matematiikan atrium › Keskustelu matematiikasta › Tehtäväpalsta › miten lasketaan |
| ‹ Edellinen aihe | Seuraava aihe › |
 Sivu: 1
|
 miten lasketaan (Luettu 58 kertaa)
|
|
wilberi
YaBB Newbies
 Poissa  I Love YaBB 2! Viestejä: 1 |
miten lasketaan03.02.2009 - 13:39:46
Kuinka monella tavalla 10m pitkä naru voidaan katkaista kolmeksi naruksi, niin että osat ovat tasametrejä? Löydän vastauksen kokeilemalla, mutta voiko tämän ihan oikeesti myös laskea funktiolla tai jollakin?
|
| Siirry sivun alkuun |
 IP on kirjattu |
|
Jordan
YaBB Newbies
Poissa I Love YaBB 2! Viestejä: 16 |
Re: miten lasketaan Vastaus #1 - 06.02.2009 - 16:12:43
Hei. Oleellisesti on tietenkin kyse siitä, että kuinka monella tavalla luku 10 voidaan esittää kolmen positiivisen kokonaisluvun summana. Pienen pähkäilyn jälkeen voi keksiä funktion f, joka kertoo kuinka monella tavalla kukin positiivinen kokonaisluku voidaan esittää kolmen positiivisen kokonaisluvun summana. Itse en tosin saanut funktiosta sievennettyä mitään hirveän nättiä. Saamani funktio on
f(n)=\sum_{k=1}^{\floor{n/3}}(1+\floor{(n-3k)/2}). Tässä siis \floor{x} on suurin kokonaisluku, joka on pienempi kuin x (lattiafunktio) ja \sum_{k=i}^{j}a_k tarkoittaa summaa a_i+a_{i+1}+...+a_j. Päädyin tähän, kun rupesin miettimään, että kuinka monella tavalla luku n voidaan esittää kolmen luvun summana, kun kiinnitetään yksi luvuista. Sanotaan vaikka, että yksi summan termeistä on kokonaisluku k ja olkoon p_k(n) niiden luvun n esitystapojen lukumäärä, joissa pienin summan termeistä on k (tarkastellaan edelleen esityksiä kolmen luvun summana). Ensinnäkin p_k(n) on nollasta poikkeava vain kun n on suurempi tai yhtä kuin 3k (pienin termi oli k, joten summa on vähintään k+k+k=3k). Seuraavaksi kannattaa lähteä tarkastelemaan lukua p_k(n) kahdelle peräkkäiselle n. Pienen pähkäilyn jälkeen huomaa, että p_k(n+1)-p_k(n) voi olla vain nolla tai yksi ja arvo riippuu vain lukujen k ja n parillisuudesta. Tarkemmin: p_k(n+1)-p_k(n)=(1-(-1)^(k+n))/2. Tästä voi sitten päätellä, että p_k(n)=1+\floor{(n-3k)/2} (kun n on suurempi tai yhtä kuin 3k). Kaikkien esitysten lukumäärä saadaan, kun summataan k:n yli. Piti olla n suurempi tai yhtä kuin 3k, joten summataan k:n arvoon \floor{n/3} asti. Tällöin saadaan tuo ylläoleva funktio. Voi olla, että tässä on jotain virheitä tai, että voidaan sieventää vielä lisää, mutta minä päädyin tällaiseen. |
| Siirry sivun alkuun |
IP on kirjattu |
|
hipsishopsis
YaBB Newbies
Poissa Viestejä: 4 Sukupuoli:  |
Re: miten lasketaan Vastaus #2 - 19.05.2009 - 21:43:19
Hei!
Ongelman voi ensinnäkin käsittää (ainakin) kahdella tavalla. Helpompi ongelmista on seuraava: 10 metrin naru ositetaan kolmeksi s.e. esimerkiksi ositukset (2,5,3) ja (3,5,2) ovat eri ositukset. Toisin sanoen sillä on väliä, otettiinko 2 metrin pätkä narun alku vai loppupäästä. Tämä ongelma yleistyy seuraavasti: Halutaan laskea, montako ratkaisua on yhtälöllä x_1 + x_2 + ... + x_n = M kun x_1, ..., x_n ovat positiivisia kokonaislukuja. Ongelmaa on helpointa lähteä ratkomaan hieman muunnellun ongelman kautta: Montako ratkaisua on yhtälöllä x_1 + x_2 + ... + x_n = M kun x_1, ..., x_n ovat epä-negatiivisia kokonaislukuja (ts. 0 on sallittu). Klassinen tapa on tarkastella M+n-1:tä vierekkäin asetettua kiveä. Otetaan esimerkiksi M = 10, n = 3: * * * * * * * * * * * * Kun 2 näistä kivistä muunnetaan väliseiniksi, saadaan tilanne kuten alla: * * * | * | * * * * * * Tämä tilanne vastaa yhtälön ratkaisua x_1 = 3, x_2 = 1, x_3 = 6. On helppo havaita, että tällaisten kivikyhäelmien ja ratkaisujen välissä on bijektio, maallikkotermein niitä on yhtäpaljon, sillä kutakin ratkaisua vastaa kyhäelmä ja päinvastoin. Kyhäelmien määrä on helppo laskea binomikertoimen avulla: / m + n - 1 \ \ n - 1 / eli valitsemme m + n - 1:stä kivestä n - 1. Jos nyt halutaan, että kaikki luvut ovat positiivisia, tehdään seuraava trikki: Lasketaan, montako ratkaisua on yhtälöllä x_1 + x_2 + x_3 = 7 kun x_1, x_2, x_3 saavat olla nollia. Tämän jälkeen lisätään kaikkiin muuttujiin 1 ja saadaan ratkaisu y_1 = x_1 + 1, y_2 = x_2 + 1, y_3 = x_3 + 1 alkuperäiselle ongelmalle y_1 + y_2 + y_3 = 10. Huh.. tuleepas pitkä viesti. Vaikeampi ongelma on kun ositukset (3,5,2) ja (5,3,2) ajatellaan samoina. Tällöin puhutaan kokonaisluvun 10 osituksista. Olkoot p(n,k) luvun n ositus k:hon osaan (alkuperäinen ongelma käsittelee siis lukua p(10,3).) Todistetaan seuraava rekursiokaava: p(n,k) = p(n-k,k) + p(n-1,k-1). Koska kaikki osat ovat > 1 voidaan jokaisesta osasta ottaa 1 pois. Jää ositettavaksi luku n-k, mutta nyt osa luvuista voi olla nollia. Jos oletetaan, että mikään ei ole nolla, on osituksia p(n-k,k), jos 1 osista on nolla, niitä on p(n-k,k-1) jne. Saadaan p(n,k) = p(n-k,k) + p(n-k,k-1) + ... + p(n-k,1) + p(n-k,0) Sijoittamalla n->n+1 ja k->k+1 saadaan p(n+1,k+1) = p(n-k,k+1) + p(n-k,k) + ... + p(n-k,1) + p(n-k,0) Nyt vähentämällä ensimmäinen yhtälö toisesta saadaan p(n+1,k+1) - p(n,k) = p(n-k,k+1) eli p(n+1,k+1) = p(n-k,k+1) + p(n,k) Edelleen sijoittamalla n+1 -> n ja k+1 -> k saadaan p(n,k) = p(n-k,k) + p(n-1,k-1). Tämä rekursiokaava on vain yksi tapa laskea ositusten määrää; asiaa on tutkittu aika paljon, ja kannattaa vaikkapa googlata "Integer partitions". |
| Siirry sivun alkuun |
IP on kirjattu |
|
Sivu: 1
|
| ‹ Edellinen aihe | Seuraava aihe › |
