1/52!

Den er vel antageligvis sandsynligheden for at du gætter rigtigt første gang (1/52) ganget med sandsynligheden for at du gætter rigtigt anden gang (1/51) etc, hvilket tilsammen er 1/(52!) - under antagelse af at spilleren konstant kan huske hvilke kort er blevet vendt og ikke gætter på et allerede vist kort.

EDIT: Og 1/52! er 1.23979993e-68

Et sted mellem 4 og 5%

Jeg læser det som at farven er ligegyldig, så det går galt i første runde, hvis du får et es, i anden runde, hvis du får en toer, ... I fjortende runde, hvis du får et es, i femtende runde hvis du får en toer osv. Der er ikke gode odds for at det går godt, men et sted mellem 4 og 5% er mit gæt uden at have regnet voldsomt på det.

Et sted i mellem de to foregående

Jeg forstår det ligesom Kai, at farven er ligegyldig. Derfor får jeg det til at der må være 4/52 ved første træk, 4/51 ved andet, 4/50 ved tredje. Ved 14. 3/39, ved 15. 3/38, ved 27. 2/26, og så kan I nok godt regne ud hvad jeg mener.

Dét synes jeg virker mere rigtigt.
Jeg prøvede det lige på lommeregneren en gang og fik sandsynligheden til 1,09E-50.

EDIT:Nej, nej, nej... Jeg regnede på at spilleren skulle gætte rigtigt hver gang. Men dét burde passe med ovenstående

Et nogenlunde gæt

Hver gang der bliver trukket et kort er der 4 mulige kort som stopper kabalen. dvs at der er 12/13 sandsynlighed for at kabalen fortsætter for hvert kort. derfor bliver sandsynligheden for at gennemfører kabalen (12/13)^52=0.0155 eller 1,55%.

Her har jeg ikke taget hensyn til at når det første kort bliver trukket og kabalen skal gå videre så skal det være mellem 2 og 13. Dette betyder at sandsynligheden for at man ikke trækker en 2-er i næste er en lille smule større, Jeg tror dog at dette ikke betyder noget særligt.

Så sandsynligheden er lidt over 1.55%

Et lidt bedre overslag

Jeg har overbevist mig selv :-) om at chancerne må være bedre end hvis

1. vi tager et kvart spil kort, fx alle ruderne
2. vi kører som ovenfor (men så altså kun es, to, .. konge)
3. vi gør det 4 gange og man skal vinde alle gange for at det tæller.

Her er det børnelærdom at chancen for at vide pkt 2 er ca 1/e, dvs ca 0.37.
For at vinde 4 gange bliver chancen 0.37 * 0.37 * 0.37 * 0.37, som er ca 0.018

Så vi er i nabolaget med etcifrede procenttal efter min mening.
Hvis vi vil tælle os frem, så behøver vi ikke kigge på alle 52! muligheder, men højst 52! / (24^13), men det er stadigt et voldsomt stort antal:
92024242230271040357108320801872044844750000000000

Jeg læner mig lige tilbage og ser om der er nogen med en smartere metode end bare at simulere skidtet og kvæle det i fx et 95% konfidensinterval :-)

Re: Et nogenlunde gæt

Hver gang der bliver trukket et kort er der 4 mulige kort som stopper kabalen.

1,557% chance for at overleve

Hver gang der trækkes et kort har spilleren 12/13 chance for at overleve. Og ved 52 forsøg giver det S = (12/13)^52 = 0,015573

Forklaring: Hver gang der trækkes et kort, og spilleren overlever, fjernes det kort både på positiv siden (kortet viser et tal, som kommer senere i rækkefølgen - sænker sandsynligheden for at dø ved næste træk) eller negativ siden (kortet viser et tal, som kommer tidligere i rækkefølgen - hæver sandsynligheden for at dø ved næste træk). De to effekter udbalancerer hinanden og sandsynligheden er den samme ved hvert træk, forudsat at man på forhånd ingen viden har om de tidligere udfald.

Matematisk skrives det sådan: Sandsynligheden for at dø ved næste træk: ((52 - j)/13)/(52 - j), hvor j er det træk, man er nået til. Udtrykket reduceres til 1/13. Altså er sandsynligheden for at overleve hvert træk 12/13.

Jeg evner ikke at forklare min hypotese bedre...

Edit: Øv, en anden kom først. Sådan går det, når man er for langsom ved tasterne :( Til gengæld har jeg forsøgt at forklare, hvorfor resultatet passer nøjagtigt :)

Re: Et nogenlunde gæt

Du kan bare skrive et simuleringsprogram :-) Jeg tror ikke at det er helt håbløst. Man kan beskrive en tilstand som en vektor med 13 tal, der fortæller hvor mange af hver slags man har tilbage. Man starter med en sandsynlighed på 1 for at være i tilstand (4,4,4,4,4,4,4,4,4,4,4,4,4). Herfra kan man så komme til 13 tilstande hvoraf en er tabt. Fra hver af de 12 ikke-tabte tilstande kan man komme til en tabt og 12 ikke-tabte. Osv men man skal holde nøje styr på det hele undervejs. Til sidst kan man så lægge sandsynlighederne for de vundne sammen.
Jeg kan ikke gennemskue hvor meget tid og plads, den udregning tager, men 5^13 er jo ikke helt vildt afskrækkende, når man kan tynde ud i træet undervejs, men det er heller ikke trivielt lille.

Mellem 4.25% og 4.30%, tror jeg.

Et ikke voldsomt gennemchecket program, jeg lige klaskede sammen, påstår at det er et godt gæt med et sted mellem 4.25% og 4.30%. (Jeg har simuleret 5 gange 1 million spil.)

Cirklens kvadratur

Løsningen skal søges i teorierne om cirklens kvadratur samt i den kendsgernig, at jeg endnu kun har fået 1 whisky. Dvs. 1/4 af det optimale i forhold til kortspillets 4 kulører. Cirklens omkreds er 2 x Pi x R. Da cirklens radius er ligegyldig bliver 1/4 af omkredsen Pi/2. Jeg ryster stadig lidt på hånden, men det ses let heraf, at sandsynligheden bliver meget tæt på Pi/2 %.
Noget bedre bud?

Spilleren bør vel også tænke sig om

Og så skulle det vist være muligt at komme igennem bunken med omkring 90% sandsynlighed.
Vel noget der nærmer sig en 12/13 chance.

Metoden må være som udgangspunkt hele tiden at nævne det kort som netop er blevet vendt.

Re: Spilleren bør vel også tænke sig om

Og dog :|
Der skal vist regnes lidt mere :)

Bedre en 7 %

48/52*
(48*47*...*36)/(51*50*...*39)*
(36*34*...*24)/(38*37*...*26)*
(24*23*...*12)/(25*24*...*12)*
(12*11*...*1)/(12*11*...*1)
=
48*36*24*12/52*51*50*49
=7,6%

Simuleret i Excel

Jeg har simuleret opgaven i Excel.
Men random generatoren har jeg genereret 117068 fordelinger af kortene. De er så holdt om mod en fast spillersekvens. Det burde ikke betyde noget om man varierer spillerens sekvens.
Ud af de 117068 spil, vindes 1921. Dvs 1.64%.

Hvis jeg spiller alle spillene til ende, i stedet for stoppe ved første hit, så får jeg en nydelig fordeling over antallet af hits pr. spil. Det ligner en ventetidsfordeling med et gennemsnit på 4.

Resultat med antagelse!

Puha!
Hvis man nu antager at der er trukket et kort af hver type efter hver 13 kort, så mener jeg regnestykket bør se således ud:
(48/52)*(47/51)*(46/50)*(45/49)*(44/48)*(43/47)*(42/46)*(41/45)*(40/44)*(39/43)*(38/42)*(37/41)*(36/40)*(36/39)*. . . . . . . (24/27)*(24/26)* . . . . . . (12/14)* (12/13)* . . . . . . . (1/2)*100% = 0,159571520916059 sandsynlighed for at spiller taber, så sandsynligheden for at det går godt må være:
99,8404284790839 %

(12/13)^52 = 1,56%

Tror de fleste kan blive enige om at sandsynligheden for ikke at vende det forkerte kort er 12/13 for det første kort i bunken.

Og man kan sikkert også overbevise sig selv om at det samme må gælde for det sidste kort i bunken (hvis man kommer så langt). Der er jo trods alt stadigvæk 1 ud af 13 mulige for at man får det forkerte.


For det andet kort man vender må der gælde:

Hvis det første var en TOer: 1/13 * 48/51 (3 TOere tilbage)
Det første var ikke en TOer: 12/13 * 47/51 (4 TOere tilbage)

Hvilket giver: 12/13

Så vil sige at løsningen (12/13)^52 = 1,56% som andre også postulere ser rigtigt ud.



Kan også prøve at tænke på det lidt anderledes:

Vi har en bunke kort og vi vender et af gangen. Så i princippet er det jo ligegyldigt hvad alle de forrige kort har været. Kort nummer N er jo stadigvæk det samme når du kommer ned til det. Og fra starten af har du jo 1/13 chance for at kortet på position N er det forkerte. Den sandsynlighed ændrer sig jo ikke af forhistorien (hvad dealeren har vendt af de første N-1 kort).

Spillerens strategi skal defineres

Man er nødt til først at tage stilling til hvilken strategi spilleren anvender: De korrekte 1,557% (12/13)^52 forudsætter at spilleren har den strategi, at vælge et helt tilfældigt af de 13 kort hver gang.

Han kan vælge både dårligere og bedre strategier:
Den dårligste jeg lige kan komme på, at f.eks. at have lykketallet 7, og så vælge det kort hver gang. Der dør spilleren med garanti senest ved kort nr. 49, så chancen her er 0%

En bedre strategi, er selvfølgelig at huske alle kort, og så hver gang vælge et tal fra de kort som er udtrukket flest gange og dermed har mindst chance for at komme igen. Når der er trukket 40 kort, er det med garanti et kort, som ikke længere er i bunken, og det er derfor sikkert at vælge, så umiddelbart kan man sige at chancen i hvert fald stiger til (12/13)^40 dvs ca, 4%, men sandsynligheden er bedre, prøv at se dette eksempel:

Træk 1:
Vi vælger et helt tilfældigt tal, lad os sige 7. Da der er fire 7'er og 48 andre kort, er chancen altså 48/52 = 12/13.
Der blev aktuelt trukket en 5er
Træk 2:
Nu er bedste chance at satse på 5, idet der kun er tre 5er tilbage, så chancen for at overleve er 48/51
Der blev aktuelt trukket en 6er
Træk 3:
Nu er det lige godt at satse på 5 og 6, for begge er chancen for overlevelse 47/50 Vi vælger blot 5 igen.
Overvejelser om træk 4:
Nu kan der ske to ting (ud over der trækkes en 5er og så er vi jo døde), trækkes der en 6er, skal vi skifte til at gætte på 6, idet chancen for overlevelse så er 47/49, men trækkes et andet kort end 5/6 f.eks 7, kan vi frit vælge at gætte på 5,6, eller 7 til overlevelse 46/49.
Tilsvarende overvejelse gør sig gældende hele vejen igennem, senest i træk 14 har vi dog et kort som er trukket to gange, indtil vi når de 40 kort, hvor vi så har et sikkert kort at satse på, Men undervejs, er der hele tiden chancen for at der kommer et mere sikkert kort, som vi så bør skifte til, men vi kan i hvert fald tage worst case som (48/52*48/51*47/50*46/49*45/48*44/47*...36/39*36/38*35/37*34/36*...12/13*1*1*1*1*1*...*1=7,66%.

Re: Spillerens strategi skal defineres

Helt enig - du kom mig i forkøbet - og med klarere resonnement end jeg kunne have præsteret.
Hvis man gør den antagelse, at spilleren kan huske alle kort og altid vælger et af de kort, der er gået flest af, så skal der naturligvis være en bestemt gevinstchance.
Men skal man regne chancen ud, skal man allerede efter 2. træk til at regne videre med flere udfaldsscenarier, så regnestykket bliver for mig at se yderst kompliceret.
I øvrigt kunne spillet jo spilles med en dealer (eller en bunke på bordet) og et antal spillere. Ren hukommelseskonkurrence.

Der er ingen strategi i denne opgave.

Opgaven er lidt uklart formuleret, men det fremgår dog, at der tælles eller nævnes tal "i sekvensen "Es, 2, 3..., dame, konge." Altså skal man sige ES TO TRE FIRE FEM SEKS SYV OTTE NI TI J D K (og forfra igen) og ikke begynde at gætte eller variere på talrækken. Herved er strategien defineret.

Kristian Kristensen er på rette spor, og Peter Weis har fundet et godt bud på den numeriske værdi. Det er helt korrekt, at resultatet bliver større end eksemplet med tilbagelægning. Den eksakte sandsynlighed findes naturligvis ved (antal vindende kortpermutationer) / 52!

Simuleret i MATLAB

Jeg har simuleret opgaven i MATLAB, og mit resultat lægger sig meget tæt op ad Peter Weis' resultat:

1.62264%

ved 10^7 forsøg.

Og jeg har forstået opgaven som, at kortene altid bliver nævnt i rækkefølgen (Es, 2,3,...,K,Es,2,3,....).

Re: Simuleret i MATLAB

Jeg fandt en spøjs fejl i mit program og erklærer mig enig i de
ca 1,62% Jeg fik 162029/10000000.

(12/13)^52 er et godt overslag, men som nævnt skal det være en brøk af formen "helt tal"/52!, så det er ikke det rigtige resultat.

Jeg kunne ikke lide at det også skulle give 12/13 i anden omgang og det gør det heller ikke. Der er 52 * 51 = 2652 muligheder for de første to kort. Af disse er 4 * 51 = 204 ude efter første omgang. Af de resterende 2448 går 188 ud og 2260 går videre. 2260/2448 er lidt større end 12/13.

Arduino siger...

1,6% til 1,7% - hvis det gættes uden form for strategi...


Kode:
int list1[52] = {};
int list2[52] = {};
unsigned long total = 10000;
unsigned long noMatchTotal = 0;

void setup(){
Serial.begin(9600);
randomSeed (analogRead(0));
int pos = 0;
for (int i=1;i<14;i++){
for (int j=0;j<4;j++){
list1[pos] = i;
list2[pos] = i;
pos++;
}
}
}

void loop(){
noMatchTotal = 0;
for(unsigned long i=0;i<total;i++){
shuffle(list1,52);
int match = 0;
for (int k=0;k<52;k++){
if (list1[k] == list2[k]){
match = 1;
break;
}
}
if (match == 0) noMatchTotal++;
}
Serial.println(1.0*noMatchTotal/total*100);
}

void shuffle(int *list, int elem)
{
for (int a=0; a<elem; a++){
int r = random(a,elem);
int temp = list[a];
list[a] = list[r];
list[r] = temp;
}
}

re. spillerens strategi

der ser ud til at være forvirring om Spillerens strategi - hvilket tal skal han vælge. For mig at se er der INGEN strategi, spilleren OPREMSER tal i fast rækkefølge ES,2,3,.. etc (jf. eksemplet givet i teksten) så der er ingen strategi. Spilleren er egentlig heller ikke nødvendig som sådan, DEALER kan opremse selv :-)

Re: (12/13)^52 = 1,56%

Tror de fleste kan blive enige om at sandsynligheden for ikke at vende det forkerte kort er 12/13 for det første kort i bunken.

Og man kan sikkert også overbevise sig selv om at det samme må gælde for det sidste kort i bunken (hvis man kommer så langt). Der er jo trods alt stadigvæk 1 ud af 13 mulige for at man får det forkerte.

For det andet kort man vender må der gælde:

Hvis det første var en TOer: 1/13 * 48/51 (3 TOere tilbage)
Det første var ikke en TOer: 12/13 * 47/51 (4 TOere tilbage)

Hvilket giver: 12/13

Vi har en bunke kort og vi vender et af gangen. Så i princippet er det jo ligegyldigt hvad alle de forrige kort har været. Kort nummer N er jo stadigvæk det samme når du kommer ned til det. Og fra starten af har du jo 1/13 chance for at kortet på position N er det forkerte. Den sandsynlighed ændrer sig jo ikke af forhistorien (hvad dealeren har vendt af de første N-1 kort).

Her er en Delphi version

Der var engang i programmeringssprog der hed Pascal, som jeg vil gøre lidt reklame for her:

const plays = 10000000;


type tdeck = array [1..52] of integer;

var deck : tdeck;
guess : integer;

procedure init(var deck : tdeck);
var i : integer;
begin
for i := 0 to 52-1 do
deck[i+1] := i mod 13 +1;
end;

procedure shuffle(var deck : tdeck);
var i, husk, p1, p2 : integer;
begin
for i := 1 to 100 do
begin
p1 := random(52)+1;
p2 := random(52)+1;
husk := deck[p2]; deck[p2] := deck[p1]; deck[p1] := husk;
end;
end;

function PlayerGuess : integer;
begin
guess := guess+1;
result := guess mod 13 +1;
end;

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
var ok : boolean;
won, n,i : integer;
begin
randomize;
won := 0;
for N := 1 to plays do
begin
init(deck);
shuffle(deck);
guess := random(13)+1;
ok := true;
for i := 1 to 52 do
if deck[i] = playerguess then
begin
ok := false;
break;
end;
if ok then inc(won);
end;
caption := floattostr(won / plays);
end;

får 0,0167

No a good Knuth

Hej Thomas

Din shuffle procedure "is not a good Knuth" shuffle ;)

http://en.wikipedia.org/wiki/K...ffle

-Eivind

Re: Spilleren bør vel også tænke sig om

Metoden må være som udgangspunkt hele tiden at nævne det kort som netop er blevet vendt.

Re: No a good Knuth

[quote]Hej Thomas
Din shuffle procedure "is not a good Knuth" shuffle ;)
-Eivind[/quote]
Nej, den "shuffle" er helt gal. Den bør set omtrent sådan ud:

procedure shuffle(var deck : tdeck);
var i, husk, p1, p2 : integer;
begin
for i := 1 to 52 do
begin

p12 := random(52 - i ) + i;
husk := deck[i]; deck[i] := deck[p12]; deck[p12] := husk;
end;
end;

Med forbehold for fejl i detaljerne, så skal en god shuffle sikre, at ethvert givet kort optræder med samme sandsynlighed (1/52) på enhver givet plads. Det kan gøres ved at tage kortstakken fra en ende af, og bytte hvert kort med et tilfældigt kort i resten af stakken inkl. kortet selv - men ikke hele stakken.

Modargument mod (12/13)^52

Antag at der er to kort. En etter og en toer.
Ved første kort har man sandsynlighed 1/2 for at gå videre.
Ved andet kort har man også sandsynlighed 1/2 for at gå videre.
Samlet set 25% for at vinde.

Men det holder jo ikke. Der er to mulige ordninger af kortene: [1,2] eller [2,1], med lige stor sandsynlighed, og man vinder med den ene.

Hvis heldig 7,659%, hvis uheldig 0,185%

Synes det er lidt et trick spørgsmål, som kommer an på held.
Derudover forudsætter jeg at man skal nævne tallene i rækkefølge, sådan som jeg læser opgaven.
I begge tilfælde er chancen ved første kort (48/52) % herefter er det henholdsvis (47/51) % hvis uheldig og (48/51) % hvis heldig.
Altså om det kort du nævner lige har været der eller kommer som nummer 2 efter det du har sagt.
Ved uheldig når du starter siger du es der kommer en konge, du siger 2 der kommer et es, du siger 3 der kommer en 2 osv. Hermed er de første 12 børker ligmed resterende antal kort -4 / resterende antal kort, de næste 13 bliver med -3 istedet de næste 13 med -2, de næste 13 -1 og den sidste -0. Det skal jo lykkes, dette giver til slut 0,185 % chance for at nå igennem bunken.
Ved heldig når du starter siger du es der kommer en 2, du siger 2 der kommer en 3 osv. Hermed bliver brøkerne således den første, resterende antal kort -4 / resterende antal kort, de næste 13 med -3, de næste 13 med -2, de næste 13 med -1 og de sidste 12 med -0. Dette giver 7,659%.

Bedre illustreret er det hvis vi skærer mængden ned til 13 kort, hvis man følger samme scenarie får man enten ved uheldig 7,69% chance for at lykkes eller ved heldig 92,31% chance for at lykkes. Fordi når du har fået det første, er der 100% chance på de sidste 12.

Så som konklusion må sandsynligheden være alt imellem 0,185 - 7,659 % alt efter hvor heldig man er.

ja og

hvad er svaret så......kom så med det. eller ved du det ikke selv

Re: No a good Knuth

I har nok ret, - men jeg vil hævde, at den er væsentlig grundigere, end når min kone blander kort :-)

Re: Simuleret i MATLAB

Jeg har også brugt 'brute force' metoden med Matlab, og fik 1.6283% ved 10^6 spil, og 1.6209% ved 10^7.

MVH Lars

Punktum

Jeg har brugt den HELT store regnemaskine (for nu at citere Kristian Hougaard) og det eksakte svar er et brøk med
1309302175551177162931045000259922525308763433362019257020678406144 i tælleren og 80658175170943878571660636856403766975289505440883277824000000000000 i nævneren.
Det giver 1,623272746719463674812955651327869441746349602564120334538..% sådan cirka :-)

Punktum

OK Kai, må vi lige se hvordan du er nået frem til resultatet?

Re: Punktum

Ideen er at holde styr på hvor mange esser, toere, ... konger, der er tilbage.
Det kan skrives med 13 tegn, fx starter vi med 4444444444444, dvs 4 af hver. Hvis vi så tager et enkelt kort, kan vi tage et af de 4 esser, hov vi døde, eller en af de fire toere, eller en af de fire treere, osv
Dvs i generation 1 er mulighederne:
4 x 4344444444444 eller 4 x 4434444444444 eller ....
Det spændende er så om det her eksploderer i hænderne på os eller om man kan finde på en måde at begrænset det på.
Det viser sig at være pænt indenfor det mulige på en standard-pc.
I alt er der 5^13 muligheder fra 4444444444444 til 0000000000000 (for
på hver af de tretten pladser kan der stå 0,1,2,3 eller 4.).
Hvis vi skal holde styr på antallet af måder man kan være havnet i hver enkelt tilstand, så er værste tilfælde 0000000000000, som vi udfra ovenstående simuleringer tror er ca 1,6% af 52! hvilket er ca 70 cifre.
Vi runder generøst op fra 13 tegn + 70 cifre til 100 pr tilstand og vi har 5^13 = ca 1,2 milliard, så 120 gb diskplads ser ud til at være rigeligt.
Undervejs har vi en udfordring med mellemresultater, men det kommer jeg til.
Et lille program kan hurtigt tøffe igennem de 1.2 milliarder muligheder og fordele på de forskellige summer og 26 kort viser sig (ikke så overraskende) at "vinde" med 94309099 mulige måder at nå dertil.
Dvs vi forventer ca 94 millioner linier med ca 100 tegn i hver, som det mellemresultat, der fylder mest. Vi har rundet pænt op undervejs, men lad os sige 5 Gb som et realistisk bud på hvad det koster at huske på alle måder, vores spil kort kan se ud på efter at vi har lagt 26 kort.

Vi er ikke helt i mål, for vi er nødt til at kunne slå dubletter sammen undervejs. Jeg prøver at forklare:
Generation 0 er "4444444444444"x1
Generation 1 er "4344444444444"x4, 4434444444444"x4, osv
Generation 2 er .... "4444444444433"x16, ..... , "4444444444433"x16, ...
Dvs en situation hvor vi har taget en dronning og en konge kan vi få
på 16 måder og vi er jo i samme situation, hvis vi har taget en konge og en dronning, så det er 16 måder mere. De to skal vi have lagt sammen til "4444444444433"x32, hvis ikke filstørrelserne skal eksplodere.
Det nemmeste er at lave to programmer. Det ene laver næste generation og er ligeglad med dubletter. Det næste slår dubletter sammen, men bekymrer sig ikke om andet.
Dubletfjerne-programmet har det nemmest, hvis de enkelte muligheder
kommer i sorteret rækkefølge, mens Næstegeneration-programmet helst ikke vil tænke over det.
Ergo skyder vi bare en sorteringskommando ind imellem, så
her er løsningen:

Næstegeneration (skrevet i perl):
while (<>) {
die unless /^(\d+):([^:]*):(\d+)$/;
$g = $1;
@f = (split(//,$2));
$m = $3;
for $f (0..12) {
next if ($f % 13) == ($g % 13);
if ($f[$f] > 0) {
$f[$f]--;
$ftext = join("",@f);
$f[$f]++;
print "".($g+1).":$ftext:${m}x$f[$f]\n";
}
}
}

Fjerndubletter skrevet i python:
import fileinput
import sys
def printf(fmt, *varargs):
sys.stdout.write(fmt % varargs)

first = 1
lastkey = "NADA"
sum = 0
for line in fileinput.input():
(gen,thiskey,mult) = line.split(":")
(multa,multb) = mult.split("x")
if first == 1:
sum = int(multa) * int(multb)
lastkey = thiskey
first = 0
else:
if thiskey != lastkey:
printf("%s:%s:%s\n",gen,lastkey,sum)
lastkey = thiskey
sum = int(multa) * int(multb)
else:
sum = sum + int(multa) * int(multb)
printf("%s:%s:%s\n",gen,thiskey,sum)

Og så en kommandofil til at sætte skub i tingene:

echo "0:4,4,4,4,4,4,4,4,4,4,4,4,4:1" > 00.g
cat 00.g | perl ng | sort | python simplificer > 01.g
cat 01.g | perl ng | sort | python simplificer > 02.g
cat 02.g | perl ng | sort | python simplificer > 03.g
cat 03.g | perl ng | sort | python simplificer > 04.g
cat 04.g | perl ng | sort | python simplificer > 05.g
cat 05.g | perl ng | sort | python simplificer > 06.g
osv

Efter at røgen har lagt sig, indeholder 52.g så
52:0000000000000:1309302175551177162931045000259922525308763433362019257020678406144

Lidt bemærkninger:
Python blev valgt, fordi den har en rimelig effektiv implementation af lange heltal.
Undervejs er der pænt store mellemresultater.
perl ng 26.g giver ca 60 Gb, inden simplificer skærer det ned til 4,7 Gb
så det må gerne køre på en disk med nogle hundrede gigabytes ledigt.

En enkelt sød ting:
51.g indeholder:
51:0000000000001:106870657266741703846538272785050110260756967966691383236014112768
51:0000000000010:109108514629264763577587083354993543775730286113501604751723200512
51:0000000000100:109108514629264763577587083354993543775730286113501604751723200512
51:0000000001000:109108514629264763577587083354993543775730286113501604751723200512
51:0000000010000:109108514629264763577587083354993543775730286113501604751723200512
51:0000000100000:109108514629264763577587083354993543775730286113501604751723200512
51:0000001000000:109108514629264763577587083354993543775730286113501604751723200512
51:0000010000000:109108514629264763577587083354993543775730286113501604751723200512
51:0000100000000:109108514629264763577587083354993543775730286113501604751723200512
51:0001000000000:109108514629264763577587083354993543775730286113501604751723200512
51:0010000000000:109108514629264763577587083354993543775730286113501604751723200512
51:0100000000000:109108514629264763577587083354993543775730286113501604751723200512
51:1000000000000:109108514629264763577587083354993543775730286113501604751723200512

Dvs sandsynligheden for at sidste kort er en konge er lidt mindre end sandsynligheden for at det er fx en toer.

Punktum

Imponerende arbejde, Kai!

Re: Punktum

Elegant Kai

Jeg skal gerne erkende, at jeg troede den helt store lommeregner skulle være temmelig meget større, selvom du har nogle halvstore tal :-)

Det er et smart princip med at udregne og reducere. Det er bestemt et princip jeg fluks vil forsøge at lære noget af. Hvor længe måtte din stakkels computer tykke på tallene?

Nu kan tråden vist godt lukkes :-)

/Kristian

Re: Punktum

Tak for rosen, Thomas og Kristian.

Jeg brugte min stationære computer på jobbet, fordi den havde en pænt stor lokal disk, der ikke rigtig blev brugt til noget. Den fik lov at tygge på tingene fra fredag formiddag til mandag aften, så lidt over 3 døgn.
Ideen med at bruge sort og reducere skyldes sikkert at jeg har læst Jon Bentleys Programming Pearls bøger. De er hermed anbefalet, for der er mange gode tricks og observationer. Men tilbage til emnet:

For sjov har jeg summeret antal muligheder for hvert kort, der bliver taget af bunken:

48
2260
104336
4721112
209294336
9086251648
386126062080
16054059141376
652735274872832
25939465666169856
1006981206848073728
38165544515820390400
1411407822148941643776
50810681597361899175936
1782525384437457653809152
60896642013642512885760000
2024464295929574113047871488
65441072928806607530485481472
2055223887848151378407222280192
62655623776201064845234309300224
1852481122119966762745223876444160
53065911398282011149710004464910336
1471272206435277284704840440594038784
39436903317262212014817282144363085824
1020769934359488629706031637759879282688
25480829094840717844251181963252114391040
611539898276177228262028367118050745384960
14114386033210100851264584751316920159961088
312773024410728675390532763708482758106939392
6643112950936736260422095085923182570213736448
134979207124521325885624826905722931687918141440
2618281650150075594639124616276453835768154030080
48376427361454826138747763104989937622941857480704
849242408747529825622709605656718083029262051311616
14125535331607003148782498696896256045811224515969024
221927258041509483310611250071089352386473743592980480
3282034443842088945377746771871848957987890305999831040
45509516164435019432146091486124570585978656821327429632
589051179399417525268184878171559602078015687885395591168
7068614152793010303218218538058715224936188254624747094016
78309200158995810803905595202045709885452627348116043988992
795356232180825687051032146904297461023120556555230095867904
7344740137806850595759575343218480654690481860469053798219776
61050863319409191553101934959590244519769664389752270725578752
451141079985488776137427482798327100486585979028482157680001024
2917415626154872246202353312077649704287499073165009553612341248
16173140563342413570710762339863818224363326813606816993222066176
74724960982860671030803122244912801581494179876824824258834202624
276237834046589801166607323976054849846870816990801819090632572928
765980381763177493422789499224515905618273998970065228230333300736
1416172832817918866777583273044972635569520401328710640256692518912
1309302175551177162931045000259922525308763433362019257020678406144

Hvis man dividerer med 52, 52*51, 52*51*50, osv får man sandsynligheden for at kabalen ikke er død endnu efter det tilsvarende antal kort og som "kontrol" er (12/13) opløftet i samme potens anført i kolonne 2. Det er jo en helt fin tilnærmelse og man ser at hvis man nøjes med at lægge 13 kort, så får man en kabale, der går op ca hver tredje gang og med 26 kort går den op ca hver ottende gang. Det passer nok bedre til de flestes temperament end at fortsætte til hele spillet er brugt, for så er det jo kun ca hver tresindstyvende gang, den går op.

1 .92307692307692307692 .92307692307692307692
2 .85218702865761689291 .85207100591715976330
3 .78684766214177978883 .78652708238507055074
4 .72661556930464493489 .72602499912468050837
5 .67108361293235242815 .67017692226893585388
6 .61987776889260887115 .61862485132517155742
7 .57265437734191378109 .57103832430015836070
8 .52909762693051845900 .52711229935399233295
9 .48891725182981593038 .48656519940368523041
10 .45184642319230567541 .44913710714186328961
11 .41763981827815995750 .41458809890018149810
12 .38607185195969564206 .38269670667709061363
13 .35693505665926537249 .35325849847116056642
14 .32947851383932188230 .32608476781953283054
15 .30417548150876895359 .30100132414110722819
16 .28085366926512200250 .27784737613025282602
17 .25935485247677514448 .25647450104331030094
18 .23953369998738032711 .23674569327074797010
19 .22125670160690393453 .21853448609607504932
20 .20440118671037724327 .20172414101176158399
21 .18885442603703155583 .18620689939547223137
22 .17451280948400770768 .17188329174966667511
23 .16128109332668352592 .15866150007661539241
24 .14907171087778004358 .14645676930149113146
25 .13780414112513465619 .13519086397060719827
26 .12740433036820690332 .12479156674209895224
27 .11760399726296021845 .11519221545424518669
28 .10857235781979178825 .10633127580391863386
29 .10024790971778211715 .09815194689592489280
30 .09257417212497994777 .09060179713469990104
31 .08549926713524740135 .08363242812433837019
32 .07897553683953029071 .07719916442246618787
33 .07295919293156350989 .07126076715919955803
34 .06740999602372566994 .06577916968541497664
35 .06229096209938068630 .06071923355576767075
36 .05756809375592180300 .05604852328224708069
37 .05321013409997794335 .05173709841438192064
38 .04918834134476483453 .04775732161327561905
39 .04547628233109430448 .04408368148917749451
40 .04197810676716397337 .04069262906693307185
41 .03875431937657640177 .03756242683101514325
42 .03578296544920463861 .03467300938247551684
43 .03304388297353244634 .03200585481459278478
44 .03051855318846005073 .02954386598270103210
45 .02818996386055054769 .02727126090710864502
46 .02604248417943630343 .02517347160656182617
47 .02406175026260984349 .02323705071374937800
48 .02223456035036490870 .02144958527423019508
49 .02054877885306543137 .01979961717621248776
50 .01899324848695839477 .01827656970111921947
51 .01755770980209428064 .01687067972411004874
52 .01623272746719463674 .01557293512994773730

Det kunne være sjovt at se hvor hurtigt det ville køre på en ramdisk på et par hundrede Gb, men sådan en har jeg ikke lige liggende :-)
Programmerne kan helt klart optimeres, men nu har jeg jo regnet resultatet ud, så det er ikke så tillokkende.

Re: Punktum

Jeg har brugt den HELT store regnemaskine (for nu at citere Kristian Hougaard) og det eksakte svar er et brøk med
1309302175551177162931045000259922525308763433362019257020678406144 i tælleren og 80658175170943878571660636856403766975289505440883277824000000000000 i nævneren.
Det giver 1,623272746719463674812955651327869441746349602564120334538..% sådan cirka :-)

Re: Punktum

Jeg har brugt den HELT store regnemaskine (for nu at citere Kristian Hougaard) og det eksakte svar er et brøk med
1309302175551177162931045000259922525308763433362019257020678406144 i tælleren og 80658175170943878571660636856403766975289505440883277824000000000000 i nævneren.
Det giver 1,623272746719463674812955651327869441746349602564120334538..% sådan cirka :-)

Super, at du har fundet den eksakte løsning. :-)

Umiddelbart kan brøken jo i hvert fald forkortes med 2, men kan man forkorte den yderligere? VI kan lige så godt se, hvor "pæn" den kan blive. Det er sikkert en forholdsvis triviel opgave, hvis man har de rette programmer, men det har jeg ikke, så måske en kunne hjælpe?

Re pæn, minimal løsning (punktum)

jeg foreslår at opløse tallene i primfaktorer og eliminere hvad der er fælles faktorer. Jeg prøvede i Excel, men excel kan tilsyneladende ikke håndtere heltal med det antal cifre ... (sic).

Re: Punktum (kristian kristensen)

super program Wolfram: indtast 309302175551177162931045000259922525308763433362019257020678406144 / 80658175170943878571660636856403766975289505440883277824000000000000
Så gør programmet arbejdet for dig :-))
http://www.wolframalpha.com/

Ro på

Det er jo bare at køre Euklids algoritme på det. 2^41 er største fælles divisor:

$ cat euklid.bc
define euklid (m,n) {
while (n != m) {
if (n > m) {
n = n - m
}
if (m > n) {
m = m - n
}
}
return m
}

euklid(309302175551177162931045000259922525308763433362019257020678406144,80658175170943878571660636856403766975289505440883277824000000000000 )
2^41
$ cat euklid.bc | bc -ql
2199023255552
2199023255552
$

Det er overkill at faktorisere tallene først.
Hvis nu der havde været et hav af små faktorer i tælleren, kunne man have håbet på at vi havde overset noget og at der var en simpel formel for at regne resultatet ud (noget i stil med x/52 * y/51 * z/50 ,,,,), men nej.

Re: Punktum

Umiddelbart kan brøken jo i hvert fald forkortes med 2, men kan man forkorte den yderligere?

Ro på. Take 2.

Pokkers. Nu kom jeg jo til at skrive af fra Kristian, der havde glemt forreste 1-tal af tælleren.

Det giver lige en faktor 3^17 (som jeg også syntes jeg havde set før :-)
Dvs største fælles divisor er 283982221662775934976 og den forkortede brøk bliver:
4610507544750288132457667562311567997623087869
over
284025438982318025793544200005777916187500000000

Spillets navn og en artikel

Ville egentlig bare regne brøken ud fra Kai's sidste indlæg, så indtastede 4610507544750288132457667562311567997623087869 / 284025438982318025793544200005777916187500000000 i mit google søgefelt. Udover brøkens værdi gav søgningen også et link til en artikel der gennemgår præcis dette problem. Spillet hedder åbenbart frustration solitaire og en googlesøgning på navnet giver nogle forskellige artikler om problemet. Blandt andet denne: http://www.scribd.com/doc/2635...aire .

Wolfram Alpha

Ja, Google Calculator er god til den slags.
Til dette, og også meget mere langhårede ting, er Wolfram Alpha også rigtig god:
http://www.wolframalpha.com/

Re: Spillets navn og en artikel

Morsomt. Det havde jeg ikke lige tænkt på. Tak til Anders for det.

Nu vi er i gang med den slags. Jeg bliver meget glad, hvis nogen kan finde lidt referencer til nedenstående spil. Jeg faldt over det i en gammel bog, hvor der bare stod at det var beskrevet af Bernoulli, men ikke hvilken Bernoulli og ikke hvor eller hvornår :-( I bogen var det 2 millioner parisere, men det tror jeg ikke spiller nogen rolle :-)

Vi tager 2000000 mennesker og giver dem en mønt hver. De kaster nu hver for sig plat og krone og forlader spillet, hvis de på et tidspunkt har fået lige mange plat og kroner. Hvis vi antager at de kan nå et kast i sekundet, hvornår er de mon så færdige allesammen ?

Re: Spillets navn og en artikel

Jeg svarer lige på mit eget spørgsmål :-) Vha Sloanes encyclopedia of Integer Sequences oeis.org har jeg fundet ud af at sandsynligheden for at være med i plat og krone spillet ovenfor efter n omgange er K(2n,n)/2^(2n).
Man kan omformulere det til at være et spørgsmål om bitstrenge af længde 2*n og så dukker nævneren 2^(2n) naturligt op.
Hvis der er nogen, der har et overbevisende argument for at tælleren lige bliver K(2n,n), hører jeg gerne om det.
http://oeis.org/A000984 har en masse links, bare ikke nogen, der ser ud til at handle om det her problem.

Re: Spillets navn og en artikel

Ah, set med de rette briller er det A063886: Number of n-step walks on a line starting from the origin but not returning to it.
Lidt regnerier giver at sandsynligheden for at være med i plat og krone spillet ovenfor efter n omgange er 1/sqrt(pi * n). Det er lidt sjovt at pi dukker op og kvadratroden gør at der skal pænt mange omgange til før alle 2 millioner er gået ud af spillet. Case closed.