Kombinatorik och tipsrader
Hej,
På stryktipset innebär en rad att man tippar resultatet i 13 fotbollsmatcher. Man väljer 1, X eller 2 (hemvinst, oavgjort eller bortavinst) för varje match.
Hur många rader måste man tippa för att säkert få minst 5 rätt av 13?
Min spontana påbörjade lösning är att räkna ut, på hur många sätt det går att välja 5 av 13, dvs. ?
Det ska inte spela någon roll om det blir 1, X eller 2 i 5 av matcherna. Hur många kombinationer behöver då täckas in?
Dr. G skrev:Det ska inte spela någon roll om det blir 1, X eller 2 i 5 av matcherna. Hur många kombinationer behöver då täckas in?
Bra fråga. Behöver nog lite mer än så.
Hur många rader skulle du tippa för att säkert få
1 rätt?
2 rätt?
Nu är jag sen in här, men det här problemet är betydligt svårare än man först tänker. Om problemet kommer från en gymnasiebok har antagligen läromedelsförfattaren själv inte löst problemet, annars skulle hen nog ha bedömt det som för svårt för gymnasiet.
Det är ju lätt att tänka att det "självklart" behövs 3^5=243 rader men faktum är att det går med 81 rader.
Den är från gymnasiet ja.. har änne ej riktigt fått grepp om den.. men aja
Smutsmunnen skrev:Nu är jag sen in här, men det här problemet är betydligt svårare än man först tänker. Om problemet kommer från en gymnasiebok har antagligen läromedelsförfattaren själv inte löst problemet, annars skulle hen nog ha bedömt det som för svårt för gymnasiet.
Det är ju lätt att tänka att det "självklart" behövs 3^5=243 rader men faktum är att det går med 81 rader.
Hur får du det till 81 rader? Jag får det till betydligt färre medelst lådprincipen: https://sv.m.wikipedia.org/wiki/Dirichlets_l%C3%A5dprincip
tomast80 skrev:Smutsmunnen skrev:Nu är jag sen in här, men det här problemet är betydligt svårare än man först tänker. Om problemet kommer från en gymnasiebok har antagligen läromedelsförfattaren själv inte löst problemet, annars skulle hen nog ha bedömt det som för svårt för gymnasiet.
Det är ju lätt att tänka att det "självklart" behövs 3^5=243 rader men faktum är att det går med 81 rader.
Hur får du det till 81 rader? Jag får det till betydligt färre medelst lådprincipen: https://sv.m.wikipedia.org/wiki/Dirichlets_l%C3%A5dprincip
Det här kan vara något jag missat, hur får du in lådprincipen i det här problemet?
Åh gud nu fattar jag, jag har tänkt så himla fel.
Jag överkomplicerade detta så enormt.
Det vore intressant att få se hur ni resonerat och vilket svar ni kommit fram till. Själv tycker jag att det borde vara betydligt fler rader för att vara säker på att få minst 5 rätt.
Det räcker med 3 rader.
T.ex en med bara ettor, en med bara kryss och en med bara tvåor.
Det finns alltid minst 5 av antingen 1, X eller 2.
Ture skrev:Det vore intressant att få se hur ni resonerat och vilket svar ni kommit fram till. Själv tycker jag att det borde vara betydligt fler rader för att vara säker på att få minst 5 rätt.
Du har 13 kulor som alla slumpvis är märkta med antingen "1", "X" eller "2".
Du har 3 lådor, en för varje kulmärkning.
Fördela nu de 13 kulorna bland lådorna enlogt märkning.
Den fördelning som ger minst antal kulor i varje låda är 4, 4, 5.
Oavsett kulornas märkning kommer alltså alltid åtninstone 1 låda innehålla åtminstone 5 kulor.
Därför kommer alltid åtminstone en av gissningarna "alla kulor är 1", "alla kulor är X", "alla kulor är 2" att ge minst 5 rätt.
Dr. G skrev:Det räcker med 3 rader.
T.ex en med bara ettor, en med bara kryss och en med bara tvåor.
Det finns alltid minst 5 av antingen 1, X eller 2.
Genialiskt! En riktig aha-upplevelse.
Smaragdalena skrev:Dr. G skrev:Det räcker med 3 rader.
T.ex en med bara ettor, en med bara kryss och en med bara tvåor.
Det finns alltid minst 5 av antingen 1, X eller 2.
Genialiskt! En riktig aha-upplevelse.
Det var tomast80 som kom med insikten.
Tidigare tänkte jag helt fel.
Jag antar Dr G tanke var att man kan tippa 3^5 rader och täcka in alla möjligheter på 5 matcher. Om man vill garantera fler rätt exempelvis 10 rätt så kan man ju då tippa 3^10 rader.
Jag övertänkte ordentligt och började tänka felrättande koder. Exempelvis om man har ett tips med 4 matcher så skulle Dr Gs metod innebära att man kan garantera 3 rätt med 3^3=27 rader men man kan faktiskt med 4 matcher garantera 3 rätt med bara nio rader, exempelvis följande:
Rad 1: 1111
Rad 2: X1XX
Rad 3: 1XX2
Rad 4: XX21
Rad 5: 2122
Rad 6: 122X
Rad 7: X212
Rad 8: 2X1X
Rad 9: 22X1
På samma sätt kan man med ett tips med 6 matcher garantera 5 rätt med bara 81 rader. Jag tänkte idiotiskt nog att detta skulle vara optimalt även på ett tips med 13 matcher.
Lådprincipen kom ju till räddningen här och jag bortsåg helt från det, men generellt sett är den här typen av problem mycket svåra, exempelvis kan man på ett stryktips med 11 matcher garantera 9 rätt med 3^6=729 rader men det är inte direkt lätt att visa.
Dr. G skrev:Det räcker med 3 rader.
T.ex en med bara ettor, en med bara kryss och en med bara tvåor.
Det finns alltid minst 5 av antingen 1, X eller 2.
Så självklart när man sett svaret!
Yngve skrev:Ture skrev:Det vore intressant att få se hur ni resonerat och vilket svar ni kommit fram till. Själv tycker jag att det borde vara betydligt fler rader för att vara säker på att få minst 5 rätt.
Du har 13 kulor som alla slumpvis är märkta med antingen "1", "X" eller "2".
Du har 3 lådor, en för varje kulmärkning.
Fördela nu de 13 kulorna bland lådorna enlogt märkning.
Den fördelning som ger minst antal kulor i varje låda är 4, 4, 5.
Oavsett kulornas märkning kommer alltså alltid åtninstone 1 låda innehålla åtminstone 5 kulor.
Därför kommer alltid åtminstone en av gissningarna "alla kulor är 1", "alla kulor är X", "alla kulor är 2" att ge minst 5 rätt.
Denna lösning var enligt mig mest logisk tack!:)
