8 oggetti 6scatole

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

8 oggetti 6scatole

Messaggio da danielf » 26 dic 2009, 14:30

in quanti modi si possono sistemare otto oggetti distinti in sei scatole diverse sapendo che in ogni scatola deve esserci almeno un oggetto?

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 26 dic 2009, 15:05

Messi i primi 6 oggetti in ciascuna scatola (8!/2! possibilità) dobbiamo scegliere come mettere i rimanenti 2. Ci sono due casi incompatibili:
1. Tutti e due nella stessa scatola (6 possibilità)
2. Ciascuno dei due in una scatola diversa (6*5 possibilità).
Abbiamo però contato più di una volta alcuni casi:
nell'1 con il modo di contare applicato ho contato 3 volte ogni caso (perchè l'ordine con cui gli oggetti vengono messi nella scatola è irrilevante in questo problema);
nel 2 con il modo di contare applicato ho contato 4 volte ogni caso (per lo stesso motivo).
In definitiva le possibilità sono:

$ N=\displaystyle \frac {\frac{8!}{2!}6}{3}+\frac{\frac{8!}{2!}6*5}{4}=191520 $
Ultima modifica di Giulius il 26 dic 2009, 16:09, modificato 1 volta in totale.
Aboliamo il latino nei licei scientifici!

Claudio.
Messaggi: 697
Iscritto il: 29 nov 2009, 21:34

Messaggio da Claudio. » 26 dic 2009, 15:50

Giulius ha scritto:Messi i primi 6 oggetti in ciascuna scatola (8!/2! possibilità) dobbiamo scegliere come mettere i rimanenti 2. Ci sono due casi incompatibili:
1. Tutti e due nella stessa scatola (6 possibilità)
2. Ciascuno dei due in una scatola diversa (6*5 possibilità).
Abbiamo però contato più di una volta alcuni casi:
nell'1 con il modo di contare applicato ho contato 3 volte ogni caso (perchè l'ordine con cui gli oggetti vengono messi nella scatola è irrilevante in questo problema);
nel 2 con il modo di contare applicato ho contato 4 volte ogni caso (per lo stesso motivo).
In definitiva le possibilità sono:

$ N=\displaystyle \frac {\frac{8!}{2!}6}{3}+\frac{\frac{8!}{2!}6*5}{4} $
Non ho capito perchè dividi per 3 e per 4, le due statuette insieme posono essere messe in 6 scatole diverse, quindi moltiplicando per 6 non conti anche l'ordine....e per l'altro la stessa cosa.

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 26 dic 2009, 16:01

Dal testo mi pare di capire che le scatole sono tutte distinte così come gli oggetti.
Chiamo A,B,C,D,E,F le scatole e 1,2,3,4,5,6,7,8 gli oggetti.
Nel primo caso (3 oggetti in una stessa scatola e 1 nelle altre 5 scatole) contavo come distinti ad esempio i casi:
* delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F6 e poi aggiungo la coppia 7,8 nella scatola F -> A1B2C3D4E5F678
** delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F7 e poi aggiungo la coppia 6,8 nella scatola F -> A1B2C3D4E5F768
*** delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F8 e poi aggiungo la coppia 6,7 nella scatola F -> A1B2C3D4E5F867
Ma non mi importa l'ordine con il quale inserisco gli oggetti nella scatola quindi questi tre casi sono equivalenti.
Nel secondo caso (2 oggetti in 2 scatole e un solo oggetto nelle restanti 4) contavo come distinti ad esempio i casi:
* delle 8!/2! scelte per i primi oggetti scelgo A1B2C3D4E5F6 e poi aggiungo la coppia 7,8 nella scatola A e nella B -> A17B28C3D4E5F678
** delle 8!/2! scelte per i primi oggetti scelgo A7B2C3D4E5F6 e poi aggiungo la coppia 1,8 nella scatola A e nella B -> A17B28C3D4E5F678
*** delle 8!/2! scelte per i primi oggetti scelgo A1B8C3D4E5F6 e poi aggiungo la coppia 2,7 nella scatola B e nella A -> A17B28C3D4E5F678
**** delle 8!/2! scelte per i primi oggetti scelgo A7B8C3D4E5F6 e poi aggiungo la coppia 1,2 nella scatola A e nella B -> A17B28C3D4E5F678
Ma anche questi 4 casi sono tutti uguali per lo stesso motivo.
Mi scuso perchè sono terribilmente contorto a spiegare in effetti =) (posto che sia giusto come l'ho risolto...)
Aboliamo il latino nei licei scientifici!

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco » 26 dic 2009, 16:06

Un modo leggermente diverso
distinguiamo subito i 2 casi:
1)3 oggetti che vanno in una stessa scatola
2)2 scatole che hanno 2 oggetti

1)Scegliamo le 5 scatole con 1 oggetto, scegliamo i 5 oggetti fra 8 da mettervi e moltiplichiamo per le possibili permutazioni:
$ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!} $

2)Scegliamo le 4 scatole con 1 oggetto, scegliamo i 4 oggetti fra 8 da mettervi e moltiplichiamo per le possibili permutazioni di questi 4 e moltiplichiamo per i modi in cui possiamo posizionare i restanti 4 in 2 scatole:
$ \displaystyle{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6} $

In totale: $ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!}+{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6}=40320+151200=191520 $
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti


[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]

danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

Messaggio da danielf » 26 dic 2009, 16:15

iademarco ha scritto:
2)Scegliamo le 4 scatole con 1 oggetto, scegliamo i 4 oggetti fra 8 da mettervi e moltiplichiamo per le possibili permutazioni di questi 4 e moltiplichiamo per i modi in cui possiamo posizionare i restanti 4 in 2 scatole:
$ \displaystyle{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6} $

In totale: $ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!}+{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6}=40320+151200=191520 $
non ho solo capito perchè moltiplichi per 6 :oops:

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 26 dic 2009, 17:13

E se fossero 50 scatole e 100 oggetti...
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 26 dic 2009, 17:27

Alur...la differenza con il caso precedente è che non posso più fare la distinzione nei due casi come facevo prima (a meno di non essere masochista e avere tanta voglia di contare). Noto che il problema è analogo a contare le funzioni suriettive da un insieme di 100 oggetti in uno di 50 oggetti. Quindi sapendo che:
le funzioni f:A->B suriettive sono $ \displaystyle n=\sum_{i=0}^{|B|-1}(-1)^i\binom{|B|}{i}(|B|-i)^|^A^| $
Nel nostro caso |B|=50 e |A|=100
(infatti se pongo |B|=6 e |A|=8 la formula restituisce esattamente
$ 6^8-6*5^8+15*4^8-20*3^8+15*2^8-6=191520 $)
Aboliamo il latino nei licei scientifici!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 26 dic 2009, 17:59

Ovviamente è giusto... ma che ne dici di dimostrare quella formuletta ;)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 26 dic 2009, 18:24

dario2994 ha scritto:Ovviamente è giusto... ma che ne dici di dimostrare quella formuletta ;)
ne dico che...non ne ho voglia =P.
Ora sto uscendo quindi vado un po' di fretta: l'idea è considerare le funzioni f:A -> B (|B|<=|A|) ma tali che f(A) sia strettamente un sottinsieme di B. Togliendo dal numero totale di funzioni |B|^|A| il numero di queste funzioni si ha il numero di funzioni suriettive.
Si classificano quindi le funzioni in insiemi C_i in cui l'i-esimo insieme è costituito da tutte e sole le funzioni f che non raggiungono l'i-esimo elemento di B (quindi 0<i<|B|+1). Si deve quindi contare la cardinalità dell'unione di questi insiemi tramite il principio IE. La cardinalità di ogni I_i è data da (|B|-1)^|A|, la cardinalità dell'intersezione a due a due degli I_i è (|B|-2)^|A| e quella dell'intersezioni a i a i (|B|-i)^|A|. Applicando IE e svolgendo i conti dovrebbe saltare fuori proprio quella formula....the details of the proof are left to the reader :D
Aboliamo il latino nei licei scientifici!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 26 dic 2009, 20:53

Perfetto :)
Giusto per completezza (anche se devo ammettere che è abbastanza chiara anche la sua proto-dimostrazione) ecco un link in Italiano in cui è presente la dimostrazione:
http://www.silsismi.unimi.it/SILSISMI/I ... toria1.pdf
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco » 26 dic 2009, 21:08

danielf ha scritto:
iademarco ha scritto:


In totale: $ \displaystyle{6 \choose 5}\cdot{8 \choose 5}\cdot{5!}+{6 \choose 4}\cdot{8 \choose 4}\cdot{4!}\cdot{6}=40320+151200=191520 $
non ho solo capito perchè moltiplichi per 6 :oops:
moltiplico per i modi in cui possiamo posizionare i restanti 4 oggetti in 2 scatole, mettendone 2 in ogni scatola
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti


[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]

Rispondi