I LF til oppgave 10 står det «Sett inn hver ridder på første lovlige plass, etter tur», hvor første lovlige plass er at du setter den over en du har slått.

Dette vil først gi (1) sort, (2) rød, fordi sort slo rød. Men når grønn da skal settes inn vil da den første lovlige plassen være øverst fordi grønn slo sort, så listen blir (1) grønn, (2) sort (3) rød. Hvordan kan dette være en lovlig ranking? Rød har jo slått grønn?

Basert på Piazza-spørsmål fra 2015

Når du er forvirret (og egentlig også ellers) er det første du bør bruke tid på å finlese oppgaven, så du er helt sikker på at du har skjønt akkurat hva den beskriver og spør etter, og at du ikke bare har trukket forhastede konklusjoner om dette. Hvis du leser oppgaven igjen, så ser du at det er nettopp denne typen sykler som er problemet, og at den definisjonen på en akseptabel ranking som fremsettes gjelder for akkurat den listen du har satt opp. Dvs., det er en ranking av den typen oppgaven spør etter, dvs. en der hver ridder har slått den neste på lista.

Jeg sliter med akkurat den samme oppgaven. Jeg har lest oppgaven flere ganger, men greier enda ikke å se hvordan det blir en gyldig løsning når man har slike sykler. Noen som kan forklare dette?

Det viktige her er å skjønne hva som menes med «gyldig løsning». Siden du har sykler vil du uansett ende opp med en situasjon der en som er rangert dårlig vil ha vunnet over en som er rangert bra. Jeg gjetter det er det du stusser på? Men poenget er at det kan vi ikke unngå, så vi definerer oss en annen målsetting. Målsettingen er altså bare at alle i listen skal ha vunnet over den som står rett under dem. Vi stiller ingen andre krav. Så om lista vår er A, B, C, så krever vi bare at A skal ha slått B og at B skal ha slått C. Det gjør ingenting at C har slått A, for derom tier våre kriterier :D

Ja, det er det jeg sliter med å skjønne/akseptere. I oppgaven står det: «Du bestemmer deg for følgende løsning: Lag en rankingliste der ridderen i hver posisjon vant over ridderen i neste posisjon ned på lista. Etter å ha klødd deg litt i hodet kommer du frem til at dette alltid må være mulig.»

Nei, etter jeg har klødd meg litt i hodet kommer jeg fram til at dette fortsatt gir meg sykler og derfor ikke gir mening.

Ut fra måten oppgaven er skrevet på så forstår jeg det slik at denne «løsningen» som kommer faktisk skal ta hensyn til disse syklene. Hadde det derimot stått, som du skrev over her, at vi definerer oss en annen målsetting, så er jeg enig. Når oppgaven innleder med at man skal lage en rankingliste for ridderne, ja da antar jeg at man skal lage en rankingliste som i 100% av tilfellene fungerer, og gir en helhetlig og presis oversikt.

Den innledende teksten er at du tror du kan bruke en sorteringsalgoritme. Eller kanskje topologisk sortering. Men så oppdager du at det er sykler – dvs., ingen av disse er mulige lenger. Hva skal du gjøre? Du bestemmer deg for det som så er beskrevet (hver må ha vunnet over neste). Og du kommer frem til at det alltid er mulig.

Jeg kan forstå at du i forbifarten kunne tenke i den retningen du beskriver, men om du ser nærmere på problemet og teksten bør det være rimelig klart at det ikke er meningen å lage en topologisk sortering av en graf med sykler, noe som jo er umulig. Er det sykler, vil alltid noen lenger ned vinne over noen over.

Du skriver «Når oppgaven innleder med at man skal lage en rankingliste for ridderne, ja da antar jeg at man skal lage en rankingliste som i 100% av tilfellene fungerer, og gir en helhetlig og presis oversikt». Ja, det er da også meningen. Og det beskrives helt presist hvordan denne skal konstrueres. Hva du mener med «og gir en helhetlig og presis oversikt» er jeg ikke sikker på. Hvordan mener du at man kunne gi en mer helhetlig og presis oversikt i et tilfelle der man har sykler? Man kunne selvfølgelig telle antall seire, e.l., som ville gi en annen rankingliste. Om det ville være bedre eller dårligere vet jeg ikke. Men det er noe annet enn det du blir bedt om å gjøre. Og når du skal løse en oppgave, er det ofte taktisk å gjøre det du blir bedt om ;-)

Men mer generelt: Det er lurt å prøve å ikke anta så altfor mye, eller tillegge ting for mange egenskaper, men bare se akkurat hva oppgaven beskriver og ber om. Og det kan kreve litt jobb, av og til, å skrelle ting ned til essensen. I dette tilfellet, for eksempel, ser det ut til at du har en del oppfatninger om ordet «rankingliste». Når du ser at de oppfatningene ikke stemmer med sånn oppgaven bruker ordet (den bruker ordet bare om en liste der deltakerne rangeres), så bør du prøve å finne ut hvordan ordet brukes, heller enn å holde på «ekstra-bagasjen» som gjør oppgaven forvirrende. Lignende ting kan jo også skje dersom ting virker meningsløse på andre måter. Prøv da å lete etter hva setningene kan bety hvis du antar at de faktisk gir mening. (Men, for all del, det kan gjerne være uklarheter og feil i oppgavene, så det er jo verdt å spørre.)

Takk for et meget utfyllende svar! (Det gir mening nå.)