"doominonupu" - 1 õppematerjal

Diskreetne matemaatika II - teine kodutöö

J = 3, % = 3 J = 4, & = 5 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.