| Svensk Bridge - Spader :: Forum :: Brickläggning | |||
|
|||
 Brickläggning, duplicering och spelGå till sidan << >> |
| Författare | Post |
| Per Hallberg [12555] |
| ||
 inlägg: 56 | Man kan väldigt enkelt visa att man måste blanda en vanlig kortlek minst fem gånger innan den kan tänkas vara välblandad: Låt oss studera "stigande följder". Tag en permutation, t ex 3 7 1 8 6 2 5 4. Leta upp 1 och sök åt höger efter 2, sen 3 etc. Om nästa siffra inte finns till höger om där du är så är det stopp och den stigande följden är slut. Fortsätt sen med nästa följd från den siffra du sökte efter. I exemplet har vi följande stigande följder: 1-2, 3-4, 5, 6, 7-8. Totalt fem stycket stigande följder. Den ursprungliga sorterade permutationen har 1 stigande följd. En helt perfekt blandad lek har i genomsnitt 26 stigande följder. Detta eftersom förväntad längd på en stigande följd är 2 om blandingen är perfekt. Övning: Varför? Nu till kärnan. Vid en riffle shuffle kan antalet stigande följder som mest fördubblas. Tänk igenom varför. Så efter fyra blandningar har vi som mest 1*2*2*2*2 = 16 stigande följder i leken, och den kan därmed omöjligen vara idealt blandad, då en sådan i snitt har 26 stycken. | ||
| Tillbaka till toppen |
| Håkan Persson [12948] |
| ||
 inlägg: 2 | Det är bra Per. Kämpa på! | ||
| Tillbaka till toppen |
| Per Hallberg [12555] |
| ||
inlägg: 56 | Per Hallberg[12555 skrev ... ] En helt perfekt blandad lek har i genomsnitt 26 stigande följder. Detta eftersom förväntad längd på en stigande följd är 2 om blandingen är perfekt. Övning: Varför? Usch! Jag borde avstå från inlägg efter midnatt. Det citerade är nonsens. Men beviset är enkelt, jag var bara för trött för att inse/minnas hur. Så här ska det vara: För en kortlek på n kort och någon permutation är antalet stigande följder plus antalet fallande följder alltid lika med n+1. I vårt exempel 3 7 1 8 6 2 5 4. är de fallande följderna 8, 7-6-5-4, 3-2, 1 dvs 4 stycken. Och våra förra 5 plus dessa 4 blir mycket riktigt 9 = 8+1. Beviset för att det alltid stämmer kan göras med s k induktion över n. För en vanligt kortlek är alltså summan av antalet stigande och fallande följder 53. Och för en idealt blandad lek följer av symmetriskäl att antalet stigande följder i snitt måste vara 53/2 = 26.5. Sen fortgår beviset som ovan. Sensmoral: Var skeptisk till bevis där centrala moment lämnas åt läsaren som övning! | ||
| Tillbaka till toppen |
| Kajsa Fröjd [30124] |
| ||
 inlägg: 112 | Per, jag skulle vilja att dina inlägg skulle nå fler bridgespelare än det som jag tror orkar ta sig igenom denna tråden (under en rubrik som inte är så beskrivande för dina inlägg)! Kanske ta in det på nytt under en annan rubrik? Eller ännu hellre, som en stadigvarande länk under tex Information? God fortsättning! | ||
| Tillbaka till toppen |
| Daniel Auby [9601] |
| ||
inlägg: 669 | Per Hallberg[12555 skrev ... ] Beviset för att det alltid stämmer kan göras med s k induktion över n. För dem som inte är så slängda i kunskapsteori kan jag meddela att med det fina ordet "induktion" menar man helt enkelt att man utifrån enskilda iakttagelser drar slutsatser om hur något förhåller sig i allmänhet (dvs slutledning baserad på erfarenhet). Ett enkelt exempel: du sitter en septemberdag under ett äppelträd och ser hur ett äpple faller ner från en gren. Strax därefter faller ytterligare ett ner. Några dagar senare observerar du att alla äpplena fallit ner från trädet. Du utför då den snillrika och induktiva slutsatsen att äpplen alltid faller från träd. Det mesta av all kunskap ernås på denna väg. Det omvända, de s.k. deduktiva slutsatserna - dvs där man utifrån det allmänna drar slutsatser om det enskilda - baseras oftast på axiom som i sig är induktivt framtagna. F.ö. kan man ju lätt se att man får vara lite försiktig när man drar sådana slutsatser. Kanske är det bara äpplen av denna sort som faller från träden? Eller så kanske grannens ungar hinner palla dem innan de faller. Se där hur det kan gå om man är för snabb med sina slutsatser.  Vad nu Per menar med "induktion över n" har jag ingen aning om. Något slags fackuttryck som någon annan får hjälpa till med.  | ||
| Tillbaka till toppen |
| Arne Frennelius [85804] |
| ||
 inlägg: 237 | Saken är den att induktion och induktionsbevis inom matematiken inte har särskilt mycket med varandra att göra. Inom vetenskapsteorin talar man man om två olika sätt att skaffa sig kunskap: induktion och deduktion. Vid induktion utgår man från observationer av verkligheten, som man drar generella slutsatser av. Om man upptäcker att ens egna äpplen så småningom faller till marken kan man kanske induktivt dra slutsatsen att alla äpplen som hänger på trän så småniningom faller till marken. I nästa steg vågar man kanske dra slutsatsen att detsamma gäller för päron. Etc. Ett deduktivt resonemang bygger inte på observationer i verkligheten. I stället gör man slutledningar av typen "Äpplen är tyngre är luft och kommer därför enligt tyngdlagen att falla till marken". En dylik tes kan ev senare få stöd av empiriska observationer. Induktionsbevis inom matematiken används typiskt för att visa att ett påstående är sant för alla naturliga tal. (Naturliga tal är talen 0, 1, 2, 3,....) Man kan då beskriva metoden på följande sätt: Kontrollera att påståendet är sant för talet n = 0. Antag att påståendet är sant för n = m, där m är ett godtyckligt naturligt tal. Visa att påståndet då även gäller för n = m + 1. Nu vet vi att: Påståndet är sant för n = 0. Då är det även sant för n = 1 och då är det sant för n = 2 och så vidare. | ||
| Tillbaka till toppen |
| Lars Höglund [11139] |
| ||
 inlägg: 264 | Arne meddelade principerna för ett induktionsbevis. Ett enkelt exempel: Bevisa att summan av de n första positiva heltalen är n(n+1)/2. Uppenbart sant för n=1. Anta sant för n. 1+2+3+...n+(n+1)=n(n+1)/2+(n+1)=(n+1)(n+2)/2.Yes! Sant för 1 medför sant för 2 medför sant för tre osv. | ||
| Tillbaka till toppen |
| Thomas Larsson [15308] |
| ||
 inlägg: 484 | Tycker det är på sin plats att än en gång läsa följande artikel av Bosse Lindberg. » länk Ibland är saker så självklara att det krävs en jurist för att missförstå det. | ||
| Tillbaka till toppen |
|
| Leif Malvefors [24241] |
| ||
inlägg: 497 | Japp den var bra och belysande. Men skillnaderna mellan hand resp maskin är väldigt liten. Om nu handgivarna är blandade enligt alla matematiska regler. Vilket i vår klubb betyder att blandningen utförs alldeles för slarvigt! Och så länge vi inte har nån brickläggningsmaskin så kommer de fåtal ggr vi köper dessa tjänster att de framstår som svingade eller i varje fall som om någon mänsklig "liten skojare" har matat maskinen med speciella givar som vi inte har så ofta. Vanans makt är stor. God fortsättning önskar södra Halland! | ||
| Tillbaka till toppen |
| Per Hallberg [12555] |
| ||
inlägg: 56 | Daniel Auby[9601 skrev ... ] Vad nu Per menar med "induktion över n" har jag ingen aning om. Något slags fackuttryck som någon annan får hjälpa till med. Som Arne redan påpekat skiljer sig matematisk induktion (som jag lite slarvigt bara kallade "induktion") från vetenskapteorins induktion. Matematisk induktion är en bevisteknik som ibland är väldigt kraftfull. Ingenjör- och matematikstudenter brukar lära sig den i någon av de första mattekurserna på universitetet. För den intresserade tänkte jag förklara hur ett sådant bevis går till och exemplifiera med vår kortlekstillämpning (utan att kasta någon skugga på Arne och Lars som ju redan koncist förklarat idén). Vi vill bevisa att summan av antalet stigande och fallande följder för en permutation av talen 1, 2, ..., 52 alltid är 53. Det verkar ju inte så lätt då antalet tänkbara permutationer är enormt, men ibland kan en uppgift göras lättare om man generaliserar den, för att den då får "rätt struktur". Så låt oss i stället betrakta följande påstående: Summan av antalet stigande och fallande följder för en permutation av talen 1, 2, ..., n är n+1. Låt oss kalla detta påstående P_n för n=1,2,3,... Vår utsaga om en vanlig kortlek svarar då mot P_52. Vi vill bevisa P_52 men vi kommer av bara farten bevisa det mer generella P_n för alla n=1,2,3,... Ett induktionsbevis har tre komponenter: 1) Basfallet Detta består oftast i att man verifierar påståendet P_1 medelst inspektion. I vårt exempel lyder P_1: Summan av antalet stigande och fallande följder för en permutation av talet 1 är 2. Och detta är ju enkelt att verifiera, då ett element bara kan permuteras på ett sätt (nämligen "1") och denna permutation har precis en stigande och en fallande följd, dvs 2 stycken totalt. 2) Induktionssteget I denna del bevisar man implikationen P_n => P_(n+1). Man ska alltså visa att om påståendet P_n är sant så följer att P_(n+1) är sant. Låt oss här därför anta att påståendet P_n gäller. Vi ska nu visa att då följer P_(n+1), dvs att summan av antalet stigande och fallande följder av en permutation av talen 1, 2, ..., n+1 är n+2. Tag därför en sådan permutation av 1, 2, ..., n+1. Någonstans finns talet n+1 och tänk dig nu att du håller för det talet med ett finger. Kvar finns då en permutation av talen 1, 2, ..., n för vilken vi vet att summan av antalet stigande och fallande följder är n+1 (enligt vårt antagande). Tag nu bort fingret och betrakta den ursprungliga permutationen. Om talet n+1 står någonstans till höger om talet n kommer denna permutation ha samma antal stigande följder som den förra permutationen, eftersom den sista följden bara förlängs med talet n+1. Dock kommer den ha exakt en mer fallande följd, nämligen den ensamma följden n+1. Om talet n+1 befinner sig någonstans till vänster om talet n så gäller det omvända - en extra stigande följd, men samma antal fallande följder. Oavsett placering är dock summan av antalet stigande och fallande följder en mer än för permutationen med fingret för talet n+1. Så summan av antalet stigande och fallande följder för den betraktade permutationen är n+1+1 = n+2 vilket var just vad vi skulle bevisa. 3) Hänvisning till induktionsprincipen Har man gjort 1) och 2) ordentligt kan man tycka att vi har visat påståendet P_n för alla n=1,2,3,... Upprepade tillämpningar av induktionssteget gör ju att vi har bevisat först P_1 och sen P_2, P_3, P_4, ... Men har vi täckning för P_n för alla heltal n>0? Svaret är ja, men att så är fallet går inte att bevisa utan är taget som ett axiom (ett axiom är ett grundantagande, en sorts given spelregel), kallat induktionsaxiomet. Så ett utförligt induktionsbevis avslutar med hänvisning till induktionsprincipen eller induktionsaxiomet. Detta blev lite långt, men det kan vara kul att få en inblick i vad matematik handlar om bortom ren aritmetik (läs: grundskolan). Slutligen "induktion över n" var bara en slentrianmässig kommentar, för man brukar ange den variabel man "stegar med" i induktionen, särskilt om det finns flera att välja på. I vårt exempel kunde man, något långsökt, kunna få för sig att man numrerar permutationerna på något sätt och sen stegar igenom dessa i ett induktionsförfarande. | ||
| Tillbaka till toppen |
Gå till sidan << >>
| Moderatorer: Thomas Winther [3522], Fredrik Jarlvik [4451], Micke Melander [7164], Johan Grönkvist [8342], Roger Wiklund [10530], Carina Wademark [12540], Tommy Andersson [14659], Björn Andersson [14660], Andreas Jansson [19642], Pontus Silow [87294] |
Forum theme loosely based on Invision Power Board
Svenska Bridgeförbundet, Karlsgatan 28, 703 41, Örebro, Tel: +46 (0)19-277 24 80