Staffetta combinatoria.

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Staffetta combinatoria.

Messaggio da jordan » 03 lug 2009, 01:36

Iniziamo una staffetta anche qui, perchè no? come nella sezione di algebra e in quella di teoria dei numeri; proporrei di nuovo agli autori dei problemi di postare la loro soluzione qualora il problema non venisse risolto entro circa una settimana..

Problema 1.
Siano dati $ n $ dadi e si definisca $ p_{i,j} $ la probabilità che lanciando il dado $ i $ esca la faccia $ j $. Sia $ S_x $ la probabilità che, lanciando insieme tutti questi dadi, la somma delle facce sia esattamente $ x $. Mostrare che esistono due interi $ a $ e $ b $ tali che $ n \le a < b \le 6n $ e $ S_a \neq S_b $.

Note. 1) ogni dado ha 6 facce :lol: 2) I $ p_{i,j} $ sono fissati ma non è detto che siano tutti $ \frac{1}{6} $, per cui il problema non è (necessariamente) banale :o 3) A conferma che non è banale posso dire che proviene da una olimpiade iraniana..
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 12 lug 2009, 02:00

Hint: considerare i polinomi $ \displaystyle q_i(x)=\sum_{i=1}^6{p_{i,j}x^j} $..
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 30 mar 2010, 22:18

Soluzione problema 1. Poniamo che per assurdo $ S_i=S_{i+1} $ per ogni $ i \in\mathbb{Z}\cap [n,6n) $, allora $ \displaystyle f(x):=\prod_{1\le i\le n}{q_i(x)}=S_nx^n\cdot \frac{x^{5n+1}-1}{x-1} $, dove il coefficiente di $ f(x) $ di grado $ i \in \mathbb{Z}\cap [n,6n] $ risulta esattamente $ S_i $. Dato che $ S_n=S_{n+1}=\ldots=S_{6n}>0 $ allora necessariamente $ p_{1,6}>0 $. D'altra parte, dato che $ f(\cdot) $, oltre lo 0, ha tutte radici complesse di modulo 1, anche ogni $ q_i $ avrà radici complesse di modulo 1. In particolare $ p_{1,1} $ vale esattamente 1 visto che è un reale non negativo che è anche prodotti di numeri complessi con modulo unitario. Ma com'è ovvio $ \sum_{1\le j\le 6}{p_{1,j}}=1 $ per cui $ p_{1,2}=p_{1,3}=\ldots=p_{1,6}=0 $, in contraddizione con le nostre ipotesi. []
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 30 mar 2010, 22:29

Vediamo se con questo andiamo meglio.. :roll:
Problema 2. A una gara di matematica partecipano 25 concorrenti; vengono assegnati 4 problemi che alla fine verranno valutati 0 e 1 (non esistono punteggi parziali). Mostrare che al termine della gara almeno una delle situazioni deve verificarsi:
i) ci sono 4 concorrenti che hanno risolto esattamente gli stessi problemi.
ii) ci sono 2 concorrenti per i quali ognuno dei 4 problemi è stato risolto da esattamente uno dei due.
The only goal of science is the honor of the human spirit.

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 30 mar 2010, 22:58

allora... ad ogni problema assegno un codice binario (0=sbagliato;1=risolto): ci sono $ 2^4 $ possibili combinazioni. Queste sono divise in 8 coppie complementari (cioè con gli 1 e gli 0 invertiti fra loro).
Ora se per assurdo la seconda condizione non fosse soddisfatta allora tutte le 25 combianzioni dei 25 concorrenti le dovrei scegliere fra al massimo 8 possibili combinazioni. (altrimenti avrei almeno una coppia complementare e la seconda sarebbe soddisfatta). A questo punto per i piccioni: ho 8 gabbie 25 piccioni(>3*8) quindi in una gabbia avrò almeno 4 piccioni: la prima condizione è soddisfatta

Scritta male come mio solito ma il ragionamento è quello giusto.

Quesito 3
Ci sono 27 cubetti uguali di spigolo 1, con faccette colorate con 6 colori
diversi. Calcolare la probabilita che, disponendoli casualmente insieme per formare un cubo piu grande di spigolo 3, il cubo così ottenuto abbia facce ognuna di un unico colore.

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 » 30 mar 2010, 23:20

cromat ha scritto:Calcolare la probabilita che, disponendoli casualmente insieme per formare un cubo piu grande di spigolo 3, il cubo così ottenuto abbia facce ognuna di un unico colore.
Quasi 0 ti va bene come risposta :P ?

Nel caso in cui la risposta sia no provo a saparare qualche presunta razzata.
Presa una faccia la probabilità che un faccina (faccia dei uno dei cubi 1X1) visibile sia colorata è 1, la probabilità che altre 8 facce siano colorate dello stesso colore della prima è $ (1/6)^8 $ e la stessa cosa immagino avrà per le altre facce, la probabilità cercata potrebbe allora essere $ \frac {1}{6} ^ {8\cdot6} $
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 31 mar 2010, 12:42

Anche a me viene lo stesso risultato... :D
Propongo un altro problema: c'è una griglia di finestre di lato 6x5 e sappiamo che ogni riga e ogni colonna ha esattamente 2 finestre accese, mentre tutte le altre sono spente.
Bisogna trovare tutte le possibili combinazioni di finestre accese e spente. :roll:

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 » 31 mar 2010, 13:08

Euler ha scritto:Anche a me viene lo stesso risultato... :D
Propongo un altro problema: c'è una griglia di finestre di lato 6x5 e sappiamo che ogni riga e ogni colonna ha esattamente 2 finestre accese, mentre tutte le altre sono spente.
Bisogna trovare tutte le possibili combinazioni di finestre accese e spente. :roll:
Euler se il risultato è giusto (aspetto qualcuno che lo confermi perchè non ne sono totalemnte sicuro) spetta a me postare il problema successivo ;)
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 31 mar 2010, 13:19

Scusa non conoscevo queste formalità... :mrgreen:
Allora prova a proporre tu quello delle finestre

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 31 mar 2010, 13:27

in realtà quello del dado era piiù complicato... bisognava ragionare sugli spigoli del cubo e ricordarsi che i dadi erano tutti uguali (con la stessa configurazione di colori)... però passiamo oltre...

su quelle delle finestre ho un dubbio di fondo: se è 6x5e ogni riga e colonna hanno esatttamente 2 finestre accese, se conto le finestre accese totali secondo le righe vengono 10 e secondo le colonne 12-> com'è possibile???

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 » 31 mar 2010, 13:44

cromat ha scritto:in realtà quello del dado era piiù complicato... bisognava ragionare sugli spigoli del cubo e ricordarsi che i dadi erano tutti uguali (con la stessa configurazione di colori)... però passiamo oltre...

su quelle delle finestre ho un dubbio di fondo: se è 6x5e ogni riga e colonna hanno esatttamente 2 finestre accese, se conto le finestre accese totali secondo le righe vengono 10 e secondo le colonne 12-> com'è possibile???
il dubbio su quello edlle finistre lo avevo anche .. forse voleva scrivere 5X5 :? .. comunque non passiamo oltre, perchè lo stesso dubbio sugli spigoli era venuto anche ame ma non sapevo come "risolverlo", se qualcuno più capace sa spiegarmelo ne sarei grato.
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 31 mar 2010, 14:02

dai ancora un po di tempo per quello del dado...poi stasera posto la soluzione!!!

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 31 mar 2010, 14:06

Scusate la cavolata che ho detto, intendevo che ogni riga e colonna ha o 2 o 0 finestre accese.

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 31 mar 2010, 14:26

Per quanto riguarda quello del dado, potrebbe essere (1/6)^8*(1/6)^6*(1/6)^4*(1/6)^4*(1/6)^2*(1/6)=(1/6)^25? :|

Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio da gian92 » 31 mar 2010, 14:38

per quello del cubo:

allora ragioniamo sulle possibili rotazioni nello spazio dei cubetti piccoli, sono 24 (fissando una faccia a "terra" possiamo fare 4 rotazioni e questo con tutte le facce).

bene una faccia di quello grande avrà il cubetto centrale che avrà un solo colore vincolato e quindi 4 rotazioni possibili, i 4 adiacenti a quello centrale con 2 colori vincolati e quindi 2 rotazioni possibili e i 4 angoli che potranno avere una sola posizione visto che hanno 3 colori vincolati).
quindi la probabilità di avere una faccia che possa essere di un cubo come quello richiesto è di:
$ \frac{4}{24}\cdot\frac{2}{24}^4\cdot\frac{1}{24}^4 $
bene il quadrato di questo numero sarà la probabilità di avere questa faccia e quella opposta (il cui colore lo potremo scegliere in 5 modi quindi il quadrato di questo numero per 6X5)
restano i 9 cubetti centrali, bene quello al centro non ci da problemi, lo possiamo prendere come vogliamo.
quelli laterali sugli spigoli li possiamo scegliere in 2 modi (hanno due colori fissati) mentre quelli al centro li possiamo scegliere in 4 modi (1 colore fissato)
mi sembra un po strano come risultato ma a me verrebbe:

$ (\frac{4}{24}\cdot\frac{2}{24}^4\cdot\frac{1}{24}^4)^2\cdot \frac{4}{24}^4\cdot\frac{2}{24}^4 $ moltiplicato per i modi di scegliere i colori che sono 6! e per le rotazioni del cubo grande (?) che sono 24.

p.s. non sono certo ma forse l'approccio giusto è questo...

Rispondi