Resultat: Senior

Lösning:

Rätt svar är 14.

Ett sätt att resonera är att stegvis uppdatera möjligheterna medan man "sveper diagonalt" genom tabellen

Utgångsläget är 0, så tabellen visar de ursprungliga antalen godisbitar

med antalet godisbitar man potentiellt kan få efter ett steg i fetstil. Nästa steg går uppåt eller till höger, och nollan uppdateras till 3 resp 0

Lägg märke till rutan med en godisbit till höger om trean eller ovanför nollan i fetstil. Dit kan man nå från endera, men största antalet bitar (4) får man om man kommer via trean.

Om man fortsätter på detta sätt inser man att det störst antalet bitar man kan ha i en viss ruta är antalet i rutan plus det största av "maximum till vänster"  resp. "maximum under". Uttryckt matematiskt 

V(i,j)=C(i,j)+max(V(i-1,j), V(i,j-1))

där C(i,j) är antalet godisbitar från början i rutan i,j och V(i,j) är maximala antalet man kunnat plocka till sig på väg dit. Eftersom man alltid vill titta under och till vänster kan man formellt lägga till en rad och en kolumn med nollor

V(i,0)=0, V(0,j)=0

Om man följer detta schema successivt får man slutresultatet

som visar att 14 är godisbitar är maximum i mål 

Detta är datavetenskap: Att hitta den bästa bland många möjliga lösningar är ett vanligt och svårt problem. I detta speciella godissamlingsproblem skulle man kunna prova alla möjliga väger, en s.k. rå kraft-metodik (brute force på engelska). Även med robotens begränsade rörelsemönster finns det tyvärr många vägar genom rutnätet, 70 stycken (ett antal man kan försöka härleda med hjälp av Pascals triangel).

Många av vägarna kan dock uppenbart väljas bort, och det är sedan möjligt att bland de kvarvarande hitta den bästa. Eftersom rutnätet är såpass litet går det att visa att alla andra vägar är sämre.

En effektivare lösning är att som vi gjorde uppdatera tabellen, med en metodik som kan kallas dynamisk programmering. När man har härlett en formel för det bästa värdet i en viss ruta utgående från värdet i cellen till vänster resp cellen under räcker det att utföra (i detta fall) 25 beräkningar för att gå från utgångsläget till det bästa slutresultatet.

Lösning:

Rätt svar är A=33, B=1, E=21, R=22, S=321; dvs 1_21_1_22_33_321.

Om vi börjar från början, om B kodas som 12 så måste E ha koden 1 vilket inte är möjligt då koden för B då innehåller koden för E. Vidare är det omöjligt för B att ha en kod längre än två tecken (121, 1211, 12112, osv) eftersom dessa siffror ska upprepa sig. Alltså är koden för B=1.

Bokstaven E följs av B och alltså måste koden vara antingen 2, 21 eller 211223332. Den kan inte vara 2 eftersom då skulle ordet börja på BEBB. Den kan inte vara 211223332 eftersom då skulle ordet bara bli BEB. Alltså är koden för E=21.

Nu vet vi att 1_21_1 är koden för BEB och vi behöver dela upp 2233321 i koder för RAS.

Beakta sista bokstaven S: dess kod kan inte vara 1 eller 21 eftersom dessa koder redan används för B och E. Möjliga koder är därmed 321, 3321, 33321, 233321 eller 2233321. S kan inte kodas som 2233321 eftersom då skulle ordet bli BEBS. Den kan inte vara 233321 eftersom då skulle endast ett tecken användas för att koda både R och A. Den kan inte heller vara 33321 eftersom då skulle 22 användas för att koda både R och A vilket skulle kräva att båda kodades som 2 vilket inte är möjligt. Om S skulle kodas som 3321, skulle bokstäverna RA kodas som 223. Dock kan inte koden för R vara bara 2 och koden för A kan inte bara vara 3 eftersom andra koder startar med dessa siffror. Alltså måste koden för S vara 321, och 2233 koda RA. Enligt tidigare argumentation måste koden för R vara 22 och koden för A måste vara 33. Därmed får vi svaret A=33, B=1, E=21, R=22, S=321; dvs 1_21_1_22_33_321.

Detta är datavetenskap

Prefixchiffret som beskrivs i uppgiften är ett exempel på en prefixkod, där koder skapas som har egenskapen att ingen av dem börjar med en annan kod. Den här egenskapen är användbar i informationskodning, eftersom det inte behövs någon separator (som mellanslag) mellan två koder. En vanlig uppgift är att hitta en prefixkod som ger så korta meddelanden som möjligt givet en specifik uppsättning texter.  Detta används bland annat för att komprimera information så att de tar mindre plats att lagra. En metod för att hitta optimala prefixkoder är att använda Huffmankodning som använder korta koder för vanliga symboler och långa koder för mer ovanliga. Dessa koder används på många ställen, bland annat för vissa saker inom JPEG och MP3.

• https://en.wikipedia.org/wiki/Prefix_code
• https://sv.wikipedia.org/wiki/Huffmankodning

Lösning:

Rätt svar är: Jag bytte ut alla 11or mot $ och sedan alla 1or mot 11or och slutligen alla $ mot 1or.

Om jag först byter ut alla 11or mot 1or så kan vi inte längre skilja på de som var 1or från början och de som var 11or. I slutändan skulle jag bara ha 11or.

Om jag byter ut alla 1or mot 11or och sedan alla 11or mot 1or så kommer jag få samma text som från början.

Om jag byter ut alla 1or mot $ och sedan alla $ mot 11or och slutligen alla 11or mot 1or så får jag en text med bara 1or.

Koppling till datavetenskap

Att byta ut alla förekomster av text som uppfyller ett mönster är en vanlig operation i alla texthantering. Ett kraftfullt språk för att byta ut text är reguljära uttryck (eng regular expressions). Där kan man beskriva möster för vilken text som ska bytas ut och vad den ska bytas ut mot. Om du jobbar med programmering eller systemadministration är det väldigt viktigt att lära sig använda reguljära uttryck då de kommer underlätta mycket i din vardag. https://sv.wikipedia.org/wiki/Reguljära_uttryck

Lösning:

Rätt svar är 

Hål A har plats för tre bollar, så boll 4 till 10 rullar förbi den i ordning. Hål B har plats för två bollar, så boll 6 till 10 rullar förbi den i ordning. Hål C har plats för en boll, så boll 7 till 10 rullar förbi den i ordning. Sedan dras sprinten i hål A ut och bollar matas ut i ordningen 3,2,1 och rullar till botten. Nu är bollarna längst ner i ordningen 7,8,9,10,3,2,1. Därefter dras sprinten i hål B ut och bollarna matas ut i ordningen 5,4. Nu är bollarna längst ner i ordningen 7,8,9,10,3,2,1,5,4. Slutligen dras sprinten i hål C ut och boll 6 rullar till botten vilket ger rätt svar.

Koppling till datavetenskap
Hålen fungerar som en stack som är en datastruktur, det vill säga det är ett sätt att organisera data. Den baseras på "sist in, först ut"-principen (LIFO - Last In First Out). Till exempel är den sista bollen som faller i ett hål den första bollen som stöts ut från hålet. Trots att det är en mycket enkel idé, är den användbar i många olika situationer. Du kan till exempel undersöka hur en stack kan användas för att kontrollera att parenteserna i ((1 + 2) * 3) är balanserade medan parenteserna i ((4 + 5) * (6-7) inte är det. Tanken är att alla öppningsparenteser sätts på en stack (den här funktionen kallas för push) och när dess matchande slutparentes hittas, avlägsnas öppningsparentesen från toppen av stacken (denna operation kallas pop). Så länge stacken inte är tom vid någon pop och stacken är tom när alla parenteser är slut så var de balanserade.

Lösning:

Det rätta svaret är torsdag.

Tom, Ted och Kim köper låten på tisdagen, Anna och Jane på onsdagen och Joe på torsdagen.

På tisdag:

På onsdag:

På torsdag har alla vännerna köpt låten.

Koppling till Datavetenskap

Uppgiften handlar om företeelsen att sprida inflytande genom ett socialt nätverk. Varje deltagare ändrar sig om dess grannar har en annan idé eller tankesätt. Här måste du simulera spridningen. Flera marknadsföringskampanjer utnyttjar olika sätt för spridning på sociala nätverk för att föreslå nya varor eller tjänster.

Lösning:

Det rätta svaret är (111(1(1011)11)).

Koppling till Datavetenskap

Quad tree-kompression lämpar sig bara för vissa typer av bilder.
https://en.wikipedia.org/wiki/Quadtree

Lösning:

Rätt svar är 14 hjärtan. 

Eftersom tre personer alla föredrar      , så kan maxantalet hjärtan inte bli mer än 4+4+3+3, men det uppfylls t.ex. med följande fördelning 

Anna	Bert	Cissi	David

Eftersom David har     som favorit, medan de andra sätter den sist , så måste han  få den för att två ska kunna få sin favorit. Alla de övriga har     som favorit, men eftersom Anna sätter     som tvåa, medan de övriga har den på tredje plats bör hon få den.  Nu kan Bert och Cissi diskutera (eller dra lott om) vem som tar vilken av     eller    , antalet hjärtan blir detsamma. 

Det är datavetenskap:

Optimering är en viktig del inom datavetenskp. I detta fall försöker vi maximera lyckan inom gruppen, definierat av totalantalet hjärtan. Optimeringsproblem dyker ständigt upp inom datavetenskapen.

I detta fall är det ett matchningsproblem. Dryckerna matchas till vännerna så att antalet hjärtan maximeras. Sådana problem är extremt viktiga i verkliga livet. Ett exempel är patienter som väntar på en transplantation och placeras på en lång väntelista. Tyvärr kan inte alla organ användas för en given person - organdonatorn måste t.ex. ha en kompatibel blodgrupp för att operationen ska ha en chans att lyckas. Sådana restriktioner gör det svårare att hitta en matchning som gör alla nöjda.

Lösning:

Svar: Alla bävrar kan vara i rum F efter 4 minuter.

Det finns två kortaste vägar till F, ABF och ACF, båda tar 2 minuter men har bara rum för en bäver i taget.

Det finns en rutt med högre kapacitet, ABCF, som tar 3 minuter men kan ta två bävrar samtidigt.

För att optimera tiden visar det sig att man måste underutnyttja AB-rutten. Den optimala lösningen skickar 3 bävrar genom AB den första minuten och tre under den andra. Eftersom bara tre tunnlar leder ut från B blir den en flaskhals där bävrar skulle fastna om det kom fyra från A.

Tabellen beskriver vad som händer minut för minut tills alla bävrar kommit till maten i F. Även om 4 minuter är minimumtiden finns det flera sätt att nå den. I denna variant behöver inga bävrar vänta i rum B.

Det är datavetenskap: 

I grafteori kan vi tänka oss nätverket av tunnlar som ett flödesnät. Det är en s. riktad graf där varje kant har en viss kapacitet (maximala antalet tunnlar eller bävrar mellan rummen) och varje kant får ett visst flöde. Flödet längs en kant kan inte överstiga kantens kapacitet. Målet är att optimera flödet av bävrar genom nätverket så att så många bävrar som möjligt anländer på kortast tid till maten. Ett sådant nätverk kan t.ex. användas för att beskriva trafiken i ett vägsystem. Det finns många algoritmer för sådana problem, en är Ford-Fulkerson algoritmen. Vårt problem är dock en specialversion av detta, eftersom bävrarna kan vänta i B eller C om de inte genast kan fortsätta. I det klassiska flödesnätverket kan inget bli stående, utan allt som kommer in måste ut genom andra kanaler. Det klassiska problemet föreskriver också riktningar för varje tunnel, medan bävrarna är fria att krypa i vilken riktning som helst.

Lösning:

Rätt svar är:

Byte av en del i taget hjälper till att identifiera den felaktiga delen. När systemet börjar fungera vet man att den del som ersatts sist var felaktig.

- Längden på slangen har ingen betydelse för att bevattningssystemet inte fungerar. Längden på program eller en komponent är ingen garanti för att den innehåller fler fel.

- Priset på en komponent spelar förstås heller ingen roll när man ska hitta felet.

- Att testa två komponenter samtidig resulterar inte i färre försök än att ersätta en del i taget. Om den trasiga delen är mot slutet av systemet, så kommer visserligen "testa två samtidigt" att kräva färre försök. Men om den felaktiga delen är i början (t.ex. strömförsörjning) behövs bara en enda provning om man byter en del i taget (vi kommer att observera att efter att ha ersatt strömförsörjningen fungerar systemet), men om man ersätter två delar åt gången skulle det krävas minst två försök att bestämma att strömförsörjningen är den felaktiga delen.

Detta är datavetenskap

Felsökning är en av de viktigaste uppgifterna i programmering eftersom komplexa system oundvikligen tenderar att få fel. Att hitta ett fel i ett program är svårt, men att hitta två fel är ännu svårare. Därför har utvecklare strategier att arbeta med för att få fungerande kod samt att köra tester efter varje viktig förändring. 

https://en.wikiquote.org/wiki/John_Gall, https://en.wikipedia.org/wiki/Systemantics

Lösning:

Rätt svar är

För att förstå vilka streck som krävs kan vi titta på par av siffror där endast ett streck skiljer dem åt:

Låt oss ta 0 och 8, de skiljer endast i ett streck vilket alltså måste vara med. Genom att titta bara på det strecket kan vi dela in alla tecken i två grupper, en grupp med de där strecket är med (2, 3, 4, 5, 6, 8, 9) och en grupp där det inte är med (0, 1, 7). Vi kan sedan se att 1 och 7 också endast skiljer sig i ett streck, vilket alltså måste vara med. Med de två valda streckena får vi nu fyra grupper av tecken (1), (0, 7), (4), (2, 3, 5, 6, 8, 9) och vi kan alltså unikt särskilja 1 och 4. Vi kan fortsätta och hitta siffror som endast skiljer sig i ett streck.

Efter att ha lagt till strecket som skiljer 3 och 9 så har vi (0), (1), (4), (7), (2, 3) och (5, 6, 8, 9).

Efter att ha lagt till strecket som skiljer 5 och 6 så har vi (0), (1), (2), (3), (4), (7), (5, 9) och (6, 8).

Efter att ha lagt till strecket som skiljer 6 och 8 så har vi (0), (1), (2), (3), (4), (5), (6), (7), (8) och (9).

Om vi använder alla ovanstående streck kan vi alltså unikt särskilja alla 10 siffrorna.

Koppling till datavetenskap

Mönsterigenkänningsalgoritmer försöker alltid ge ett rimligt svar för alla möjliga bilder utifrån mönsternas statistiska egenskaper Mönstermatching är en del inom maskininlärning som fokuserar på att hitta mönster och regelbundenheter i data. En approach är att hitta specifika mönster eller egenskaper som unikt identifierar objekt. Mönstermatchning är också väldigt vanligt inom bildbehandling vilket är ett aktivit och viktigt forskningsområde.

• https://sv.wikipedia.org/wiki/Bildbehandling
• https://sv.wikipedia.org/wiki/Maskinläsning

Lösning:

Det rätta svaret är RLLLRR. Det ska alltså se ut så här:

När araboten kommer in från startplatserna B och C måste vi få den att fortsätta in mot mitten i figuren, så sträcka 2 måste ha bokstaven L och sträcka 5 måste ha bokstaven R. Eftersom den sedan svänger av uppåt i figuren måste sträcka 3 ha bokstaven L för att undvika att den svänger in till A. Alltså kommer araboten att passera antingen sträcka 1 (om den startade från B eller C) eller sträcka 6 (om den startade från A), i båda fallen i riktning mot laddningsstationen. Det enda sättet att nå laddningsstationen är att komma snett nerifrån så de återstående sträckorna måste märkas så att araboten alltid kommer den vägen, nämligen genom R på sträcka 1, L på sträcka 4 och R på sträcka 6.

Detta är datavetenskap

När araboten följer en rutt genom grafen så innebär varje steg att läsa och förstå en instruktion: ”vilken väg ska tas i nästa korsning”, och detta val påverkar också vilken ny instruktion araboten får. Detta påminner om hur datorhårdvara fungerar på elektroniknivå.

Men uppgiften handlar också om att hantera flera olika vägproblem (A till , B till och C till ) i en enda datastruktur (en graf i det här fallet). Den väcker därför ett antal intressanta matematiska frågor om hur svårt det egentligen är att bestämma rätt bokstäver. Några av dessa frågor är olösta och studeras aktivt av forskare i datavetenskap och komplexitetsanalys. Besläktade frågor har tillämpningar inom beräkningsbiologi och beräkningsmedicin.

Lösning:

Svar: 

är den enda genomförbara banan. På de släta sektionerna kan du göra + - -, - + -, eller - - +, eftersom det bara gäller att totalt minska med 10 km/h för att vara nere till 0 vid mållinjen. 

Övriga banor är inte genomförbara:

 Även om du ökar på den släta (andra) sektionen kommer farten att ta slut innan mål.

Även om du bromsar på båda de släta sektionerna kommer din hastighet att vara för hög i mål.

På sista sektionen ökar farten, och eftersom din hastighet inte kan vara negativ när du når den är det omöjligt att din hastighet är 0 i mål. mål.

Det är Datavetenskp:

Parenteser är vanliga i formler. I algebraiska uttryck, som [n (n-1)] / 2 eller (a + b) (a-b) används parentes för att uttryckligen föreskriva operatorsordningen. Parenteser används alltid parvis, med en början(=vänsterparentes) och ett slut(=högerparentes). Uttryck är "välformade" endast om parenteserna är korrekt ordnade. En högerparentes måste matcha den närmast föregående vänsterparentesen, och för varje vänsterparentes måste det finnas en högerparentes.

På samma sätt måste många instruktioner (eller "språk" som datavetenskapare säger) som ska "förstås" av datorer, innehålla några typer av parenteser. Till exempel, i beskrivningsspråket HTML för webbsidor, omsluts ett stycke av öppnings- och stängningskoderna <p> och </ p>, och varje kod själv alltså i ett par parenteser < och >. Men varför är parentespar så populära i datorspråk? Anledningen är enkel: De är enkla att bearbeta!

Sektionerna i CykelKul-banorna kan också betraktas som parenteser: En nedfartssektion är en vänsterparentes och en uppförsbacke en högerparentes. En slät sektion är en tom plats där man valfritt kan sätta in en vänster- eller en högerparentes. En CykelKul-bana är genomförbar om denna insättning kan utföras så att resultatet är ett välformat parentesuttryck. Den möjliga banan ovan kan symboliskt skrivas (? (??), och den är genomförbar eftersom den kan omvandlas på flera sätt till ett välformat parentesuttryck: (())) eller () (()) eller () () (). I teoretisk datalogi kallas ett språk av välformade parentesuttryck ett "Dyck-språk".

Lösning:

Rätt svar är att det kortaste avståndet mellan dessa noder är 8 eller mer.

Om det kortaste avståndet skulle vara mindre än 8 bör det kortaste avståndet mellan S och nod 11 vara mindre än 11. Det kortaste avståndet kan vara större än 8, eftersom den kortaste vägen från S till nod 11 kan gå genom de yttre hörnen av nätverket.

Koppling till Datavetenskap

Att räkna ut avstånd mellan olika noder i en graf är ett vanligt problem till exempel när man ska hitta en väg mellan två platser i en karta.

Lösning:

Rätt svar är 4. En möjlig sekvens av operationer är

STÄVAN -> SÄVAN   (ta bort T)
SÄVAN -> BÄVAN   (byt S mot B)
BÄVAN -> BÄVARN   (sätt in R)
BÄVARN -> BÄVERN   (byt A mot E)

Detta är datavetenskap

Det här måttet på hur lika två textsträngar är kallas för Levenshtein-avstånd och har tillämpningar inom såväl datavetenskap som lingvistik och till och med genetik.

https://en.wikipedia.org/wiki/Levenshtein_distance#Applications

Lösning:

Svar: Följande serie med instruktioner upprepad tre gånger leder Mysto genom labyrinten:

F

H

F

V

F

V

F

F

H

F

F

H

F

Detta är datavetenskap

Mysto följer ett program för att komma till utgången. Ett program består av en serie instruktioner och ibland måste serien upprepas. För att göra det så enkelt som möjligt innehåller de flesta programspråk speciella instruktioner för "loopar". En serie kommandon kan på så sätt upprepas valfritt antal gånger, bestämt av programmeraren. Genom att använda loop-instruktioner slipper man skriva om programavsnitt flera gånger, vilket gör programmet effektivare och lättare att läsa och ändra.