Så er vi igang igen. Med Don til psykolog og Megan ved roret imens. Et glimrende afsnit.
Der var matematik og datalogi emner i massevis.
Jeg spottede
Induktiv Turing maskine, Voip (Voice Internet Protocol), logiske labyrinter, kageudskæringsalgoritmer (jo, det hedder det) samt diverse ord hørende til disse emner.
Kageudskæringsalgoritmer:
Det handler groft set om at dele noget – en kage eller noget andet – i et antal stykker, så alle bliver tilfredse. Et mere avanceret og kompliceret eksempel er opdeling af landområder efter en krig.
Et eksempel på en kageudskæringsalgoritme er “du deler og din søster vælger først” algoritmen, som forældre i hele verden nok kender. Ideen er, at hvis jeg deler, må jeg mene, begge stykker er lige gode. Og jeg er altså tilfreds, uanset hvilket stykke hun vælger. Omvendt er hun tilfreds, for hun får det stykke, hun selv mener ser bedst ud.
Man forestiller sig, en kage skal deles mellem personer, som har forskellige præferencer; Charlie viste en lagkage med vanille og chokolade og med glasur. Nogen sætter meget pris på glasur, andre mindre, nogen er vilde med vanille, andre med chokolade.
Vi forestiller os altså, at et stykke af kagen kan have forskellig værdi for forskellige personer. Og hele kagen kan være mere værd for en person end for en anden. Lad os sige, der er n personer, der skal dele kagen.
Man kan stille mange forskellige krav til en deling – hvad betyder det, at den er rimelig. Det kunne være
1) Proportionalt – hver person mener, at værdien af deres eget stykke er mindst 1/n af den samlede værdi. (OBS. Hvis nu jeg bedst kan lide vanilje og min søster chokolade og kagen består af halvt af hver, kan vi begge to få mere end halvdelen af det, vi mener er den samlede værdi. Ved at lade mig få den halvdel, der er vanilje og hun får den anden.)
2) Misundelsesfrit: Hver person mener, hun har fået det bedste af de stykker, kagen er delt i. (Ikke en skarp ulighed – det er nok, at der ikke er et andet, hun hellere vil have.)
3) Pareto optimalt:Vi har en opdeling, hvor enhver anden opdeling, hvor en deltager får mere, vil medføre, at en eller flere får mindre. Begrebet er en slags stabilitet overfor ændringer og optræder ofte i økonomi. Hvis jeg skal overbevise de andre om at lave det om, skal jeg overtale en deltager til at få mindre. (Det er det, der starter krige)
4) Ligeligt: Alles stykker har samme værdi. Så værdien af mit stykke for mig, er det samme som værdien af min søsters stykke for hende. Det kræver, at man kender alle deltagernes værdisætning af kagen.
Lad os begynde med to personer, som har et snit til at dele kagen. Vi vil ikke have en deling, hvor man tillader så mange stykker, at det ender med, at hver får en bunke krummer. Med “du deler, din søster vælger” algoritmen bliver delingen proportional og misundelsesfri men ikke nødvendigvis ligelig og pareto optimal.
Eksempel: Halvdelen af kagen er vanilje, halvdelen chokolade. Jeg er vild med chokolade, min søster med vanilje. jeg skærer og ved ikke, at min søster helst vil have vanilje. Så for en sikkerhedsskyld deler jeg, så begge stykker har halvt chokolade og halvt vanilje. Vi ville begge to have foretrukket delingen hvor jeg fik kun chokolade, og min søster kun vanilje – det er altså ikke pareto optimalt.
Lad os kigge nærmere på betingelserne ligelig og misundelsesfri. Pareto optimal er en lidt pudsig betingelse her, for hvis jeg får det hele, kan min søster ikke forbedre sin situation, uden jeg får mindre, end jeg havde; det er altså Pareto optimalt – og nok er jeg storesøster, men mon ikke FN eller forældre ville gribe ind.
Ligelig opdeling giver kun mening, hvis alle deltagere har samme samlede værdi af kagen, og man antager også, at alle sætter værdien af nok så små stykker højere end 0. Hellere chokolade end slet ingen kage. Lad os sige, den samlede værdi er 1.
En yderligere forsimpling er, at man kun må skære i en på forhånd valgt retning ( Tænk på en langstrakt skærekage, hvor man skærer på tværs – ikke noget med kagemænd, hvor man kan foretrække en af fødderne).
Vi kalder midtpunktet af kagen 1/2 og siger, man kan skære i punkter fra 0 til 1 (kagen er 1 lang). Fra 0 til 1/2 er der chokolade og fra 1/2 til 1 er der vanilje. (Vi antager, at stykker med areal 0, ikke har nogen værd, så det er ligemeget, hvad der er i 1/2.)
Hvis nu A er dobbelt så vild med chokolade som med vanilje, er hans værdisætning 4/3⋅x for et stykke af længde x med chokolade. Den er 2/3⋅ x for et stykke med vanilje. Vi antager, B har det omvendt.
Hvis A skal dele, vil hans strategi være, at det stykke, han ender med, har værdi mindst 1/2. (En minimax strategi – man satser ikke, men sørger for, at få mest muligt ud af det værste, der vil kunne ske.)
Så han deler i punktet p=3/8. Han har kun chokolade på stykket til venstre for p, så det har værdi
3/8 ⋅ 4/3 = 1/2
B vil vælge stykket til højre og få en værdi på 3/4, så det er ikke ligeligt, og A har snydt sig selv.
Havde A delt i midten, ville B stadig vælge stykket til højre, begge ville få værdi 2/3, og det ville være ligeligt og misundelsesfrit.
For n = 3 eller flere, kan man vise, at der findes situationer, hvor man ikke med n-1 snit kan lave en misundelsesfri og ligelig deling. Se f.eks. Better ways to cut a cake S. Brams, M.A. Jones og C. Klamler, Notices of the AMS, Vol 53 no. 11. Husk, hvis du går igang med den, at det handler om strategier og algoritmer: Hvordan ser det ud, hvis A ikke er ærlig om sin værdifunktion; er der en udenforstående involveret (FN eller andre) etc.
I How to cut a cake fairly, Walter Stromquist, American Mathematical Monthly, Vol 87, No.8, Oct. 1980, pp 640-644 (findes på Jstor for dem, der har adgang til det), bevises, at der eksisterer en misundelsesfri opdeling med n-1 snit for n deltagere. Men der er ikke en algoritme til at finde den. Det er et meget smukt argument (jo, det er det altså).
En opdeling i n+1 stykker betragtes som en stribe snit x1,x2,…,xn hvor 0 ≤ x1 ≤ x2 … ≤ xn ≤ 1. Det er de steder i intervallet mellem 0 og 1, hvor der skæres. Det tænker man så på som et punkt (x1,x2,…,xn) i et n-dimensionalt rum.
Las os begrænse os til at dele i tre stykker. Punkterne (x1,x2) vil ligge i en trekant i planen med hjørner (0,0), (0,1) og (1,1). Så hvert punkt svarer til en opdeling.
Hjørnepunkterne svarer til, at der to “stykker” uden noget, og et stykke, der er hele kagen. Kald de tre stykker, der kommer ud af opdelingen for nummer 1, 2 og 3 for stykket mellem 0 og x1, mellem x1 og x2 og mellem x2 og 1. Så er (0,0) der, hvor stykke 3 udgør hele kagen. (0,1) er, hvor stykke 2 er hele kagen og i (1,1) er det stykke 3, der er det hele.
På kanten mellem (0,0) og (0,1) er stykke nummer 1 “tomt”, og tilsvarende på de andre kanter.
I et punkt (x1,x2) vil spiller A måske foretrække stykke nummer 1, spiller B nummer 2 og spiller C måske også nummer 1. Der vil være en del af trekanten, hvori A vil foretrække 1, en anden del, hvor A foretrækker 2, og en tredie, hvor han foretrækker 3. (og nogen grænseområder, hvor han er ligeglad). Og tilsvarende for spillerne B og C. Nu skal man vise, at der findes et punkt, hvor spillerne foretrækker hver sit stykke. Og det kan man – med visse forudsætninger, men sådan er det jo i matematik. Ingrediensen i beviset er Brouwers fikspunktsætning, som har forbavsende mange anvendelser. Den siger:
En kontinuert afbildning fra en kugle til en kugle (tænk her på en klump modellervoks, som man kun må ælte og ikke flå) har et fikspunkt. (Et punkt er kommet tilbage, hvor det var)
Som illustration: Hvis man tager en blok papir, tager det øverste stykke af og krøller det sammen og lægger papirkuglen ovenpå blokken. Så vil der være et punkt, der ligger lige præcis lodret over der, hvor det var, før vi rev papiret af blokken.
Jeg vil ikke gengive, hvordan det bliver brugt i kageudskærings eksistensbeviset, men det står i artiklen.
Bemærk i øvrigt, problemet kan vendes om, så man skal dele noget, man ikke bryder sig om. Opvask og lignende. Det giver tilsvarende udskæringsalgoritmer “med modsat fortegn” i en vis forstand.
Logiske labyrinter.
Dem havde jeg ikke hørt om før, men det er ikke noget nyt for mig, at jeg lærer noget om matematik, når jeg ser Numb3rs og blogger… På engelsk hedder de “logic mazes”. I en logisk labyrint skifter reglerne, alt afhængig af, hvilken vej man går. Eksempel: Når jeg kommer ind i et rum i labyrinten afhænger de mulige udgange af, hvilken dør, jeg kom ind igennem. Som i masser af computerspil: Har man nået et højere niveau, kan man slå flere grimme trolde ihjel. Og dermed komme videre til andre dele af spillet.
Se for eksempel denne artikel – på engelsk. Opfinderen af logiske labyrinter er efter sigende Roger Abbot, som har hjemmesiden Logic Mazes. Der findes mange rigtig sjove spil designet som logiske labyrinter. Se f.eks.The orientation maze. Man kan “trevle en logisk labyrint op” ved at lave et diagram med alle de mulige tilstande og pile imellem de tilstande, man kan bevæge sig mellem. Så et rum kan være repræsenteret med tre forskellige tilstande, fordi man kan komme ind tre forskellige steder fra, og dermed har forskellige muligheder for at komme videre.
Spændende – måske finder jeg ud af mere.
Induktive Turingmaskiner vil jeg ikke kaste mig ud i. Men måske overtaler jeg en anden med forstand på de dele til at give jer noget om det. Det ser ud til at være omdiskuteret, hvad man mener med det – se bloggen “Computational complexity”.
Pingback: 4-08 Tabu. på numb3rs