Matematiikka
Tehtävä 1. Ison luvun jaollisuus S2023, B1
a) Määritä suurin luku k ∈ N, jolle 1023 ≡ -1 (mod 2^k). 3p.
b) Todista, että 2^12345678910 -1 on jaollinen luvulla 1023. 9p.
Hyvän vastauksen piirteet:
Annettu ehto on yhtäpitävä sen kanssa, että 1023 + 1 ≡ 0 (mod 2^k) TAI 1024 ≡ 0 (mod 2^k). 1 p.
riippumaton Koska 1024 = 2^10, niin kongruenssi toteutuu, kun k = 10. 1 p.
Perusteltu, miksi k = 10 on suurin mahdollinen luvun k arvo. (esimerkiksi 1024/2^k ei ole kokonaisluku, kun k ≥ 11.) 1 p.
Osatehtäväkohtaiset erillisohjeet
Siirrytty kongruenssista yhtälöön 1024 = 2^k ilman selitystä -1 p.
riippumaton 2^x – 1 on jaollinen luvulla 1023 täsmälleen silloin, kun 2^x ≡ 1 (mod 1023) TAI 2^x – 1 ≡ 0 (mod 1023).
Koska 2^10 ≡ 1 (mod 1023), niin 2^12345678910 = (2^10)^1234567891 ≡ 1^1234567891 = 1 (mod 1023).
(2 p./yhtäsuuruus tai kongruenssi)
Osatehtäväkohtaiset erillisohjeet
Ohjelmointiratkaisu mahdollinen.
Hyvän vastauksen kuva:
Tehtävä 2. Eukleideen algoritmi S2025, B1
Määritä Eukleideen algoritmilla lukujen 121110987654321 ja 123456789101112 suurin yhteinen tekijä. Voit käyttää ohjelmistoa, kunhan algoritmin välivaiheet näkyvät ratkaisussa.
Hyvän vastauksen piirteet:
Tehtävän voi ratkaista esimerkiksi käsin tai Pythonilla tai taulukkolaskennalla.
Laskettu oikeiden lukujen osamäärä TAI löydetty oikea kerroin (q1 = 1). (1 p.)
Löydetty oikea jakojäännös (r1 = 2345801446791). (2 p.)
Jatkettu vastaavasti. (1 p.)
Ensimmäiset kaksi jakojäännöstä oikein (B2–B3). (2 p.)
Näkyvissä rivi, josta voi päätellä vastauksen. (2 p.)
Johtopäätöksenä: Suurin yhteinen tekijä on siis 3. (2 p.)
Laskut dokumentoitu: kaikki laskut (a = q_nb+r_n) näkyvissä TAI kaikki (mod)/remain-rivit näkyvissä TAI
taulukkolaskennassa solujen kaavat näkyvissä. (2 p.)
Tähän ratkaisuun liittyvät erillisohjeet:
Pienet lasku- ja kopiointivirheet rivistä 5 alkaen (-1 p./virhe)
Jos virheet lyhentävät ratkaisua 5/10/15 riviä, niin lisäksi vähennys [-1/2/3 p.]
Pienet laskuvirheet eivät nollaa Johtopäätöksenä-rivin pisteitä.
Pelkkä taulukko/luvut ilman komentoja tai laskuja, ei dokumentoitu TAI ei kaikkia laskuja näkyvissä. (1+2+1+2+2+2+0)
(max 10 p.)
Osamääriä ei laskettu eli q = 1 jokaisessa askeleessa. (1+2+1+0+0+0+0+0). (max 4 p.)
Jaettu alkuperäiset luvut kolmella, laskut oikein, saatu suurin yhteinen tekijä kerrotaan kolmella. (max 12 p.)
TAI Koodiratkaisu
Esitetty koodi ohjelmointikielellä, missä:
Koodissa ensimmäiset luvut on alustettu algoritmiin oikein. (1 p.)
Koodi laskee seuraavat luvut oikein ja ne sijoitetaan muuttujiin oikein. (2 p.)
Koodissa on iteraatioehto oikein. (3 p.)
Koodi tulostaa lopussa oikean muuttujan arvon TAI algoritmin kaikki välivaiheet jossakin muodossa (esimerkiksi
jakojäännökset). (1 p.)
Ratkaisussa näkyy kokonainen ajettava koodi (esimerkiksi kuvakaappaus). (2 p.)
Ratkaisussa näkyy rivin 4 mukainen oikea tuloste. (1 p.)
Suurin yhteinen tekijä on siis (2 p.)
Tähän tehtävään liittyvät erillisohjeet
Pelkät laskut (selityksiä ei vaadita) TAI oikea Python-koodi ja tuloste. (max 12 p.)
Käytetty syt-komentoa laskimessa tai math.gcd Pythonissa. (+0 p.)
Ratkaisu pythonilla
Koodi:
a=123456789101112
b=121110987654321
while(b>0):
c=a-(a//b)*b
a=b
b=c
print(a)Välivaiheet tulostava ratkaisu pythonilla:
Koodi välivaihein:
a=123456789101112
b=121110987654321
while(b>0):
c=a%b
q=a//b
print(f'{a} = {q} * {b} + {c}')
a=b
b=c
print(f'suurin yhteinen tekijä on {a}')Ratkaisut näyttökuvina, ensin perinteinen ratkaisu, sitten Python-ratkaisut ja lisäksi taulukkolaskennalla saatu ratkaisu.
Tehtävä 3. Eukleideen algoritmi K2025, A
Määritä Eukleideen algoritmilla lukujen 5322 ja 342 suurin yhteinen tekijä.
Hyvän vastauksen piirteet
Laskettu 5322/342 ~ 15,6 TAI 5322 = 15*342 + r1 TAI idea 5322 = q1 *342 + r1 [1 p.]
5322 = 15 * 342 + 192 TAI 5322 ≡ 192 (mod 342). (2 p.)
Jatketaan samaa luvuille 342 ja 192. [1 p.]
342 = 1 * 192 + 150 TAI 342 ≡ 150 (mod 192). (1 p.)
192 = 1 * 150 + 42 TAI 192 ≡ 42 (mod 150). (1 p.)
150 = 3 * 42 + 24 TAI 150 ≡ 24 (mod 42). (1 p.)
42 = 1 * 24 + 18 TAI 42 ≡ 18 (mod 24). (1 p.)
24 = 1 * 18 + 6 TAI 24 ≡ 6 (mod 18). (1 p.)
18 = 3 * 6(+0) TAI 18 ≡ 0 (mod 6). (1 p.)
Vastattu suurimpana yhteisenä tekijänä omasta laskusta viimeinen nollasta eroava jakojäännös. (1 p.)
Suurin yhteinen tekijä on siis täsmälleen 6. (1 p.)
Tehtäväkohtaiset erillisohjeet
Alkupiste: Perusteltu oikea vastaus esimerkiksi SpeedCrunchin gcd komennolla tai pythonin math.gcd –
komennolla. / Löydetty kaikki alkutekijät tai kaikki positiiviset tekijät. (1 p.)
Näytetty vain, että 6 on yhteinen tekijä. (0 p.)
Laskuvirhettä kohden vähennetään 1 p. (ja lisäksi vastausriviltä), ja lisäksi tehdään vähennys, jos virheen
seurauksena algoritmissa on
1 rivi vähemmän (-0 p.)
2–3 riviä vähemmän (-1 p.)
4– riviä vähemmän (-3 p.)
Hyvän vastauksen kuva
Tehtävä 4. Collatzin lukujono
Collatzin jono on rekursiivinen lukujono, jonka jäsenet ovat positiivisia kokonaislukuja. Jonon seuraava jäsen a_n+1 saadaan edellisestä jäsenestä a_n seuraavalla tavalla:
– Jos a_n on parillinen, niin a_n+1 = 1/2 a_n
– Jos a_n on pariton ja suurempi kuin 1, niin a_n+1 = 3a_n + 1
– Jos a_n = 1 niin jono päättyy.
Esimerkiksi luvusta a1 = 20 alkava Collatzin jono on 20, 10, 5, 16, 8, 4, 2, 1. Saksalainen Lothar Collatz esitti vuonna 1937 konjektuurin (eli väittämän, jota ei kyennyt todistamaan), jonka mukaan mistä tahansa alkuarvosta alkava Collatzin jono on äärellinen. Tähän päivään mennessä kukaan ei ole kyennyt todistamaan sitä oikeaksi tai vääräksi.
a) Määritä Collatzin lukujono alkuarvolla a1 = 23. (3 p.)
b) Selvitä ohjelmiston avulla, mikä alkuarvo välillä 2-100 johtaa pisimpään Collatzin jonoon. Voit kirjoittaa koodisi esimerkiksi Pythonilla tai taulukkolaskentaohjelmalla. Anna vastauksena koodisi, koodin selitys ja taulukko, jossa näkyvät ainakin ne alkuarvot, jotka tuottavat viisi pisintä jonoa, sekä näiden jonojen pituudet. (9 p.)
Hyvän vastauksen piirteet
a) 23 → 3 * 23 + 1 = 70 → 70/2 = 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (3 p.)
b) Ohjelmakoodin voi toteuttaa esimerkiksi seuraavasti: Määritetään ensin vektori pituudet, joka laskee välivaiheiden määrää. Tämän jälkeen jokaisella 2 ≤ l ≤ 100 lasketaan siitä lähtevä jono, ja joka kierroksella kasvatetaan pituuden arvoa yhdellä. Tämä tehdään while-silmukassa. Silmukka pyörii, kunnes lukujonon arvoksi tulee 1.
Lopulta tulostetaan kaikki ne pituudet ja lukujen l arvot, joilla jonossa on yli 100 välivaihetta. (2 p.)
Koodi:
import math
pituudet = [0 for k in range(0, 101)]
for l in range(2, 101):
s = l
while s > 1:
if s % 2 == 0:
s = s / 2
else:
s = 3 * s + 1
pituudet[l] = pituudet[l]+1
for l in range(2, 101):
if pituudet[l] > 100:
print(l, pituudet[l])(3 p.)
Hyvän vastauksen kuvat
Tehtävä 5. Integraalialgoritmi
Tekstissä XX on esitetty pseudokoodilla kirjoitettu algoritmi.
1. Minkä tuloksen algorimi antaa, kun a = 0, b = 1 ja n = 5? (2 p.)
2. Tee taulukkolaskenta- tai ohjelmointitoteutus algoritmille, kun a = -1, a B=- b=2b = 2 ja n = 100. =1000. Minkä tuloksen se tässä tapauksessa antaa? (4 p.)
3. Mitä integraalia algoritmi approksimoi? Selitä muuttujien a, b, n, h, r, k ja f roolit algoritmissa. (6 p.)
Pseudokoodi:
integraali(a, b, n):
h = (b-a)/n
r = 0
toista arvoilla k = 1, 2, ..., n
f = (a+k*h)^2 + 1
r = r + f*h
palauta rTehtävä 6. Ohjelmakoodi ja tekijät
Papu yritti selvittää positiivisen kokonaisluvun alkutekijät. Tähän tarkoitukseen hän kirjoitti Python-koodin, joka on esitetty oheisessa koodikentässä. Koodissa #-merkkiä seuraava teksti on kommentti, joka ei vaikuta ohjelman toimintaan. Papu ajoi ohjelman muuttujan n eri alkuarvoilla. Hän huomasi, että toisinaan ohjelma toimi virheettömästi ja tulosti luvun n alkutekijät, toisinaan se tulosti muitakin lukuja.
Koodi:
n=x # korvaa x tutkittavalla luvulla
m=n
while n>1: #toista niin kauan kuin n>1
for a in range(2,m+1): # a käy läpi arvot 2, 3,..., m
if n%a==0: # jos n modulo a on nolla
print(a) # tulosta luvun a arvo
n=n/aa) ja b) -kohtien vastauksista täytyy ilmetä käytetty alkuarvo ja ohjelman tuloste.
a) Anna esimerkki luvun n alkuarvosta, jolle ohjelma tulostaa listan, joka sisältää vain luvun n alkutekijöitä. (3 p.)
b) Anna esimerkki luvun n alkuarvosta, jolle ohjelma tulostaa muitakin kuin luvun n alkutekijöitä. (3 p.)
c) Selitä, miksi ohjelma ei aina toimi niin kuin Papu oli tarkoittanut. (6 p.)
Huomaa, että tehtävässä annettua ohjelmakoodia voi ajaa koeympäristön ohjeiden Ohjelmointi-välilehdellä. Siellä on myös Python-kielen käskyjen selityksiä.
Hyvän vastauksen piirteet:
Ohjelma tuottaa oikean tulosteen esimerkiksi arvolla x = 35, sillä tällöin se tulostaa luvut 5 ja 7. (3 p.)
Ohjelma ei tuota oikea tulostetta esimerkiksi arvolla x = 16, sillä tällöin se tulostaa luvut 2, 4 ja 2. Luku 4 ei ole luvun 16 alkutekijä. (3 p.)
Pistejako: Yleinen selitys ongelmasta 3 pistettä, ja perustelu sille, miksi näin joskus käy (esim. esimerkin
avulla) 3 pistettä. (6 p.)
Esimerkki kuuden pisteen vastauksesta:
Ohjelman for-rakenteen sisällä tulostetaan kaikki ne luvut a1 < a2 < …, jotka toteuttavat ehdot n/a1 , n/a1a2 , … on kokonaisluku. Missään ei ole kontrollia sille, onko löydetty luku a_i alkuluku. Jos esimerkiksi n/a1 on jaollinen jollain luvulla, joka on suurempi kuin a1, mutta pienempi kuin seuraava alkuluku, jolla n/a1 on jaollinen, niin a2 ei ole alkuluku. Näin käy esimerkiksi luvun 16 kanssa, sillä tällöin ensin löydetään alkutekijä 2. Sitten tarkastellaan lukua 16/2 = 8, jolle 2:ta suurempi pienin tekijä on 4, eli ohjelma tulostaa sen seuraavaksi.