Kans op oplossing "Cijfers en Letters"

Moderators: dirkwb, Xilvo

Gebruikersavatar
Berichten: 10.557

Kans op oplossing "Cijfers en Letters"

Ik heb een vraag over het spelletje "Countdown", of in het Nederlands "Cijfers en Letters". Maar mijn vraag gaat met name over het "cijfers" gedeelte. Ik speel zo'n spelletje wel eens op mijn telefoon.

Korte uitleg van het spel: Men krijgt een willekeurig getal tussen 100 en 999. En men krijgt 6 getallen, waarmee door optellen, aftrekken, delen en vermenigvuldigen, dit getal gemaakt moet worden. Die 6 getallen zijn 2 "grote" (twee uit het rijtje 25, 50, 75 of 100, zonder teruglegging) en 4 "kleine" (uit het rijtje 1 tot en met 10, mét teruglegging). Elk getal mag maar 1 keer gebruikt worden dus in totaal kun je 5 keer een bewerking doen.

Wat me nu opvalt: het lukt niet atijd om een oplossing te vinden maar toch verrassend vaak wél. Ik schat dat in zeker 95% van de gevallen een oplossing mogelijk is/blijkt en dat vond ik opvallend hoog. Ik vraag me nu af of je kunt berekenen hoe groot de kans is dat een willekeurige "opgave" inderdaad een oplossing heeft. Hoe zou je zoiets aan kunnen pakken?
Cetero censeo Senseo non esse bibendum

Gebruikersavatar
Berichten: 7.463

Re: Kans op oplossing "Cijfers en Letters"

Heb je al een voorbeeld waarbij er zeker geen oplossing bestaat?

Gebruikersavatar
Berichten: 10.557

Re: Kans op oplossing "Cijfers en Letters"

Hierbij een voorbeeld:

Doel: 781

Getallen: 3, 4, 9, 10, 50 en 100
Cetero censeo Senseo non esse bibendum

Berichten: 463

Re: Kans op oplossing "Cijfers en Letters"

Moet je alle 6 getallen gebruiken of mag je met minder uitkomen?
Hoe zit het met de prioriteiten van de bewerkingen: links naar rechts / (meneer) Van Dale (wacht) Op Antwoord / nog iets anders ?
Zijn haakjes toegestaan?

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

Met 3, 4, 9, 10, 50 en 100 kan je inderdaad 781 niet maken.
Net zomin als 734, 758, 786, 842 en 858.

Alle andere getallen zijn mogelijk.

Ik heb geen idee hoe je het zou moeten uitrekenen maar je kunt wel de computer aan het werk zetten.
Het blijkt dat er inderdaad verrassend vaak een oplossing mogelijk is.
Hier 40 willekeurig getrokken getallencombinaties en het aantal mogelijkheden (van de 900) dat te maken is:

Code: Selecteer alles

[25, 50, 3, 10, 10, 3] 729
[50, 100, 1, 7, 5, 3] 862
[50, 25, 3, 4, 3, 6] 851
[25, 50, 5, 3, 8, 3] 849
[25, 75, 9, 1, 1, 9] 537
[100, 75, 6, 4, 9, 1] 872
[50, 75, 9, 5, 2, 2] 883
[100, 50, 3, 10, 7, 5] 884
[75, 25, 5, 7, 9, 1] 881
[25, 75, 2, 2, 9, 2] 683
[100, 25, 9, 1, 2, 5] 888
[50, 75, 10, 8, 8, 1] 801
[25, 50, 8, 7, 4, 2] 895
[25, 100, 6, 3, 7, 10] 899
[25, 100, 8, 3, 8, 4] 861
[25, 100, 5, 1, 10, 2] 825
[100, 75, 5, 4, 1, 6] 804
[50, 25, 1, 1, 6, 2] 594
[25, 75, 10, 7, 2, 3] 886
[25, 75, 4, 1, 1, 1] 266
[25, 100, 5, 6, 3, 6] 870
[50, 75, 6, 6, 10, 4] 792
[100, 50, 9, 6, 4, 4] 867
[50, 75, 10, 3, 9, 4] 896
[25, 75, 6, 3, 2, 6] 863
[100, 25, 3, 2, 1, 5] 881
[75, 100, 3, 6, 8, 6] 879
[75, 25, 5, 8, 9, 4] 900
[25, 100, 3, 4, 4, 5] 827
[50, 25, 9, 6, 9, 2] 879
[50, 100, 3, 5, 9, 9] 875
[50, 75, 9, 3, 4, 9] 855
[100, 50, 6, 5, 8, 2] 891
[50, 25, 5, 4, 3, 7] 891
[100, 50, 10, 10, 10, 1] 356
[100, 50, 6, 2, 4, 7] 890
[50, 100, 5, 6, 10, 9] 880
[75, 50, 1, 1, 5, 5] 509
[50, 100, 2, 9, 4, 4] 840
[50, 25, 2, 8, 1, 10] 890
Als er weinig mogelijkheden zijn zitten er vaak veel enen bij de getrokken getallen.

Uitreaard onder voorbehoud van fouten...

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

RedCat schreef: do 18 nov 2021, 15:14 Moet je alle 6 getallen gebruiken of mag je met minder uitkomen?
Terechte vraag, ik heb steeds alle getallen gebruikt. Als dat niet hoeft zal het aantal mogelijkheden nog wat groter zijn.
RedCat schreef: do 18 nov 2021, 15:14 Hoe zit het met de prioriteiten van de bewerkingen: links naar rechts / (meneer) Van Dale (wacht) Op Antwoord / nog iets anders ?
Zijn haakjes toegestaan?
Ik heb "haakjes" gebruikt. Niet echt, maar ik heb RPN gebruikt, net als bij sommige HP rekenmachines. Dat komt op hetzelfde neer.

Technicus
Berichten: 1.151

Re: Kans op oplossing "Cijfers en Letters"

Xilvo schreef: do 18 nov 2021, 15:15 Met 3, 4, 9, 10, 50 en 100 kan je inderdaad 781 niet maken.
Net zomin als 734, 758, 786, 842 en 858.

Alle andere getallen zijn mogelijk.

Ik heb geen idee hoe je het zou moeten uitrekenen maar je kunt wel de computer aan het werk zetten.
Het blijkt dat er inderdaad verrassend vaak een oplossing mogelijk is.
Hier 40 willekeurig getrokken getallencombinaties en het aantal mogelijkheden (van de 900) dat te maken is:
....
Ha, Nice.
Hoe heb je dit gedaan? met de hand alle mogelijke combinaties van operaties bepaald, en daar de getallen in willekeurige volgorde ingestopt?
Heb je python code die je kan delen?

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

CoenCo schreef: do 18 nov 2021, 15:43 Ha, Nice.
Hoe heb je dit gedaan? met de hand alle mogelijke combinaties van operaties bepaald, en daar de getallen in willekeurige volgorde ingestopt?
Heb je python code die je kan delen?
Alle getallen van 0 tm 1023 in het 4-tallig stelsel gemaakt (5-cijferige getallen).
De nul staat voor optellen, de een voor aftrekken, enz.

Die als RPN-bewerkingen losgelaten op alle mogelijke permutaties van de 5 getrokken getallen (m.b.v. itertools).
Quick-and-dirty, en ongetwijfeld doe ik zaken dubbel.
CoenCo schreef: do 18 nov 2021, 15:43 Heb je python code die je kan delen?

Code: Selecteer alles

import numpy as np
import sys
import itertools as it


np.set_printoptions(threshold=sys.maxsize)

def maakrij():
    g=[25,50,75,100]
    ix0=np.random.randint(4)
    ix1=np.random.randint(4)
    while ix0==ix1:
        ix1=np.random.randint(4)
        
    rij=[g[ix0],g[ix1]]
    for k in range(4):
        rij.append(np.random.randint(10)+1)
    return rij
        

def mogelijk(rij,opl):
    
    for k in range(1023):
        z=np.base_repr(k,base=4,padding=0)
        z='0'*(5-len(z))+z
        r=rij[0]
        for k2 in range(5):
            if z[k2]=='0':
                r=r+rij[k2+1]
            elif z[k2]=='1':
                r=r-rij[k2+1]
            elif z[k2]=='2':
                r=r*rij[k2+1]
            elif z[k2]=='3':
                r=r/rij[k2+1]
        r=abs(r)
        if abs(r-round(r))<1e-8:
            ri=int(r)
            if 99<ri<1000:
                opl[ri-100]=1
    tot=np.sum(opl)
    return opl,tot

sr=[]
for teller in range(200):
    opl=np.zeros(900,np.int32)
    rij=maakrij()
    zit=it.permutations(rij)
    zl=list(zit)
    tel=0
    for z in zl:
        tel+=1
        opl,s=mogelijk(z,opl)
    print(rij,s)
    sr.append(s)

sr=np.array(sr)
gem=np.mean(sr)
stdev=np.std(sr)    
print(gem)
print(stdev)

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

Een steekproef met n=200 geeft voor het gemiddelde aantal mogelijkheden 833 en voor de standaardafwijking 84

Gebruikersavatar
Berichten: 10.557

Re: Kans op oplossing "Cijfers en Letters"

RedCat schreef: do 18 nov 2021, 15:14 Moet je alle 6 getallen gebruiken of mag je met minder uitkomen?
Hoe zit het met de prioriteiten van de bewerkingen: links naar rechts / (meneer) Van Dale (wacht) Op Antwoord / nog iets anders ?
Zijn haakjes toegestaan?
Dat had ik inderdaad niet duidelijk aangegeven. Met minder mag het ook. De bewerkingen worden steeds een voor een gedaan, waarbij je kunt kiezen of en hoe je de tussentijdse resultaten gebruikt. bijvoorbeeld bij 211 als doel en met 1, 2, 3, 4, 25 en 50 als cijfers kun je zeggen:

1 + 2 = 3
3 * 3 = 9
25 + 4 = 29
29 * 9 = 261
261 - 50 = 211

Of, met haakjes opgeschreven (1+2) * 3 * (25+4) - 50 = 211
Cetero censeo Senseo non esse bibendum

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

Een nieuwe steekproef met n=200, waarbij nu niet alle getallen gebruikt hoefden te worden, geeft voor het gemiddelde aantal mogelijkheden 855 (95 %) en voor de standaardafwijking 70.
Dat komt dus mooi overeen met de schatting van Marko in het eerste bericht.

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

Je kunt trouwens beter een klein getal als opdracht krijgen, die zijn blijkbaar vaker te maken dan grotere

Getal Hoe vaak te maken in een steekproef met n=200

Code: Selecteer alles

    100     200  
    101     200  
    102     200  
    103     200  
    104     200  
    105     200  
    106     200  
    107     200  
    108     200  
    109     200  
//
    300     200  
    301     199  
    302     190  
    303     192  
    304     195  
    305     198  
    306     197  
    307     195  
    308     196  
    309     198  
//
    600     200  
    601     193  
    602     191  
    603     191  
    604     195  
    605     197  
    606     190  
    607     190  
    608     192  
    609     194  
//
    990     180  
    991     171  
    992     186  
    993     176  
    994     186  
    995     185  
    996     194  
    997     183  
    998     177  
    999     195

Berichten: 463

Re: Kans op oplossing "Cijfers en Letters"

Xilvo schreef: do 18 nov 2021, 15:54 Quick-and-dirty, en ongetwijfeld doe ik zaken dubbel.
Dirty werk is niet zo'n probleem, maar misschien wel iets te quick: de haakjesuitdrukkingen ontbreken.
Voorbeeld:
rij = [100, 50, 1, 1, 1, 1]:
oplossing (100 + 1 + 1) * (1 + 1) + 50 = 254 ontbreekt.
Zie de aanpassingen/mishandeling van je code hieronder (voorzien van #commentaar):

Code: Selecteer alles

import numpy as np
import sys
import itertools as it

np.set_printoptions(threshold=sys.maxsize)

def maakrij():
    g=[25,50,75,100]
    ix0=np.random.randint(4)
    ix1=np.random.randint(4)
    while ix0==ix1:
        ix1=np.random.randint(4)
    rij=[g[ix0],g[ix1]]
    for k in range(4):
        rij.append(np.random.randint(10)+1)
    rij=[100,50,1,1,1,1]     # nu alleen even naar deze rij kijken
    return rij

def mogelijk(rij,opl):
    for k in range(1024):    # off-by-one error:  1023 -> 1024
        z=np.base_repr(k,base=4,padding=0)
        z='0'*(5-len(z))+z
        r=rij[0]
        for k2 in range(5):
            if z[k2]=='0':
                r=r+rij[k2+1]
            elif z[k2]=='1':
                r=r-rij[k2+1]
            elif z[k2]=='2':
                r=r*rij[k2+1]
            elif z[k2]=='3':
                r=r/rij[k2+1]
        r=abs(r)
        if abs(r-round(r))<1e-8:
            ri=int(r)
            if 99<ri<1000:
                opl[ri-100]=1
    tot=np.sum(opl)
    return opl,tot

sr=[]
for teller in range(1):      #  nu even alleen interesse in slechts 1 rij
    opl=np.zeros(900,np.int32)
    rij=maakrij()
    zit=it.permutations(rij)
    zl=list(zit)
    tel=0
    for z in zl:
        tel+=1
        opl,s=mogelijk(z,opl)
    for h in range(900):      # print alle gevonden getallen
      if opl[h]==1:           #
        print(h+100)          #
    print(rij,s)
    sr.append(s)

sr=np.array(sr)
gem=np.mean(sr)
stdev=np.std(sr)    
print(gem)
print(stdev)


Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

RedCat schreef: do 18 nov 2021, 22:22 Dirty werk is niet zo'n probleem, maar misschien wel iets te quick: de haakjesuitdrukkingen ontbreken.
Voorbeeld:
rij = [100, 50, 1, 1, 1, 1]:
oplossing (100 + 1 + 1) * (1 + 1) + 50 = 254 ontbreekt.
Zie de aanpassingen/mishandeling van je code hieronder (voorzien van #commentaar):
Je hebt gelijk. Je kunt wel 'haakjes' toepassen in RPN maar dan moet je niet pas alle bewerkingen aan het eind toepassen.
Ik ga eens kijken of het zonder al te veel werk goed te krijgen is (zonder dat het onbruikbaar traag wordt).

Die 1023 was inderdaad fout. Een fout zonder consequentie (wanneer deel je 5 keer na elkaar) maar zeker niet zo bedoeld.

Gebruikersavatar
Moderator
Berichten: 9.782

Re: Kans op oplossing "Cijfers en Letters"

Ik denk dat ik nu alle mogelijkheden vind. Alleen wordt er nu (nog veel meer dan eerder) dubbel gedaan.
Als je alleen de zes getallen optelt krijg je altijd hetzelfde resultaat.
Dat doe ik nu voor alle 720 permutaties van de zes getallen en voor 6 verschillende volgordes van push/bewerkings-operaties.

Een steekproef (n=100), geeft nu voor het gemiddelde aantal mogelijkheden 886 (ruim 98 %) en voor de standaardafwijking 27.

Het blijft waar dat kleinere getallen vaker te maken zijn dan grotere.

Code: Selecteer alles

def mogelijk(rij,opl):
    for k in range(1024):
        z=np.base_repr(k,base=4,padding=0)
        z='0'*(5-len(z))+z
        r=rij[0]
        opl=plaats(r,opl)
        sppr=['00000011111','00100100111','00011001101',
              '00011000111','00001110011','00000111101']
        for spp in sppr:
            bt=0
            rt=0
            stack=[]
            for c in spp:
                if c=='0': # push
                    stack.append(rij[rt])
                    rt+=1
                else: # bewerking op laatste twee in stack en terugzetten
                    a1=stack.pop()
                    a2=stack.pop()
                    if z[bt]=='0':
                        r=a1+a2
                    elif z[bt]=='1':
                        r=a1-a2
                    elif z[bt]=='2':
                        r=a1*a2
                    elif z[bt]=='3':
                        if a2!=0: 
                            r=a1/a2
                        else: 
                            r=a1
                    stack.append(r)
                    bt+=1
                    opl=plaats(r,opl)
           
    tot=np.sum(opl)
    return opl,tot

Reageer