Una scatola dentro l'altra

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
franco
Livello 7
Livello 7
Messaggi: 906
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Una scatola dentro l'altra

Messaggio da franco » gio apr 07, 2016 4:56 pm

In un'urna sono contenuti 2016 bussolotti numerati da 1 a 2016.
Ne estraggo 3 e poi altri 3 (senza aver rimesso nell'urna i primi 3).
Consideriamo a questo punto due scatole a forma di parallelepipedo con le dimensioni (in mm) pari ai numeri di ogni terna.

:?: Qual è la probabilità che la prima possa stare dentro la seconda? (mantenendo sempre i lati paralleli)
:?: Qual è la probabilità che una scatola possa stare dentro l'altra?
:?: Come variano le risposte se prima di estrarre la seconda terna rimetto nell'urna i tre bussolotti estratti in precedenza?
:?: Come variano le risposte se ogni singolo bussolotto è rimesso nell'urna prima di estrarre il successivo?

ciao


Franco


G.187
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

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Una scatola dentro l'altra

Messaggio da Pasquale » sab apr 09, 2016 1:36 am

Qui mi son buttato sulle simulazioni per non perdere memoria del linguaggio; quindi i risultati sono approssimati:

1° quesito: sul 25%
2° quesito: sul 50%
3° quesito: ributtando dentro i primi 3 bussolotti, i precedenti risultati diminuiscono di un tantino
4° quesito: non l'ho simulato, ma amche per questo caso penso che i risultati non si discostino di molto dai precedenti, considerato che 6 numeri estratti su 2016 sono pochini.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 926
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Una scatola dentro l'altra

Messaggio da Gianfranco » dom apr 10, 2016 10:37 pm

Questo problema è troppo difficile per me, ma scrivo ugualmente per dire che mi piace e per ringraziare Franco e Pasquale per una prima risposta.
A una prima lettura mi aveva colpito la difficoltà combinatoria di stabilire quando una scatola "sta dentro un'altra".
Poi ho notato la facilitazione che i lati si mantengono paralleli.
Qual è la probabilità che la prima possa stare dentro la seconda? (mantenendo sempre i lati paralleli)
Mah, forse proverò a risolvere i casi di scatole a una e due dimensioni...
Pace e bene a tutti.
Gianfranco

franco
Livello 7
Livello 7
Messaggi: 906
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Una scatola dentro l'altra

Messaggio da franco » lun apr 11, 2016 6:09 am

In realtà, nel sito francese dove ho trovato il problema veniva posto solo lo primo quesito.
Ho aggiunto gli altri perché mi sembrava "troppo facile". :mrgreen:

Mi viene il dubbio di aver preso una cantonata ... :?

Lascio comunque ancora un po' di tempo prima di postare quella che credo sia la soluzione.

Ciao

Franco
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

gnugnu
Livello 4
Livello 4
Messaggi: 121
Iscritto il: dom set 07, 2014 1:00 pm

Re: Una scatola dentro l'altra

Messaggio da gnugnu » lun apr 11, 2016 12:17 pm

Direi che il $ 2016 $ possa essere sostituito da qualsiasi numero maggiore di cinque.
I risultati di Pasquale sono esatti: $ 25 \% $ e $ 50 \% $ per il primo e secondo quesito. Si trovano rapidamente 'contando' quante disposizioni dei sei estratti soddisfano la condizione posta. In generali estraendo $ 2n $ numeri da un'urna che ne contiene $ m>2n $, diversi fra loro, la probabilità che fra gli ultimi $ n $ ed i primi $ n $ si possano formare $ n $ coppie, nelle quali il primo sia maggiore del secondo è $ \frac 1 {n+1} $.
Per il terzo e quarto, come ha già osservato Pasquale, la differenza è minima e, a monte, bisognerebbe almeno stabilire se una scatola, con una dimensione esattamente uguale alla corrispondente dell'altra, possa, o meno, 'starci' dentro.
Ciao

franco
Livello 7
Livello 7
Messaggi: 906
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Una scatola dentro l'altra

Messaggio da franco » lun apr 11, 2016 10:05 pm

Sono perplesso.

Rispondete entrambi 25% al primo quesito.
E Pasquale ha anche fatto le simulazioni ...

Io invece avrei detto 12,5%.

Pensavo che se A>B>C è la prima terzina e D>E>F la seconda, la condizione di cui al quesito si verifica quando sono contemporaneamente A<D .and. B<E .and. C<F
(la scrittura magari non è correttissima ma spero si capisca il concetto).
Poiché ognuna delle singole condizioni ha una probabilità pari a 1/2 e le condizioni sono indipendenti, la probabilità complessiva dovrebbe essere (1/2)^3 = 1/8 = 12,5%

Dove sbaglio :? ?
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

franco
Livello 7
Livello 7
Messaggi: 906
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Una scatola dentro l'altra

Messaggio da franco » lun apr 11, 2016 10:13 pm

...

del resto, ragionando come suggerisce Gianfranco, prima su 1 o 2 dimensioni mi sembra il mio ragionamento fili.

Nel caso di un segmento (1D), evidentemente A>B e A<B sono equiprobabili quindi il risultato è 50%

Nel caso dei rettangoli (2D) con A>B prima coppia di dimensioni e C>D seconda coppia, le quattro possibilità (tutte equiprobabili sono)
A>C e B>D negativo
A<C e B>D negativo
A>C e B<D negativo
A<C e B<D positivo ---> 25%

Ancora ... dove sbaglio???
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

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Una scatola dentro l'altra

Messaggio da Pasquale » mar apr 12, 2016 4:30 am

Per meglio meditare sulla questione e per un confronto dei risultati, riporto di seguito la simulazione del 1° quesito così come l'ho concepita, peraltro conforme a quanto indicato da Franco, salvo il fatto che ho inteso la superficie delle scatole di spessore adimensionale, il che non comporta significative differenze ( se non piace, nell'algoritmo è sempre possibile sostituire <= con un semplice < ).

'Primo caso con i primi 3 estratti che non vengono ributtati nell'urna

DIM a(2016)
DIM b(6) ' contiene gli estratti (3 nelle prime posizioni e 3 nelle ultime); ho evitato 2 matrici da 3 per ridurre un tantino i tempi di esecuzione

RANDOMIZE

LET cont=0
FOR z=1 TO 500000 'reiterazioni: bisogna attendere un po' per il risultato, trattandosi di codice in Decimal Basic

MAT a=ZER
FOR m=1 TO 6 'estrai i numeri evitando che vi siano doppioni
10 LET x=1+INT(RND*2016)
IF a(x) = 0 THEN ' il numero è valido se già non è stato estratto
LET a(x)=1
LET b(m)=x
ELSE
GOTO 10
END IF
NEXT M

'Come 1° bussolotto s'intende b(da 1 a 3) e come 2° b(da 4 a 6)
'metti in ordine crescente i numeri dei 2 bussolotti in modo separato
FOR m=1 TO 2
FOR n= m+1 TO 3
IF b(n)<b(m)THEN swap b(n),b(m)
NEXT N
NEXT M
FOR m=4 TO 5
FOR n= m+1 TO 6
IF b(n)<b(m)THEN swap b(n),b(m)
NEXT N
NEXT M

'confronta i numeri del 1° con quelli del 2°
IF b(1)<=b(4) AND b(2)<=b(5) AND b(3)<=b(6) THEN LET cont=cont+1

NEXT Z

LET Pr = 100*cont/500000
PRINT "probabilità 1^ scatola nella seconda = "; pr;"%"
END
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

gnugnu
Livello 4
Livello 4
Messaggi: 121
Iscritto il: dom set 07, 2014 1:00 pm

Re: Una scatola dentro l'altra

Messaggio da gnugnu » mar apr 12, 2016 10:07 am

@franco:
questo è il procedimento che ho seguito.
Dall'urna, che contiene numeri diversi fra loro ed in quantità sufficiente per soddisfare la richiesta estraggo, procedendo come ha suggerito Gianfranco.
(a) Due numeri A e B, non importa quanto grandi siano, supponiamoli semplicemente in ordine crescente A < B. Questi due numeri dovranno essere assegnati alle le due 'scatole', se nella spartizione la prima 'scatola' si aggiudica A, potrà essere inserita nella seconda. Probabilità che questo accada $ 1 / 2 $.

(b) Quattro numeri A, B, C, e D (sempre in ordine crescente). Ad ogni 'scatola' vengono assegnati due di questi numeri. Affinché la prima possa essere inserita nella seconda fra le sei coppie possibili AB, AC, AD, BC, BD, CD (equiprobabili); dovrà ottenere una delle prime due. Probabilità che questo avvenga $ 1/3 $.

(c) Sei numeri A, B, C, D, E, F. Tre di questi a ciascuna scatola. Per permettere l'inserimento, fra le 20 possibili terne equiprobabili, alla prima dovrà andare una delle seguenti: ABC, ABD, ABE, ACD, ACE. Probabilità di questo evento $ 5/20= 1/4 $.

Volendo generalizzare per ottenere una formulazione adatta ad uno spazio n-dimensionale, indicando con $ a_j $ con $ 0<j<2n+1 $ i numeri estratti, e con $ b_i $ $ 0<i<n+1 $ quelli assegnati alla prima scatola. Dovrà essere per ogni $ i $, $ b_i<a_{2i} $; e la probabilità che questo avvenga è $ \frac 1 2 \frac 2 3 ... \frac n {n+1}= \frac1 {n+1} $.

La differenza rispetto a quanto proponi, credo risieda nella divisione per coppie, che implicitamente esclude la possibilità di assegnare alla prima scatola otre ad A, anche B e così via, riducendo di conseguenza la probabilità di ottenere misure adeguate all'inserimento.
Ciao

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 926
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Una scatola dentro l'altra

Messaggio da Gianfranco » mar apr 12, 2016 12:40 pm

Ohh!
Dopo aver letto il ragionamento di Gnugnu, questo problema mi è apparso molto più semplice di quello che mi era sembrato all'inizio.
Interessante il fatto che la probabilità è indipendente dal numero di bussolotti.
Grazie a tutti!
Pasquale, ho provato il tuo programma e mi dà i risultati attesi, anche riducendo il numero dei bussoloti.
Tuttavia il modello non mi convince del tutto:
mi sembra che il programma NON simuli una "ESTRAZIONE DI 6 NUMERI SENZA REINSERIMENTO" ma piuttosto una "ESTRAZIONE CON REINSERIMENTO CON EVENTUALI RIPETIZIONI FINO A OTTENERE 6 NUMERI TUTTI DIVERSI".
Non so se le due cose sono equivalenti.
Pace e bene a tutti.
Gianfranco

franco
Livello 7
Livello 7
Messaggi: 906
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Una scatola dentro l'altra

Messaggio da franco » mar apr 12, 2016 7:19 pm

gnugnu ha scritto:@franco:
questo è il procedimento che ho seguito.
.....
Ciao
La spiegazione è chiarissima, ti ringrazio.

Siccome poi sono come Tommaso :) ho fatto anch'io un programmino di simulazione sul quale mi vorrei confrontare con Pasquale:

Dato non ho installato Decimal Basic e sono più pratico di Visual Basic, ho scritto una routine su Excel.
A occhio mi sembra corretta ma ci dev'essere qualche problema perché, nonostante le 500.000 iterazioni e il fatto che l'abbia fatta girare molte volte, mi da' sempre un risultato appena superiore al 22% :shock:

Che te ne pare?

Sub Calcola()

Dim Numeri(6) As Integer
Dim Scatola1(3) As Integer
Dim Scatola2(3) As Integer
NumeroRipetizioni = 500000
Randomize

For k = 1 To NumeroRipetizioni

'estrai i 6 numeri tutti diversi
Numeri(1) = Int(Rnd() * 2016 + 1)
For i = 2 To 6
Numeri(i) = Int(Rnd() * 2016 + 1)
For j = 1 To i - 1
If (Numeri(i) = Numeri(j)) Then
j = i - 1
i = i - 1
End If
Next j
Next i

'metti in ordine le 3 terzine
Scatola1(1) = Numeri(1)
If (Numeri(2) > Numeri(1)) Then
Scatola1(2) = Scatola1(1)
Scatola1(1) = Numeri(2)
Else
Scatola1(2) = Numeri(2)
End If
If (Numeri(3) > Numeri(1)) Then
Scatola1(3) = Scatola1(2)
Scatola1(2) = Scatola1(1)
Scatola1(1) = Numeri(3)
Else
If (Numeri(3) > Numeri(2)) Then
Scatola1(3) = Scatola1(2)
Scatola1(2) = Numeri(3)
Else
Scatola1(3) = Numeri(3)
End If
End If
Scatola2(1) = Numeri(4)
If (Numeri(5) > Numeri(4)) Then
Scatola2(2) = Scatola2(1)
Scatola2(1) = Numeri(5)
Else
Scatola2(2) = Numeri(5)
End If
If (Numeri(6) > Numeri(4)) Then
Scatola2(3) = Scatola2(2)
Scatola2(2) = Scatola2(1)
Scatola2(1) = Numeri(6)
Else
If (Numeri(6) > Numeri(5)) Then
Scatola2(3) = Scatola2(2)
Scatola2(2) = Numeri(6)
Else
Scatola2(3) = Numeri(6)
End If
End If

'verifica; check=1 se la scatola 2 contiene la scatola 1, altrimenti check=0
check = 1
For i = 1 To 3
If Scatola1(i) > Scatola2(i) Then
check = 0
End If
Next i

'metti a totale il risultato della verifica e poi parti con un'altra iterazione
totale = totale + check
Next k

'stampa il risultato finale nella cella A1 del foglio Excel
risultato = totale / NumeroRipetizioni
Cells(1, 1) = risultato

End Sub


ciao

Franco
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

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Una scatola dentro l'altra

Messaggio da Pasquale » mer apr 13, 2016 3:05 am

La scelta dell'algoritmo così come l'ho postato e sperimentato, è stata determinata dall'esigenza di ridurre al minimo i comandi, per velocizzare l'esecuzione dei vari comandi in rapporto al tipo di linguaggio non eccessivamente veloce, pur rispettando i termini del problema di seguito riportati (il 1°....gli altri derivano da questo con le dovute variazioni):

----------------------------------------------------------------------------------
In un'urna sono contenuti 2016 bussolotti numerati da 1 a 2016.
Ne estraggo 3 e poi altri 3 (senza aver rimesso nell'urna i primi 3).
----------------------------------------------------------------------------------
Quindi ho immaginato un'urna contenente 2016 numeri [ matrice a(2016)];
ho creato poi un contenitore da 6 diviso in 2 parti (da 1 a 3 e da 4 a 6) [matrice b(6)]
(potrebbe rappresentare un tavolo sul quale vado ad appoggiare a sinistra i primi 3 numeri estratti ed a destra i secondi 3)
Quindi estraggo i 6 numeri e li sistemo in sequenza nello stesso ordine casuale con cui vengono estratti, tenendo presente che poi i primi 3 rappresenteranno le misure della scatola che dovrà entrare nella seconda, alla quale saranno assegnate le misure rappresentate dai secondi 3 numeri (mi dilungo per essere quanto più chiaro possibile anche nei cofronti di qualche ragazzo appassionato che ci legge).
Metto in ordine crescente i primi tre numeri e così proseguo per i secondi tre, perché poi esguirò il confronto fra i lati più corti, fra quelli medi e fra quelli più lunghi, assumendo che una scatola entra nell'altra solo se il lato corto dell'una è <= del lato corto dell' altra e così dicasi per i lati di misura media e poi per i restanti più lunghi. Conteggio i casi favorevoli su 500.000 reiterazioni e ne traggo la percentuale.
Una volta lavoravo in Quick Basic, poi mi convertii al Decimal, grazie ai buoni uffici di Gianfranco, ma in questo periodo di inattività qualcosa era già finita nel dimenticatoio.
Quanto sopra si riferisce all'intento di aderire allo spirito del quesito da cui consegue materialmente la traduzione in Decimal Basic, così come l'ho intesa.
Penso che simuli abbastanza quanto richesto:
per ottenere l'estrazione di 6 numeri diversi di varie dimensioni tratte a caso dall'urna dei 2016, ho utilizzato il randomizzatore dello stesso Decimal (con i limiti che ogni randomizzatore può avere, ma accettabili per questo problema); ogni numero estratto viene smarcato sulla matrice ( LET a(x)=1)], per evitare che possa essere ripetuto (cosa casualmente inevitabile); per cui se il randomizzatore dovesse scegliere un numero già smarcato, cioè già estratto, il programma gli dà l'alt e gli dice di riprovare, perché significherebbe la presenza nell'urna di due numeri uguali che non dovevano esserci; questo significa perdere del tempo, ma non ho visto altra soluzione e d'altra parte l'ventualità sarebbe rara, dovendosi estrarre solo 6 numeri su 2016. Quanto sopra si traduce nel comando ELSE GOTO 10.
IL resto dell'algoritmo mette in ordine crescente separatamente i primi 3 numeri e poi i secondi 3 per il confronto di cui ho detto prima, che segue all'ordinamento.
Riducendo le reiterazioni a 100.000 ed anche meno, l'esecuzione naturalmente si velocizza, ma aumenta l'imprecisione, anche se il programma dà egualmente un'idea sulla tendenza.
Tutto quanto sopra a beneficio del dubbio di Gianfranco, al quale naturalmente sarei grato se avesse da proporre un'alternativa alla mia soluzione.
Per quanto concerne la richiesta di Franco, direi che il suo algoritmo differisce solo nell'ordinamento delle terne, realizzato in senso decrescente.
Non saprei come mai il suo risultato di discosta dal mio, non conoscendo le caratteristiche di Excel, specie per quanto riguarda il randomizzatore. Potrebbe essere che non sia molto efficiente? Ogni macchina random genera una crta quantità di numeri casuali ed al termine li ripete se la routine non ha terminato il suo lavoro. Poniamo che Excel generi meno numeri random di Decimal Basic, questo potrebbe giustificare la differenza, perché comunque una routine random non è una formula matematica. Tutto è relativo e volendo, sforzandoci un po' possiamo dire che 22 è più vicino a 25 rispetto a 16 o 64. :)
Suggerirei, per una verifica, di provare a cambiare il numero delle reiterazioni, diminuendole e aumentandole gradualmente, con la speranza di trarne qualche conclusione.
Magari si potrebbe provare anche a diminuire la quantità dei numeri nell'urna (300 in vece di 2016), sempre allo scopo di testare l'efficienza del randomizzatore e per vedere se si notano miglioramenti.
Quanto tempo impiega Excel per sfornare il risultato? Il 22% è abbastanza stabile, oppure soffre di una certa variabilità non del tutto trascurabile?
Magari si potrebbe provare anche a diminuire la quantità dei numeri nell'urna (300 in vece di 2016), sempre allo scopo di testare l'efficienza del randomizzatore e per vedere se si notano miglioramenti.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

gnugnu
Livello 4
Livello 4
Messaggi: 121
Iscritto il: dom set 07, 2014 1:00 pm

Re: Una scatola dentro l'altra

Messaggio da gnugnu » mer apr 13, 2016 9:22 am

@franco:
penso di aver scovato la ragione dei risultati diversi ottenuti con la tua simulazione. Nell'ordinare le due terne, la condizione del secondo "If" confronta due valori di "Numeri" (il cui contenuto non è stato, eventualmente, modificato a seguito del primo controllo). Dovrebbe invece confrontare, ad esempio per la prima terzina, "Numeri(3) con Scatola1(1)". Lo stesso dicasi per la condizione successiva.
Ciao

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Una scatola dentro l'altra

Messaggio da Pasquale » mer apr 13, 2016 3:32 pm

Si è vero. Ci sono dei confronti fra Numeri e Numeri, anzicché fra Numeri e Scatole. nel primo confronto è ininfluente, ma dopo si possono generare degli errori di piazzamento.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Rispondi