binomikertoimet nk , kun n, k∈N, k ≤n <10

Matematiikan olympiavalmennus Toukokuun 2011 helppo teht¨av¨asarja

1. Laske

1⁴+ 2010⁴+ 2011⁴ 1²+ 2010²+ 2011². 2. Kun n, k ∈ N, binomikertoimen ⁿ_k

voidaan m¨a¨aritell¨a olevan joukon {0, . . . , n− 1} (tai yht¨apit¨av¨asti mink¨a tahansa n-alkioisen joukon) k-alkioisten osajoukkojen lu- kum¨a¨ar¨a. Siis ⁿ₀

= 1, sill¨a Ø on ainoa 0-alkioinen joukko, ja ⁿ_n

= 1, sill¨a{0, . . . , n−1}

itse on ainoa joukon {0, . . . , n−1} n-alkioinen osajoukko.

a) Osoita my¨os, ett¨a tuttu rekursiokaava n+ 1

k+ 1

= n

k+ 1

+ n

k

, kun n, k∈N, on voimassa.

b) Laske Pascalin kolmiosta kymmenen ensimm¨aist¨a rivi¨a, ts. binomikertoimet ⁿ_k , kun n, k∈N, k ≤n <10.

c) Laske edellisen kohdan avulla – ilman taskulaskinta – osam¨a¨ar¨a 1 009 036 084 126 126 084 036 009 001

1 006 015 020 015 006 001.

3. Luvun n ∈ N kertoma n! taas on joukon {0, . . . , n−1} permutaatioiden eli bijek- tioidenf:{0, . . . , n−1} → {0, . . . , n−1} lukum¨a¨ar¨a. Olkoon n, k ∈N,k ≥n.

a) Perustele tuttu kaava

n k

= n!

k!(n−k)!. b) N¨ayt¨a, ett¨a

n k+ 1

= n−k k+ 1

n k

.

c) Mik¨a on suurin binomikertoimista n

r

, kun n on kiinnitetty ja r ∈N? 4. Todista, ett¨a kaikilla n, m∈N on voimassa

n

X

k=0

k m

=

n+ 1 m+ 1

.

5. Merkit¨a¨an jokaisella n∈N

sn =

n

X

k=0

n−k 2k

.

Osoita, ett¨a jono (sn)n∈N on itse asiassa ns. Fibonaccin lukujono, ts. s0 = s1 = 1 ja kaikillan∈N p¨atee sn+2 =sn+1+sn.

6. Todista binomilause: Kun a, b∈R ja n∈N, niin

(a+b)ⁿ=

n

X

k=0

n k

a^kb^n−k = n

0

a⁰bⁿ+ n

1

a¹bⁿ⁻¹+· · ·+ n

n

aⁿb⁰.

7. Todista, ett¨a

n

X

k=0, k parillinen

n k

=

n

X

k=0, k pariton

n k

,

kun n∈Z₊. Mik¨a on yht¨al¨on kombinatorinen tulkinta?

8. Todista, ett¨a 2^s

k

on parillinen, kun s, k∈Z₊ ja k <2^s.

9. Olkoon X ¨a¨arellinen n-alkioinen joukko, miss¨a n∈N, n≥2. Olkoon k∈N, k ≥n ja A sellainen perhe joukon X k-alkioisia osajoukkoja, ett¨a eri joukkojen A, B ∈ A leikkauksessa A∩B on korkeintaan k−2 alkioita. Todista, ett¨a

|A| ≤ 1 k

n k−1

.

10. Olkoon S ⊂ {1,2,3, . . . ,2008} 756 luvun joukko. Osoita, ett¨a on olemassa eri alkiota, b∈S, joille 8|a+b.

Ratkaisuja voi l¨ahett¨a¨a (mieluiten toukokuun kuluessa) osoitteeseen Kerkko Luosto

Koroistentie 4d A10 00280 Helsinki