Böckigt induktion problem

Well.

När jag läste detta tänkte jag omedelbart gå hem där sängen är förhoppningsvis lite varm.

Då hörde jag Yngves rost svagt i minnena, som visslade eteriskt: ''riiiiitaaaaaa figur''.

Så jag ritade figur med 5 böcker ordnade i fel ordning, och det går att flytta dem i 5 steg. 6 böcker går att flytta i 7 steg (i min figur, jag är medveten att några andra kan säkert omorganisera sina imaginär böcker ännu bättre).

Så vi skriver:

$n^{m o v e s} < \frac{1}{2} n (n - 1)$ ....

Well well... sängen var inte så dumt?

Att bevisa att påståendet är sant för n=1 är enkelt ;-)

Antag nu att du har n böcker som kan sorteras med högst $\frac{n (n + 1)}{2} = \frac{n^{2} + n}{2}$ steg. Du sätter sedan in en ny bok någonstans i hyllan. Antalet böcker är nu n+1 och vi vill bevisa att de kan sorteras med $\frac{(n + 1) (n + 2)}{2} = \frac{n^{2} + n + 2 n + 2}{2} = \frac{n^{2} + n}{2} + n + 1$ steg.

Observera alltså att det vi vill bevisa är att om n böcker kan sorteras med x steg så kan n+1 böcker sorteras med x + n+1 steg.

Tänk nu att du börjar sortera dina n+1 böcker. Du kan då dela upp dina steg i två typer.

Typ 1: Du byter plats på två böcker som till hör de n "gamla" böckerna. Detta steg är identiskt med det byte du skulle ha gjort om du bara skulle sortera de gamla böckerna.

Typ 2: Du byter plats på den nya boken och en av de gamla. Detta steg ändrar inte ordningen på de gamla böckerna, men flyttar den nya ett steg åt höger eller vänster.

Du vet från induktionsantagandet att det behövs högst $\frac{n (n + 1)}{2}$ steg av typ 1 för att sortera de gamla böckerna. Eftersom du har n böcker räcker n+1 steg av typ 2 för att flytta den nya boken hela vägen från längst till höger till längst till vänster (eller tvärtom), och alltså behöver du aldrig göra mer än n+1 steg av typ 2 för att få den nya på rätt ställe. Och därmed är beviset klart.

Oj, jag fick inga avisering för detta svar!

Återkommer för innehållet lite senare ;), stor tack för hjälpen!

SvanteR skrev :
Att bevisa att påståendet är sant för n=1 är enkelt ;-)
Antag nu att du har n böcker som kan sorteras med högst $\frac{n (n + 1)}{2} = \frac{n^{2} + n}{2}$ steg. Du sätter sedan in en ny bok någonstans i hyllan. Antalet böcker är nu n+1 och vi vill bevisa att de kan sorteras med $\frac{(n + 1) (n + 2)}{2} = \frac{n^{2} + n + 2 n + 2}{2} = \frac{n^{2} + n}{2} + n + 1$ steg.
Observera alltså att det vi vill bevisa är att om n böcker kan sorteras med x steg så kan n+1 böcker sorteras med x + n+1 steg.
Tänk nu att du börjar sortera dina n+1 böcker. Du kan då dela upp dina steg i två typer.
Typ 1: Du byter plats på två böcker som till hör de n "gamla" böckerna. Detta steg är identiskt med det byte du skulle ha gjort om du bara skulle sortera de gamla böckerna.
Typ 2: Du byter plats på den nya boken och en av de gamla. Detta steg ändrar inte ordningen på de gamla böckerna, men flyttar den nya ett steg åt höger eller vänster.
Du vet från induktionsantagandet att det behövs högst $\frac{n (n + 1)}{2}$ steg av typ 1 för att sortera de gamla böckerna. Eftersom du har n böcker räcker n+1 steg av typ 2 för att flytta den nya boken hela vägen från längst till höger till längst till vänster (eller tvärtom), och alltså behöver du aldrig göra mer än n+1 steg av typ 2 för att få den nya på rätt ställe. Och därmed är beviset klart.

Ok, jag förstår (?) vad du menar. Egentligen, det frågades inte att berätta hur man gör utan att använda formeln som angavs här och applicera den för n+1 böcker?

Svara

Visa senaste svar