Tænkeboksen: Stoleleg – hvem har ret, eleven eller læreren?

Illustration: Ingeniøren

Forårssæsonens sidste opgave kommer fra Morten Grud Rasmussen ved Institut for Matematiske Fag ved AAU og lyder:

Opgave 51: En gymnasieklasse med 31 elever har idræt, og idrætslæreren beder eleverne stille sig ved en række markeringer med en meter imellem langs gymnastiksalens ene ­endevæg. Langs den modsatte endevæg står en række stole ved tilsvarende marke­ringer, så hver elev står ­direkte over for en stol.

Imidlertid er der på stolesæderne påklistret et navn, så hver elev har sin egen stol, men da de studerende står i tilfældig rækkefølge, står de ikke nødvendigvis overfor deres egen stol.

De skal nu efter nedtælling hurtigst muligt finde og besætte deres egen stol.

»Det er ikke fair!«, råber en elev: »Vi har jo alle forskellige afstande til vores egen stol!« Læreren indvender: »Det er ikke rigtigt; mindst to elever vil altid have samme afstand til deres stol.«

Det viser sig, at en af dem har ret, og den anden tager fejl.

Hvis det er eleven, der har ret, hvordan kan stole og elever så være arrangeret? Hvis det er læreren, hvorfor har han så det?
– – –

Vi bringer løsningen i næste uge, men fra søndag eftermiddag ligger opgaven også på adressen ing.dk/ fokus/taenkeboksen, hvor I kan diskutere jeres forslag til løsninger.

Illustration: Ingeniøren
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Det kan hurtigt ses, at forskellig afstand ikke kan opnås med tre stole, men gerne med fire (ABCD -> CBDA).

Stilles stolene overfor hinanden så de passer, er den samlede tværafstand nul. Ved enhver ombytning af to stole ændres den samlede afstand med et lige nummer (evt. nul).

Den samlede tværafstand hvis alle er forskellige er 0+1+2+...+30 == 30x31/2 = 465. Dette kan altså aldrig opnås ved at bytte om på stolene parvis fra udgangssituationen. Da udgangssituationen altid kan nås fra en vilkårlig opstilling ved at bytte om på to stole ad gangen, har læreren ret.

  • 2
  • 0

Nu da Kim har givet løsningen, kan man jo så i stedet spørge: For hvilke antal elever er det eleven, der har ret.

  • 0
  • 0

Sludder. Det behøver ikke at være et lige antal. 7, 11, 15, 19, ... er også kandidater

  • 0
  • 0

Man skal nok udnytte, at den samlede afstand regnet med fortegn forbliver nul. Dvs. tallene 0, 1, 2, ... n-1 skal kunne opdeles i to grupper som er lige store ([0, 1, 2] kan ikke, [0, 1, 2, 3] kan godt). Men det er ikke nødvendigvis en tilstrækkelig betingelse.

Det giver at 5, 9, 13, .... bliver kandidater, ikke 7, 11, 15, ... som jeg skrev ovenfor (jeg havde lige glemt at vi slutter med n-1 :-)). 5 elever er faktisk er løsning.

Endelig, blandt de lige tal er det kun dem delelig med 4 der er kandidater.

  • 2
  • 0

Jeg har "snydt" lidt og lavet en pc-test af mulige løsninger, hvor alle har forskellig afstand for antallet af elever op til 12. Der ser ud, som Kim skriver, at være løsninger for 4,5,8,9,12..

Nogle eksempler på løsninger med forskellige vejlængder for alle elever 4: (2,4,3,1) 5: (3,5,2,4,1) 8: (4,8,7,5,3,6,2,1) 9: (4,9,8,5,7,6,3,2,1) 12: (5,12,11,10,7,9,6,8,4,3,2,1)

  • 0
  • 0

Det kan godt være 2 elever har samme afstand, men hvad så med alle de andre? Det er en ulige konkurrence uanset lærerens påstand.

  • 1
  • 3

Som nævnt tidligere ændres summen af afstandene med et multiplum af 2 når to stole byttes. Når det går op er summen af afstandene = (0+1+2+..+n-1) = n(n-1)/2 og dette tal skal altså være lige.

Dvs. at enten n eller n-1 skal være delelig med 4.

  • 0
  • 0

Vi har nu set, at der kun kan være en løsning når elevantallet er deleligt med 4 eller 1 større end et tal deleligt med 4. Men det betyder jo ikke automatisk, at alle tilfældene er løsninger, atså at flytningerne kan udføres i praksis. Jeg tænkte på, om man kunne finde et generelt flytteskema. Det skulle jo begynde med at den længste flytning gik den ene vej og den næstlængste den anden vej, men hvad så? Jeg har ikke selv svaret, men det er måske et problem med lidt mere kød på. Og så får vi set om alle tilfældene er mulige.

  • 0
  • 0

Vi har nu set, at der kun kan være en løsning når elevantallet er deleligt med 4 eller 1 større end et tal deleligt med 4. Men det betyder jo ikke automatisk, at alle tilfældene er løsninger, atså at flytningerne kan udføres i praksis. Jeg tænkte på, om man kunne finde et generelt flytteskema. Det skulle jo begynde med at den længste flytning gik den ene vej og den næstlængste den anden vej, men hvad så? Jeg har ikke selv svaret, men det er måske et problem med lidt mere kød på. Og så får vi set om alle tilfældene er mulige.

  • 0
  • 0

Det er en lidt mærkelig formulering, for eleven har ret i, at opgaven ikke er fair, og det bliver den heller ikke, bare fordi mindst to skal gå lige langt Men læreren har ret , at der er mindst 2, som går lige langt med det valgte tal på 31. Når ingen ender uden stol, og ingen stol står tom betyder det jo, at hvis nogle går til højre, må andre gå til venstre for at alle kan blive "i systemet". Og hvis man f.eks. sætter + foran bevægelser til højre og - foran bevægelser til venstre, skal summen af disse blive nul. Som Kim Bygum tidligere har nævnt, bliver summen af de mulige positionsskift, når disse alle er forskellige, 465. Det er ikke deleligt med 2; derfor har læreren ret. Hvis der er n elever vil antallet af mulige positionsskift være n-1(muligheden: at gå lige tværs over tæller med 0). Man kan altid finde summen af mellemrummene som summen af en differensrække med n-1 led(ved n elever). Så man kan hurtigt se, om mindst 2 nødvendigvis må gå lige langt eller ej.

  • 0
  • 0

Jeg faldt lige over en tænkeboksopgave og har ikke selv et ing.dk login, så nu får du lige denne mail :-)

I har generaliseret stoleopgaven lidt, så den blev interessant.

Generelt er der mulige løsninger for n, hvis n giver rest 0 eller 1 med division med 4. Som I også er inde på, så er der sammenhæng til opsplitning af tallene fra 0 til n-1 i to klasser med samme sum.

For n lig 4, får vi denne opsplitning (man kan også skifte fortegn på begge sider, så om man tæller det som 1 eller 2 muligheder, tjah?) +3-2-1+0 = 0 og der er også permutationer, der passer med det mønster.

For n lig 8, er der 4 (eller 8, hvis vi synes det er sjovt at skifte fortegnene) +7-6-5+4-3+2+1+0 = 0 +7+6-5-4-3-2+1+0 = 0 +7-6+5-4-3+2-1+0 = 0 +7-6-5+4+3-2-1+0 = 0

Det sjove er imidlertid at der kun er permutationer svarende til de her sæt af afstande:

-6 -4 -3 -1 0 2 5 7 -6 -5 -2 -1 0 3 4 7 -6 -5 -3 0 1 2 4 7 -7 -4 -2 -1 0 3 5 6 -7 -4 -3 0 1 2 5 6 -7 -5 -2 0 1 3 4 6

(De hænger sammen to og to, for man kan klassificere efter om (2, 5, 7), (3, 4, 7) eller (1, 2, 4, 7) har samme fortegn.

Dvs der er et eksempel på en klasseopdeling (0,1,6,7)(2,3,4,5) hvor der ikke findes en permutation af stole, der passer til. Det er lidt irriterende, for jeg kan godt finde et eksempel på opsplitning af n, som kan generalisere: Bare gentag +--+ mønsteret af fortegn.

3 2 1 0 bliver til +3-2-1+0 = 0 7 6 5 4 3 2 1 0 bliver til +7-6+5-4 +3-2-1+0 osv men jeg mangler lige et bevis for at jeg altid kan finde en stolepermutation, der passer til den opsplitning.

Antallet af den her slags summer +7-6+5-4 +3-2-1+0, der giver 0, er forresten en kendt række: https://oeis.org/A058377

Jeg håber ovenstående får dig til at pusle lidt videre. Det har med sikkerhed ikke værkshøjde, så bare brug det uden kreditering, hvis det giver mening :-)

mvh Birger Nielsen (bnielsen@au.dk)

  • 1
  • 0

Jeg har ikke selv svaret, men det er måske et problem med lidt mere kød på. Og så får vi set om alle tilfældene er mulige.

Ja, spørgsmålet er om betingelsen også er tilstrækkelig.

Der findes en sætning eller formodning indenfor grafteori, som måske kan bringes i spil. Søg f.eks. "Graceful unicyclic graphs" af Truszczynski. Evt. "On certain valuations of the vertices of a graph" af Rosa.

Men det ville være fint med et konstruktivt bevis. F.eks. baseret på induktion.

  • 0
  • 0

Normalt synes jeg, at det er for letkøbt at kaste computerkraft efter tænkeboks-opgaver. Men lige denne her gjorde mig nysgerrig efter antallet af løsninger, og det ville jeg aldrig kunne finde ud af at løse analytisk. Jeg blev noget overrasket over resultatet.

Min forhåndsantagelse var, at der med et givent antal elever ville være ret få løsninger. Begrundelsen var, at hvis man starter med at vælge den længste rute, så den næstlængste osv. vil man opdage, at de ruter, man allerede har valgt, ligger ret godt i vejen for de næste ruter, der skal vælges.

Resultatet er noget anderledes, end jeg forventede:

  • Antal elever: 4 - Løsninger: 4
  • Antal elever: 5 - Løsninger: 4
  • Antal elever: 8 - Løsninger: 32
  • Antal elever: 9 - Løsninger: 96
  • Antal elever: 12 - Løsninger: 992
  • Antal elever: 13 - Løsninger: 2512
  • Antal elever: 16 - Løsninger: 50512
  • Antal elever: 17 - Løsninger: 144144
  • Antal elever: 20 - Løsninger: 3717888

...og maskinen står stadig og tæller løsninger for 21 elever. Det har stået på meget længe nu.

  • 1
  • 0

De fleste, der allerede forstår denne slags algoritmer, vil sikkert korse sig over min uvidenhed på området. Og de fleste andre vil sikkert være ligeglade med min metode. Men jeg blev så fascineret, at jeg var nødt til at dele det med nogen. Jeg håber, at der ud over de to nævnte grupper findes et mindretal, der kan dele min fascination.

Forhistorie:

Jeg har med års mellemrum forsøgt at løse en opgave af denne type med computerkraft. "Denne type" skal forstås som opgaver, hvor man er nødt til at træffe en række valg, og mulighederne for hvert valg afhænger af de foregående valg, man har truffet.

Min metode har altid været at starte fra en ende af. Finde mulighederne for valg nr. 1. Vælge den første af disse muligheder. Finde mulighederne for valg. nr. 2. Vælge den første af disse muligheder. På et tidspunkt kan man så ikke komme længere, enten fordi man har ramt en løsning, eller fordi man har ramt ind i en blindgyde. Så bakker man tilbage til det foregående valg og tjekker, om dette valg stadig har uafprøvede valgmuligheder på listen. Hvis ja, fortsætter man igen fremad med den første uafprøvede mulighed. Hvis nej, bakker man yderligere et step og tjekker igen.

Nu er jeg ikke så stærk i standardalgoritmer. Jeg bygger bare selv mine egne. Det fører ovenstående ofte til en meget omstændelig og uoverskuelig programmering, når ovenstående metode skal føres ud i livet.

Træer

Denne gang startede jeg med at læse lidt op på stoffet og fandt ud af, at det her tilsyneladende er det, man kalder et træ i programmeringsjargon. Og det findes der standardløsninger på.

Den objekt-orienterede standardløsning er fascinerende simpel, elegant og eksplosiv. I hvert fald i Python. Det eksplosive vender jeg tilbage til.

Man laver en klasse, hvor hver instans af klassen repræsenterer nøjagtigt 1 delvalg, man har foretaget undervejs. Klassen indeholder følgende:

  • en status på de foregående valg, der ledte op til det sted, hvor vi er nu.
  • en metode til at beregne mulighederne for det næste valg baseret på de forudgående valg.
  • en metode til at generere en ny instans af klassen for hver af disse valgmuligheder og føje instanserne til en liste over børn.
  • en generator. Den vender jeg tilbage til. Den er ikke nødvendig for at generere løsningerne.

Eksplosionen

Hvis man allerede i init-metoden for klassen kalder den metode, der genererer listen med klasseinstanser af det næste valg, så står man med noget, der for mig ligner programmeringsversionen af en nuklear kædereaktion:

Man skaber en instans af klassen, der indeholder startbetingelserne for valgene. Og så eksploderer løsningen, uden at man skal gøre mere.

Allerede når instansen bliver initieret, finder den løsningsmulighederne for næste valg og skaber en ny instans for hver af disse. Og hver af disse instanser finder løsningsmulighederne for næste valg og skaber en ny instans for hver. Og så videre.

Tilbage står så problemet med at få overblik over det virvar af klasser med børn, børnebørn, oldebørn osv., som blev skabt i eksplosionen. (Det må vel være en befolkningseksplosion...)

Til det skal vi bruge generatoren.

Generatoren

Med en generatormetode kan man gøre en klasse i Python itererbar. Det vil egentlig bare sige, at man igen og igen kan bede klassen om næste element. I vores tilfælde vil hvert element være en af de instanser af klassen, som blev skabt ovenfor.

Fidusen er, at første gang generatormetoden bliver kaldt, skal den returnere klassen selv. Næste gang den bliver kaldt, skal den kalde det første barns generatormetode og returnere resultatet af dette kald. Og det bliver den ved med, så længe dette barn returnerer resultater. Derefter går den videre til næste barn på listen.

Det lyder bøvlet, men det kræver kun denne lille smule kode inde i klassen:

def __iter__(self):  
    yield self  
    for child in self.children:  
        for item in child:  
            yield item

Og dermed kan man arbejde sig gennem samtlige delvalg, ved at man uden for klassen kører en simpel for-løkke på allerførste instans af klassen (som jeg har givet navnet root):

for path in root:  
    print(path.level, path.startnode, path.endnode )

Overbefolkning

Ovenstående gik meget godt, indtil jeg nåede op omkring 17 elever. Så crashede programmet, fordi der ikke var mere hukommelse tilbage på computeren.

Problemet var naturligvis, at jeg forsøgte at have hele løsningsrummet i hukommelsen på en gang, inklusive alle de delvalg, der ikke havde ført til et resultat. Der har sandsynligvis været tale om millioner af instanser af klassen.

Og så slog det mig: Hvad nu, hvis jeg skaber hvert barn inde i generatormetoden, kalder barnets generatormetode, indtil den ikke returnerer flere resultater, og derefter fjerner barnet? Så har jeg altid kun en lige linie af børn, børnebørn, oldebørn osv. i spil, hvilket må reducere antallet af klasseinstanser, så det svarer til antallet af elever + 1.

Dette virkede, og gjorde koden endnu mere kompakt.

Den endelige Python-kode

from copy import deepcopy

class branch():

def __init__(self):  

    self.parent = None  
    self.children = []  
    self.startnode = None  
    self.endnode = None  

def set_as_root(self, nodecount):  
    self.freenodes_begin = list(range(nodecount))  
    self.freenodes_end = list(range(nodecount))  
    self.branches_remaining = nodecount  

def createchild(self, startnode = None, endnode = None,):  
    b = branch()  
    b.parent = self  
    b.startnode = startnode  
    b.endnode = endnode  
    b.freenodes_begin = deepcopy(self.freenodes_begin)  
    b.freenodes_end = deepcopy(self.freenodes_end)  
    b.freenodes_begin.remove(startnode)  
    b.freenodes_end.remove(endnode)  
    b.branches_remaining = self.branches_remaining - 1  
    return b

def __iter__(self):  
    yield self  
    absdist = self.branches_remaining - 1  
    for endnode in self.freenodes_end:  
        for dist in set([-absdist,absdist]):  
            startnode = endnode + dist   
            if startnode in self.freenodes_begin:  
                child = self.createchild(startnode, endnode)  
                for item in child:  
                    yield item  
                child = None  

Test af klassen gentagne gange med 2-31 elever i stolelegen

for nodecount in range(2, 32):

results = []  
root = branch()  
root.set_as_root(nodecount=nodecount)  

for path in root:  
    if path.branches_remaining == 0:  
        results.append(path)  
print('Nodecount: {:3}    -    Results: {:8}'.format(nodecount, len(results)) )
  • 1
  • 0
Bidrag med din viden – log ind og deltag i debatten