Induktionsbevis för ett pussel

Här gäller det att tänka geometriskt! 1024 x 1024 är en kvadrat (sedan har vi tagit bort en bit, men i alla fall). Vi kan ta basfallet $n=1$‚ vilket ger oss rutnätet $2^1\times2^1$, där vi tagit bort en ruta, så att vi har tre rutor kvar. Det går bra att täcka denna figur med de L-formade bitar vi har (figuren har samma form som en L-bit). 

Som induktionsantagande säger vi att vi antar att påståendet är sant för $n=p$, dvs. att vi kan täcka ett rutnät av storlek $2^p\times2^p$ (minus en hörnruta) med våra L-brickor. 

Nu behöver vi på något vis visa att om induktionsantagandet stämmer, kan vi täcka även ett rutnät av storlek $2^{p+1}\times2^{p+1}$ med L-bitar. 

Rita upp hur antagandet ser ut geometriskt, och sedan hur induktionssteget skulle kunna utföras. Börja gärna med exempelvis $n=2$. :)

Smutstvätt skrev:

Här gäller det att tänka geometriskt! 1024 x 1024 är en kvadrat (sedan har vi tagit bort en bit, men i alla fall). Vi kan ta basfallet $n=1$‚ vilket ger oss rutnätet $2^1\times2^1$, där vi tagit bort en ruta, så att vi har tre rutor kvar. Det går bra att täcka denna figur med de L-formade bitar vi har (figuren har samma form som en L-bit). 

Som induktionsantagande säger vi att vi antar att påståendet är sant för $n=p$, dvs. att vi kan täcka ett rutnät av storlek $2^p\times2^p$ (minus en hörnruta) med våra L-brickor. 

Nu behöver vi på något vis visa att om induktionsantagandet stämmer, kan vi täcka även ett rutnät av storlek $2^{p+1}\times2^{p+1}$ med L-bitar. 

Rita upp hur antagandet ser ut geometriskt, och sedan hur induktionssteget skulle kunna utföras. Börja gärna med exempelvis $n=2$. :)

 

Ledtråd

Ta ett fyllt rutnät från induktionsantagandet. Hur kan vi placera dessa när vi gör vårt induktionssteg?

Tack för svar, men det står ingenstans att det är just hörnrutan som ska bort. Iaf, menar du såhär?:

P(1) är trivialt sant (basfall)

Anta P(k) : ”möjligt för 2^k * 2^k”, k >= 1. (IH)

Visa P(k+1) : ”möjligt för 2^(2k + 2)”

2^(2k + 2) = 4*2^2k

vi vet att det är möjligt för 4 (basfall)

vi vet att det är möjligt för 2^2k (IH)

därför kan vi också anta P(k+1)?

Vet inte riktigt

Iden är alltså att för en 2^(k+1)x2^(k+1) kvadrat så kan vi dela in den i fyra 2^k x 2^k delkvadrater. På var och en av de fyra mindre kvadraterna kan du utnyttja induktionsantagandet, det vill säga om du plockar bort en ruta från var och en av de fyra så går det att fylla med brickor av ditt slag.

Väljer man vilka kvadrater som du plockar bort i de mindre kvadraterna på ett klurigt sätt följer induktionssteget.