Kans op oplossing "Cijfers en Letters"
- Berichten: 10.564
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?
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
- Berichten: 7.463
Re: Kans op oplossing "Cijfers en Letters"
Heb je al een voorbeeld waarbij er zeker geen oplossing bestaat?
- Berichten: 10.564
Re: Kans op oplossing "Cijfers en Letters"
Hierbij een voorbeeld:
Doel: 781
Getallen: 3, 4, 9, 10, 50 en 100
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?
Hoe zit het met de prioriteiten van de bewerkingen: links naar rechts / (meneer) Van Dale (wacht) Op Antwoord / nog iets anders ?
Zijn haakjes toegestaan?
- Moderator
- Berichten: 9.995
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:
Als er weinig mogelijkheden zijn zitten er vaak veel enen bij de getrokken getallen.
Uitreaard onder voorbehoud van fouten...
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
Uitreaard onder voorbehoud van fouten...
- Moderator
- Berichten: 9.995
Re: Kans op oplossing "Cijfers en Letters"
Terechte vraag, ik heb steeds alle getallen gebruikt. Als dat niet hoeft zal het aantal mogelijkheden nog wat groter zijn.
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.167
Re: Kans op oplossing "Cijfers en Letters"
Ha, Nice.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:
....
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?
- Moderator
- Berichten: 9.995
Re: Kans op oplossing "Cijfers en Letters"
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.
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)
- Moderator
- Berichten: 9.995
Re: Kans op oplossing "Cijfers en Letters"
Een steekproef met n=200 geeft voor het gemiddelde aantal mogelijkheden 833 en voor de standaardafwijking 84
- Berichten: 10.564
Re: Kans op oplossing "Cijfers en Letters"
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
- Moderator
- Berichten: 9.995
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.
Dat komt dus mooi overeen met de schatting van Marko in het eerste bericht.
- Moderator
- Berichten: 9.995
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
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"
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)
- Moderator
- Berichten: 9.995
Re: Kans op oplossing "Cijfers en Letters"
Je hebt gelijk. Je kunt wel 'haakjes' toepassen in RPN maar dan moet je niet pas alle bewerkingen aan het eind toepassen.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):
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.
- Moderator
- Berichten: 9.995
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.
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