"doominonupuga" - 1 õppematerjal

Diskreetne matemaatika II - teine kodutöö

J = 5, ' = 8 Panen tähele, et = # + $. Tõestan väite kehtivust induktsiooniga. Baas: väide kehtib n=3 korral. % = $ + # = 2 + 1 = 3 Induktsioonisamm: Eeldan, et väide peab paika k korral. Näitan, et väide kehtib ka k+1 korral. Ülemisele, vasakult esimesele ruudule saan panna doominonupu kas vertikaalselt või horisontaalselt. 1) Kui alustan vertikaalse doominonupuga, siis jääb veel katmata 2x(n-1) ruutu ja ülejäänud malelaua katmiseks on mul võimalust. 2) Kui alustan horisontaalse doominonupuga, siis jääb veel katmata 2x(n-2) ruutu ja ülejäänud malelaua katmiseks on mul # võimalust. 3) Kolmandat varianti pole. Seega kokku võimalusi: # = + #, mida tuligi näidata. Saadud rekurrentne seos erineb Fibonacci jadast üksnes algväärtuste poolest(# = 1 ja $ = 2), $ vastab % -le ja # $ -le. Järelikult W =