Viikkotehtävä: melkein alkuluvut (Viikko 51)

lukuteoria
kombinatoriikka

#1

Viikkotehtävä

Vastausaikaa su 23.12.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Kaikenlaisten valmennustehtävien ja -tehtäväkokoelmien laatijalla on aina hankaluutena löytää optimaalinen vaikeustaso. Palstalla on ollut vaihtelevan vaikeita tehtäviä, mutta koska lähiaikoina valmennukseen lienee tulossa uusia oppilaita, tasoa toivottiin helpommaksi. Nämä saattavat siis olla kokeneemmille valmennettaville aika helppoja, mutta ehkä saamme houkuteltua enemmän vastauksia. Vaikeita tehtäviä riittää valmennuskirjeissä ja muussa materiaalissa.

Tehtävä

Kutsutaan kokonaislukua n>1 alkuluvun näköiseksi luvuksi, jos se on yhdistetty luku mutta ei ole jaollinen 2:lla, 3:lla tai 5:llä. Lukua 1000 pienempiä alkulukuja on 168. Montako alkuluvun näköistä lukua on, jotka ovat lukua 1000 pienempiä?


#2

#3

#4

Ratkaisu käyttää niin kutsuttua inkluusio-ekskluusio -periaatetta. Tästä voi lukea esimerkiksi täältä: https://brilliant.org/wiki/principle-of-inclusion-and-exclusion-pie/

Olkoon S = \{1, 2, \ldots , 1000\}. Tutkitaan joukon S niitä alkioita, jotka eivät ole jaollisia luvuilla 2, 3, 5. Olkoon näiden alkioiden joukko T. Olkoot S_2, S_3, S_5 ne S:n osajoukot, jotka ovat jaollisia luvuilla 2, 3, 5. Inkluusio-ekskluusion nojalla:

|S| - |T| = |S_2| + |S_3| + |S_5| - |S_2 \cap S_3| - |S_3 \cap S_5| - |S_2 \cap S_5| + |S_2 \cup S_3 \cup S_5|

Oikean puolen summa on 500 + 333 + 200 - 166 - 66 - 100 + 33 = 734. |S| = 1000, joten |T| = 1000 - 734 = 266.

Joukossa S on siis 466 alkioita, jotka eivät ole jaollisia luvuilla 2, 3, 5. Toisaalta kaikki S:n alkuluvut ovat joko 2, 3, 5, tai T:n alkioita. Siis T sisältää kaikki paitsi 3 alkulukua väliltä [1, 1000], eli se sisältää 165 alkulukua. Lisäksi T sisältää alkion 1, joka ei ole alkuluku eikä yhdistetty luku. Siis T sisältää 266 - 165 - 1 = 100 yhdistettyä lukua. Siis alkuluvun näköisiä lukuja on 100 kappaletta.


#5

Juuri näin. Paremmalla suomella tämän nimi on summan ja erotuksen periaate, mutta inkluusio–ekskluusiosta toki monet puhuvat.