Käytössä on kolme kirjainta, A, B ja C. Näistä voidaan muodostaa esimerkiksi neljän kirjaimen merkkijono ABBA. Kuinka monta merkkijonoa, jossa on n kirjainta ja joissa on parillinen määrä A-kirjaimia, voidaan muodostaa, kun n on positiivinen kokonaisluku.
(MAOL lukion matematiikkakilpailu 2015)
Mielenkiintoinen kisatehtävä, en osannut ratkaista itse. Onko hyviä ideoita miten kannattaisi lähteä ratkaisemaan?
(MAOL lukion matematiikkakilpailu 2015)
Mielenkiintoinen kisatehtävä, en osannut ratkaista itse. Onko hyviä ideoita miten kannattaisi lähteä ratkaisemaan?
Vastaukset 11
Vanhimmat
A(n) on n-kirjaimisten jonojen määrä.
rekursiomuodossa saadaan
a(1)=2
a(n 1)=2a(n) (3^n-a(n))=3^n a(n),
josta voidaan ratkaista
a(n)=(3^n 1)/2
Tuossa tehtävässä olisi ollut hyvä mainita että ei yhtään (0) A-kirjainta katsotaan parilliseksi määräksi. Vaikkakin 0 kai määritellään parilliseksi luvuksi.
Tuon ratkaisun logiikka on kai että otetaan kaikki ne n-mittaiset jonot joissa on parillinen määrä A-kirjaimia ja lisätään perään B tai C, ja toisaalta otetaan kaikki ne n-mittaiset jonot jossa on pariton määrä A-kirjaimia, ja lisätään perään A. Näin saadaan kaikki kysytyt n 1 mittaiset jonot.
Aika vaikea jos on kyseessä alkukilpailu, joskin helppo sitten kun keksii oikean idean.
En tiedä mikä on oikea vastaus... Pohdin tuota siten, että miten kuviteltu oikea vastaus, f(n), muuttuu kun rivin alkioiden määrään, eli n:ää kasvatetaan ydellä. Noh... rivin alkioiden (n:n) kasvattimen yhdellä on sama asia kuin teksi kaikille mahdollisille testattavilla riveille seuraavasti (eli triplataan testattavien rivien määrä):
rivi1 A
rivi1 B
rivi1 C
rivi2 A
rivi2 B
rivi2 C
....
A, B, C:n lisääminen oikeisiin riveihin tuplaa uusien oikeiden rivien määrän (sillä B ja C:n lisäys tuottavat kumpikin yhden uuden oikean rivin, kun taas A tekee rivistä parittoman eli ei tuota uutta oikeaa riviä), joten saadaan:
f(n) = 2*f(n-1) U
Jossa U on jäljellä jäännyt osa, eli se miten paljon A, B, C:n lisääminen edellisen kierroksen vääriin riveihin kasvattaa märää. Se tietysti nostaa oikeiksi riveiksi sieltä ne rivit, missä esiintyy pariton määrä A kirjaimia, sillä kun niihin lisätänä A ne muuttuvat parillisiksi. Tuo edellisen kierroksen parittomien rivien määrä, on sitten taas tietysti sama kuin sen kierroksen kaikkien rivien määrä: 3*3*3*3 ... *3 (n-1 kpl), eli 3^(n-1), vähennetynä parillisten rivien määrällä, eli f(n-1), että niiden rivien määrällä mitkä eivät ole parillisia eikä parittomia, eli joissa mukana vain B ja C kirjainta, eli 2*2*2*2*2*2 (n-1 kpl), eli (2^(n-1)). Joten:
f(n) = 2*f(n-1) (3^(n-1) - (f(n-1) 2^(n-1)))
f(n) = f(n-1) (3^(n-1)-2^(n-1))
Eli, vastaus:
Kun n < 1: f(n) = 0
muutoin: f(n) = f(n-1) (3^(n-1)-2^(n-1))
Testaus viellä, alkuun:
f(0) = 0
Nollan merkin pituisella rivillä ei voi muodostaa yhtään riviä, jossa parillinen määrä A kirjaimia. (OK)
f(1) = 0
Yhden merkin pituisella rivillä ei voi muodostaa yhtään riviä, jossa parillinen määrä A kirjaimia. (OK)
f(2) = 1
Kahden merkin pituisella rivillä voi muodostaa yden rivin, jossa parillinen määrä A kirjaimia. Nämä ovat: AA. (OK)
f(3) = 6
Kolmen merkin pituisella rivillä muodostaa kuusi riviä, jossa parillinen määrä A kirjaimia. Nämä ovat: BAA, ABA, AAB, CAA, ACA, AAC. (OK)
f(4) = 25
Neljän merkin pituisella rivillä muodostaa 25 riviä, jossa parillinen määrä A kirjaimia. Nämä ovat: BBAA, BCAA, CBAA, CCAA, BABA, BACA, CABA, CACA, BAAB, BAAC, CAAB, CAAC, ABBA, ABCA, ACBA, ACCA, ABAB, ABAC, ACAB, ACAC, AABB, AABC, AACB, AACC,AAAA.(OK)
Joten tuntuisi toimivan.... En tiedä saako tuota rekursiota tuosta kaavasta jotenkin pois. On kyllä melko vaikea tehtävä.... Näyttää olevan eri tulos kuin tuossa ensimmäisessä vastauksessa, mutta lähdin siitä olettamuksesta, että ne rivit missä ei ole yhtään A kirjainta ei lasketa parillisiksi, eli en luokittele "bbbb":ta kuuluvan f(4):n vastaus joukkoon....
Minäkin lähdin ensin siitä että kokonaan Aattomat jonot eivät ole niitä joissa on parillinen määrä A-kirjaimia. Nikin geometrinensumma ratkaisun jälkeen tarkistin asian wikistä ja siellä sanotaan "Vielä pitkään sen jälkeen, kun nolla oli hyväksytty luvuksi, ei sitä pidetty parillisena. Nykyään se luetaan aina osaksi parillisia kokonaislukuja, mutta määritelmästä riippuu, kuuluuko se vielä parillisiin luonnollisiin lukuihin vai ei."
Eli oletan että tehtävä on tarkoitettu tulkittavaksi niin kuin nikki geometrinensumma on sen tehnyt ja että hänen ratkaisunsa on oikea.
Hyväksyisin kummankin ajatteluntavan mukaiset ratkaisut (jos tulos oikea). En tiedä minkä laatuinen tuo koe on ollut, mutta arkielemässä määrän arvoa: 0 kpl, ei useimminten luokitella kumpaakaan luokkaan (parillinen tai pariton), joten tehtävän anto on siltä osin tulkinnan varainen. Itsellä sen verran pitkä aika kun olen koulunpenkillä istunut, ettei tuo toisenlainen luokittelu käynnyt edes mielessä.
Arkielämässäkin nolla on parillinen.
Tuo tapaus että ei hyväksytä sellaisia rivejä jossa ei ole yhtään A-kirjainta, voidaan ratkaista myös seuraavan päättelyn kautta. Oletetaan että meillä on a(n) kappaletta jonoja, joissa on parillinen määrä ja vähintään kaksi A-kirjainta. Nyt voidaan erottaa seuraavat n 1 kirjainta pitkät jonot:
* n kirjainta pitkät jonot, jotka täyttävät parillisuusvaatimuksen ja joiden perään on lisätty B tai C; näin syntyy 2*a(n) kpl parillisuusvaatimuksen täyttävää jonoa
* n kirjainta pitkät jonot, joissa ei ole yhtään A-kirjainta; näistä ei saa vaatimukset täyttäviä n 1 kirjaimen jonoja ja näitä on 2^n kpl
* loput n kirjainta pitkät jonot, joissa on pariton määrä a-kirjaimia; näistä saa vaatimukset täyttävät n 1 kirjaimen jonot lisäämällä perään A; tällaisia jonoja on 3^n-2^n-a(n) kpl.
Eli vaatimukset täyttäviä n 1 pitkiä jonoja on
a(n 1) = a(n) 3^n-2^n (sama kuin ohjelmoijasedän kaava)
Tuosta saadaam kehittämällä kahdeksi geometriseksi sarjaksi:
a(n) = 3^n/2 - 2^n 1/2
Monta tapaa ratkoa tehtävä. Näistä kolme on esitetty osoitteessa http://matematiikkakilpailut.fi/MAOL/2015/ala2015ratk.pdf . Mutta jotenkin en ole ihan varma siitä, etteikö Mrman11 osaisi tätä kun samanlaisen jekun teki aikoinaan Mrman116, http://keskustelu.suomi24.fi/t/10951599/pulma .
Pitää varmaan tutkia tarkemmin tuota parittomuuden ja parin käsitettä, sillä en kyllä tuotakaan oikein ymmärä. Testasin tuota vetämällä hatusta viisi erinlaista punnuskokoa: 1 kg, 2 kg, 3 kg, 4 kg ja 7 kg, jolloin päädyin että pelkästään näistä painoista muodostettussa sarjassa pitäisi olla vähintäin 14 punnusta:
Perus punnukset: 1 kg, 2 kg, 3 kg, 4 kg ja 7 kg
1. Kierros, yritän käydä läpi kaikki peruskomobinaatiot ja muodostetaan ne kahdella muulla sarjan painoilla:
1 2 = 3 = 1 2 (=> Tarvitaan uudet: 1 ja 2)
3 1 = 4 = 2 2 (=> Ei tarvita uusia, löytyy jo)
4 1 = 5 = 3 2 (=> Ei tarvita uusia, löytyy jo)
4 2 = 6 = 3 3 (=> Tarvitaan uudet: 3)
4 3 = 7 = 3 4 (=> Tarvitaan uudet: 4)
7 1 = 8 = 1 7 (=> Tarvitaan uudet: 7)
7 2 = 9 = 2 7 (=> Ei tarvita uusia, löytyy jo)
7 3 = 10 = 7 3 (=> Ei tarivita uusia, löytyy jo)
7 4 = 11 = 7 4 (=> Ei tarivita uusia, löytyy jo)
2. Uudet mukaan otettut punnukset ovat tuonneet mahdollisuuden ottaa mukaan tuplat, joten yritetään muodstaa nämä viellä:
1 1 = 2 => 1 1 (=> Tarvitaan uudet: 1 ja 1)
2 2 = 4 => 3 1 (=> Ei tarvita uusia, löytyy jo)
3 3 = 6 => 4 2 (=> Ei tarvita uusia, löytyy jo)
4 4 = 8 => 4 2 (=> Ei tarvita uusia, löytyy jo)
7 7 = 14 => 7 7 (=> Tarvitaan uudet: 7 ja 7)
Joten loppu tulema tuosta on 14 punnusa (> 13):
1 kg, 2 kg, 3 kg, 4 kg, 7 kg, 1 kg, 2 kg, 3 kg, 4 kg, 7 kg, 1 kg, 1 kg, 7 kg, 7 kg.
Jos parillinen määrä A-kirjaimia tarkoittaa sitä, että myös 0 A-kirjainta on parillinen määrä, on näitä parillisen A:n jonoja
jos n on parillinen: C(n,0) 2^n C(n,2) 2^(n-2) ... C(n,n-2) 2^2 C(n,n) 2^0
jos n on pariton: C(n,0) 2^n C(n,2) 2^(n-2) ... C(n,n-1) 2^1
jos sellaista jonoa ,jossa ei ole yhtään A-kirjainta, ei hyväksytä mukaan niin noista kaavoista jää tuo ensimmäinen termi C(n,0) 2^n pois.
Ohman
Huomasin vasta nyt tuon valmisratkaisun (MAOL)ja että siinä lausekkeita oli kehitetty edelleen ja saatu tuo (3^n 1) / 2. Kirjoittamistani kaavoista näkyy selvästi, miten tuo haluttu lukumäärä saadaan, mutta hyvähän se on yksinkertaistaa kaavaa edelleen kun se kerran onnistuu.
Ohman