Fasit til "Ukens nøtt 10"
Det er ikke noe spesielt med 16 lag, resultatet gjelder like godt for turneringer med N lag. Vi skal vise dette ved induksjon på N (induksjon er strengt tatt ikke nødvendig - du kan gjennomføre det samme resonnementet uten formell bruk av induksjon).
Induksjonshypotesen er: I enhver turnering med N lag kan vi arrangere alle lagene i rekkefølge på en slik måte at hvert lag har slått det neste i rekken. Det er lett å se at resultatet gjelder for turneringer med bare to lag. Anta at det gjelder for alle turninger med k lag, vi må vise at det også gjelder for enhver turnering med k + 1 lag. Gitt en slik turnering, fjerner vi et ett lag (kall det A) og ser på alle oppgjørene mellom de andre lagene. Dette er en turnering mellom k lag, og etter induksjonshypotesen kan vi ordne dem etter hverandre på rekke slik at hvert lag i rekken har slått det neste laget. La B være det første laget i rekken som er blitt slått av A. Hvis det ikke finnes noe slikt lag, kan vi plassere A til slutt i rekken og få den rekkefølgen vi ønsker oss. Dersom B er det første laget i rekken, kan vi plassere A aller først i rekken og få den rekkefølgen vi ønsker oss. Hvis B står inne i rekken rett etter lag C, må lag C ha slått A (siden B er det første laget som er slått av A). Dermed kan vi plassere A mellom C og B uten at rekkefølgen ødelegges.
Oppdatert 1/11-99 av Tom Lindstrøm