Con tutte le cifre da 1 a 9 prese una sola volta possono essere scritti 9! numeri diversi.
Prendendone uno a caso, qual è la probabilità che sia divisibile per 11?
www.diophante.fr
G1926 ***
Divisibilità aleatoria
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Divisibilità aleatoria
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Divisibilità aleatoria
Il criterio di divisibilità per 11 ci dice che la differenza tra la somma delle cifre in posizione dispari e la somma di quelle in posizione pari deve essere multipla di 11
Su 9 cifre abbiamo 5 posizioni dispari e 4 pari, la diffenza maggiore è (5+6+7+8+9)-(1+2+3+4)=25 e la minore (1+2+3+4+5)-(6+7+8+9)=-15
in questo range di 41 possibili risultati solo 4 sono multipli di 11 (-11, 0, 11, 22)
Quindi grossomodo la probabilità è vicina 4/41 = 9,75% (reale è 11/126 = 8,73%)
Ora penso a come ricavarlo algebricamente
Su 9 cifre abbiamo 5 posizioni dispari e 4 pari, la diffenza maggiore è (5+6+7+8+9)-(1+2+3+4)=25 e la minore (1+2+3+4+5)-(6+7+8+9)=-15
in questo range di 41 possibili risultati solo 4 sono multipli di 11 (-11, 0, 11, 22)
Quindi grossomodo la probabilità è vicina 4/41 = 9,75% (reale è 11/126 = 8,73%)
Ora penso a come ricavarlo algebricamente
[Sergio] / $17$
Re: Divisibilità aleatoria
In realtà le differenze possono essere solo dispari, quindi 2/21 (12/126) è un stima più attendibile.
Per il calcolo esatto consideriamo che le uniche due possibilità sono -11 e 11, quindi 17-28 e 28-17.
Nel primo caso, per il secondo gruppo ci sono solo 2 combinazioni che danno somma 28: {4, 7, 8, 9} e {5, 6, 8, 9}, ognuna delle quali ha 4! permutazioni e per ogni permutazione il primo gruppo ha 5! permutazioni.
Totale 2 x 4! x 5!
Nel secondo caso le combinazioni che danno somma 17 sono 9: {1, 2, 5, 9}, {1, 2, 6, 8}, {1, 3, 4, 9}, {1, 3, 5, 8}, {1, 3, 6, 7}, {1, 4, 5, 7}, {2, 3, 4, 8}, {2, 3, 5, 7}, {2, 4, 5, 6}
Quindi analogamente: 9 x 4! x 5! permutazioni
La probabilità è $\displaystyle \frac{11 \cdot 4! \cdot 5!}{9!}=\frac{11}{126}$
Per il calcolo esatto consideriamo che le uniche due possibilità sono -11 e 11, quindi 17-28 e 28-17.
Nel primo caso, per il secondo gruppo ci sono solo 2 combinazioni che danno somma 28: {4, 7, 8, 9} e {5, 6, 8, 9}, ognuna delle quali ha 4! permutazioni e per ogni permutazione il primo gruppo ha 5! permutazioni.
Totale 2 x 4! x 5!
Nel secondo caso le combinazioni che danno somma 17 sono 9: {1, 2, 5, 9}, {1, 2, 6, 8}, {1, 3, 4, 9}, {1, 3, 5, 8}, {1, 3, 6, 7}, {1, 4, 5, 7}, {2, 3, 4, 8}, {2, 3, 5, 7}, {2, 4, 5, 6}
Quindi analogamente: 9 x 4! x 5! permutazioni
La probabilità è $\displaystyle \frac{11 \cdot 4! \cdot 5!}{9!}=\frac{11}{126}$
[Sergio] / $17$
Re: Divisibilità aleatoria
Come sempre sei velocissimo ... io nemmeno avevo cominciato a ragionarci

A occhio mi sembra giusto; magari si può fare un "hard check" con decimal basic; 9! combinazioni non sono un'infinità ...
Si tratta, come quasi sempre, di un problema tradotto dal sito francese www.diophante.fr che pubblica i problemi a inizio mese e le risposte ricevute il mese successivo.
Se vuoi, puoi inviare la soluzione ai transalpini utilizzando il link presente nella pagina.
Però bisogna tradurla in francese

ciao
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Divisibilità aleatoria
Fatta la verifica con python, il risultato è corretto
Che poi, a ben vedere, la probabilità che un numero preso a caso da un insieme abbastanza grande ed eterogeneo sia divisibile per 11 (e in generale per qualsiasi numero primo) è 1/11 (11/121)
Codice: Seleziona tutto
from itertools import permutations as perms
def fact(x):
if x == 1: return 1
else: return fact(x-1)*x
i = list(range(1,10))
q = 0
for p in perms(i,9):
pj = 0
for j in range(0,9,2): pj += p[j]
pk = 0
for k in range(1,8,2): pk += p[k]
if (pj-pk)%11 == 0: q += 1
print(q, q/fact(9))
[Sergio] / $17$
Re: Divisibilità aleatoria
Si, anche con Decimal Basic la routine conferma la percentuale già individuata, utilizzando un criterio di costruzione casuale delle combinazioni di 9 numeri e di conteggio di quelle divisibili per 11. Naturalmente la percentuale cercata tende a stabilizzarsi di più aumentando il ciclo di ripetizione degli eventi, ma cresce anche l'attesa del risultato.
Ad esempio, con 10 milioni di combinazioni casuali generate, quelle divisibili per 11 sono risultate sull'ordine del 8,73026 per cento, ovvero circa 8,73 %
Altro esempio : generazione casuale di combinazioni valide in quantità pari a 100 volte il fattoriale di 9, con risultato pari ad 8,735 % relativamente alle combinazioni intercettate, divisibili per 11.
^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^
Infine, una routine "stupida", ma comunque precisa, conferma il risultato annunciato magistralmente da Quelo, ovvero:
.
$31680*100/362880 = 8,\overline{730158}$
in cui 362880 sono le permutazioni dei 9 numeri diversi e 31680 tutte le permutazioni divisibili per 11.
Segue la elementare routine utilizzata (una volta lanciata, meglio dedicarsi ad altro) :
LET tot=0 !'per conteggio permutazioni esaminate
LET div=0 !'per conteggio permutazioni divisibili per 11
DIM a(9) !' per esame permutazioni
FOR m1=1 TO 9
FOR m2=1 TO 9
FOR m3=1 TO 9
FOR m4=1 TO 9
FOR m5=1 TO 9
FOR m6=1 TO 9
FOR m7=1 TO 9
FOR m8=1 TO 9
FOR m9=1 TO 9
LET a(1)=m1
LET a(2)=m2
LET a(3)=m3
LET a(4)=m4
LET a(5)=m5
LET a(6)=m6
LET a(7)=m7
LET a(8)=m8
LET a(9)=m9
FOR n=2 TO 9
FOR p=1 TO n-1
IF a(n)=a(p) THEN GOTO 10
NEXT P
NEXT N
LET tot=tot+1
LET x=m1*10^8+m2*10^7+m3*10^6+m4*10^5+m5*10^4+m6*10^3+m7*10^2+m8*10+m9
IF MOD(x,11)=0 THEN LET div=div+1
10 NEXT m9
NEXT m8
NEXT m7
NEXT m6
NEXT m5
NEXT m4
NEXT m3
NEXT m2
NEXT m1
PRINT "Totale permutazioni esaminate =";tot
PRINT "Totale permutazioni divisibili per 11 =";div
PRINT ""Probabilità percentuale, affinché una permutazione presa a caso sia divisibile per 11 =";100*div/tot
END
Ad esempio, con 10 milioni di combinazioni casuali generate, quelle divisibili per 11 sono risultate sull'ordine del 8,73026 per cento, ovvero circa 8,73 %
Altro esempio : generazione casuale di combinazioni valide in quantità pari a 100 volte il fattoriale di 9, con risultato pari ad 8,735 % relativamente alle combinazioni intercettate, divisibili per 11.
^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^
Infine, una routine "stupida", ma comunque precisa, conferma il risultato annunciato magistralmente da Quelo, ovvero:
.
$31680*100/362880 = 8,\overline{730158}$
in cui 362880 sono le permutazioni dei 9 numeri diversi e 31680 tutte le permutazioni divisibili per 11.
Segue la elementare routine utilizzata (una volta lanciata, meglio dedicarsi ad altro) :
LET tot=0 !'per conteggio permutazioni esaminate
LET div=0 !'per conteggio permutazioni divisibili per 11
DIM a(9) !' per esame permutazioni
FOR m1=1 TO 9
FOR m2=1 TO 9
FOR m3=1 TO 9
FOR m4=1 TO 9
FOR m5=1 TO 9
FOR m6=1 TO 9
FOR m7=1 TO 9
FOR m8=1 TO 9
FOR m9=1 TO 9
LET a(1)=m1
LET a(2)=m2
LET a(3)=m3
LET a(4)=m4
LET a(5)=m5
LET a(6)=m6
LET a(7)=m7
LET a(8)=m8
LET a(9)=m9
FOR n=2 TO 9
FOR p=1 TO n-1
IF a(n)=a(p) THEN GOTO 10
NEXT P
NEXT N
LET tot=tot+1
LET x=m1*10^8+m2*10^7+m3*10^6+m4*10^5+m5*10^4+m6*10^3+m7*10^2+m8*10+m9
IF MOD(x,11)=0 THEN LET div=div+1
10 NEXT m9
NEXT m8
NEXT m7
NEXT m6
NEXT m5
NEXT m4
NEXT m3
NEXT m2
NEXT m1
PRINT "Totale permutazioni esaminate =";tot
PRINT "Totale permutazioni divisibili per 11 =";div
PRINT ""Probabilità percentuale, affinché una permutazione presa a caso sia divisibile per 11 =";100*div/tot
END
_________________
$\text { }$ciao
ciao
E' la somma che fa il totale (Totò)
$\text { }$ciao
E' la somma che fa il totale (Totò)
Re: Divisibilità aleatoria
Tra gli esempi di Decimal Basic c'è una routine per le permutazioni (PERMUTAT.BAS) che possiamo riadattare al nostro scopo
Codice: Seleziona tutto
DECLARE EXTERNAL SUB perm
DECLARE EXTERNAL FUNCTION fact
LET n = 9
DIM a(n)
MAT a=ZER(n)
FOR i=1 TO n
LET a(i)=i
NEXT i
LET e = 0
CALL perm(a,1,e)
PRINT "probabilità = "; e; "/"; fact(n)
END
EXTERNAL SUB perm(a(),n,e)
LET m=UBOUND(a)
IF n=m THEN
LET d = 0
FOR k = 1 TO 9
IF MOD(k,2) = 1 THEN
LET d = d + a(k)
ELSE
LET d = d - a(k)
END IF
NEXT k
IF MOD(d,11) = 0 THEN LET e = e + 1
ELSE
FOR i=n TO m
LET t=a(i)
FOR j=i-1 TO n STEP -1
LET a(j+1)=a(j)
NEXT j
LET a(n)=t
CALL perm(a,n+1,e)
LET t=a(n)
FOR j=n TO i-1
LET a(j)=a(j+1)
NEXT j
LET a(i)=t
NEXT i
END IF
END SUB
EXTERNAL FUNCTION fact(n)
IF n=1 THEN
LET fact=1
ELSE
LET fact=n*fact(n-1)
END IF
END FUNCTION
[Sergio] / $17$