Tavoli rotondi e distinzione di sessi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Tavoli rotondi e distinzione di sessi

Messaggio da Gatto »

Premetto che non so la soluzione :roll:, è un problema che ho trovato e che mi ha dato qualche problema...

"Ad una festa in maschera ci sono $ 2n $ persone, $ n $ maschi e $ n $ femmine. In quanti modi si possono sedere in un tavolo rotondo, se l'unica distinzione è tra maschi e femmine?"
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)
Alex90
Messaggi: 260
Iscritto il: 25 mag 2007, 13:49
Località: Perugia

Messaggio da Alex90 »

Ci provo...

le persone si possono disporre in $ 2n! $ modi, considerando poi le persone uguali e le rotazioni diventano:

$ \displaystyle \frac{2n!}{2n\cdot n! \cdot n!} = \frac{(2n-1)!}{n!^2} $
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio da Gatto »

Alex90 ha scritto:Ci provo...

le persone si possono disporre in $ 2n! $ modi, considerando poi le persone uguali e le rotazioni diventano:

$ \displaystyle \frac{2n!}{2n\cdot n! \cdot n!} = \frac{(2n-1)!}{n!^2} $
Uno dei primi pensieri fatti anch'io... però $ n = 2: $

$ \displaystyle \frac{3!}{2!2!} = \frac{3}{2} $ che non è intero :wink:
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

a sto punto ci si puo' aiutare empiricamente
n=1 si ha 1 modo
n=2 si hanno 2 modi
n=3 si hanno 4 modi
n=4 si hanno 10 modi

edit: dimenticato un caso per n=4, contato doppio un altro, ergo era giusto
Ultima modifica di SkZ il 13 mar 2009, 17:59, modificato 2 volte in totale.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Uhm, ho paura che il risultato non si scriva in maniera molto decorosa..

Per adesso direi che il risultato è:

$ \displaystyle \frac{1}{2n}\sum_{d|n} {2d\choose d} \cdot\phi\left(\frac{n}{d}\right) $

che, stando alla tabella di skz, funziona per n=1,2,3,4... (cosa di cui sono genuinamente sorpreso...)

La mia dimostrazione è ai limiti dell'indecenza però... Qualcuno ne ha di più decorose prima che mi avventuro a postarla?
Gatto ha scritto:l'unica distinzione è tra maschi e femmine
Giusto per curiosità, è opera tua questa bizzarra formulazione del problema? :P
"Sei la Barbara della situazione!" (Tap)
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

non sono sicuro (non ho controllato) ma mi pare che (escludendo il caso n=1) ci sia una soluzione semplice.
Cmq, perche' quella formula? ovvero come la giustifichi?
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio da Gatto »

piever ha scritto:
Gatto ha scritto:l'unica distinzione è tra maschi e femmine
Giusto per curiosità, è opera tua questa bizzarra formulazione del problema? :P
No, è un problema che ho trovato in giro... cmq sono curioso del perchè della formula (e della dimostrazione :D)
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Uhm, ecco un modo non troppo sottile per dimostrare quella formula:

Ogni disposizione possibile di maschi e femmine ha un ordine (vale a dire il numero minimo k tale che shiftando tutto di k posti da una parte ottengo la stessa configuarazione di maschi e femmine). Di conseguenza la configurazione si ottiene prendendo il primo "blocco" di k tizi seduti e ripetendoglielo accanto fino a riempire la tavola, quindi tra queste k persone, metà sono maschi e metà sono femmine, per cui k=2m per qualche m (m è il numero di maschi). Ora, visto che k|2n, allora m|n, quindi in sostanza l'idea è contare tutte le configurazioni che hanno ordine 2m con m divisore di n, e dividere ciascuna quantità per l'ordine (perché a noi interessano a meno di rotazioni).

Chiamiamo f(m) le configurazioni di ordine 2m (per ora _non_ le conto a meno di rotazioni): è chiaro che, per ogni m, $ \displaystyle\sum_{d|m}f(d)={2m\choose m} $ da cui $ \displaystyle f(m)=\sum_{d|m}{2d\choose d}\cdot \mu \left(\frac{m}{d}\right) $

Ora la quantità che a noi interessa è dunque:

$ \displaystyle\sum_{m|n} \frac{f(m)}{2m}=\sum_{m|n}\frac{1}{2m}\sum_{d|m}{2d\choose d}\cdot \mu \left(\frac{m}{d}\right)=\sum_{d|n}{2d\choose d}\sum_{d|m|n}\frac{1}{2m}\cdot \mu \left(\frac{m}{d}\right)= $

$ \displaystyle =\frac{1}{2n}\sum_{d|n}{2d\choose d}\sum_{\delta |\nu }\frac{\nu}{\delta }\cdot \mu(\delta )= \frac{1}{2n}\sum_{d|n}{2d\choose d}\cdot\phi (\nu )=\frac{1}{2n}\sum_{d|n}{2d\choose d}\cdot\phi \left(\frac{n}{d}\right) $

Dove $ \displaystyle\nu =\frac{n}{d} $ e $ \displaystyle\delta =\frac{m}{d} $

Ora, se la sommatoria finale possa essere scritta in maniera più decorosa mi è ignoto...

P.S. Skz, qual è la soluzione facile?
"Sei la Barbara della situazione!" (Tap)
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

avevo poco tempo e una soluzione simil giusta, ergo in scioltezza, la parte $ $f(n)=\frac{(2n)!}{n!n!} $ e' sicuramente giusta, basta solo trovare il valore di $ ~k $ tale che $ $\frac{f(n)}{k} $ sia la soluzione
dai i tentativi a mano hai
$ $n=1\Rightarrow f(n)=2\Rightarrow k=2 $
$ $n=2\Rightarrow f(n)=6\Rightarrow k=3 $
$ $n=3\Rightarrow f(n)=20\Rightarrow k=5 $
$ $n=4\Rightarrow f(n)=70\Rightarrow k=7 $
allora le cose sono 2:
1) k e' l'n-esimo primo: assurdo e cmq si vede che per $ ~n=5 $ non vale ($ ~11\not|252 $)
2) $ ~k=2n-1 $ e escludo $ ~n=1 $ come caso anomalo: ha piu' senso e piu' facile da trovare una giustificazione

ergo $ $\frac{(2n)!}{(2n-1)n!n!} $
Cmq non e' giusto!! :lol: appena accorto che mi ero doimenticato un caso nel n=4, quello in cui sono alternati. :oops:
a volte il caso e' molto bastardo
la frase sopra e' sbagliata.
avevo contato 2 volte un caso, ergo i conti tornano di nuovo
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
gismondo
Messaggi: 84
Iscritto il: 05 feb 2009, 18:42
Località: Roma

Messaggio da gismondo »

Credo si possa generalizzare in questo modo:
Dati $ $2n $ oppure $ $2n+1 $ individui di cui $ $k $ maschi il numero di modi in cui si possono disporre attorno a un tavolo rotondo è:

$ \frac{1}{2n-1} {2n\choose k} $
oppure $ \frac{1}{2n+1} {2n+1\choose k} $
"Per tre cose vale la pena di vivere: la matematica, la musica e l'amore"
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Falliscono già per n=6.
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio da Gatto »

Tibor per n = 5 e n = 6 quanto dovrebbe venire?
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Tibor Gallai ha scritto:Falliscono già per n=6.
Uhm, a quali ti riferisci?

E sopratutto, qual è, secondo te, la soluzione al problema originale di Gatto?

@ gismondo: uhm, mi sembra ottimista generalizzare a quel modo...

@ Gatto: a me risulta che per n=5 sono 26 e per n=6 sono 80... Mah...

EDIT: Ok Tibor, ora ho riguadagnato fiducia in me stesso :D

Tra l'altro, sai se il risultato finale si può scrivere decentemente??
Ultima modifica di piever il 14 mar 2009, 14:48, modificato 3 volte in totale.
"Sei la Barbara della situazione!" (Tap)
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Ah, io concordo con la soluzione di piever!
Dicevo che le varie altre soluzioni e/o generalizzazioni falliscono per n=6.
Almeno, così mi pare. :shock:
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

la mia sol "empirica" dice 28 per n=5 e 84 per n=6

una sovrastima del 7.7 e 5%. Beh, non posso lamentarmi.
E' abbastanza esatta! :lol:

ma li avete contati tutti a mano? :shock: per n=6
per n=7 sarebbero 246. Chi controlla? :D
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Rispondi