Tavoli rotondi e distinzione di sessi
Tavoli rotondi e distinzione di sessi
Premetto che non so la soluzione , è 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?"
"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)
Uno dei primi pensieri fatti anch'io... però $ n = 2: $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} $
$ \displaystyle \frac{3!}{2!2!} = \frac{3}{2} $ che non è intero
"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)
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
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
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
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?
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?
Giusto per curiosità, è opera tua questa bizzarra formulazione del problema?Gatto ha scritto:l'unica distinzione è tra maschi e femmine
"Sei la Barbara della situazione!" (Tap)
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?
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
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
No, è un problema che ho trovato in giro... cmq sono curioso del perchè della formula (e della dimostrazione )piever ha scritto:Giusto per curiosità, è opera tua questa bizzarra formulazione del problema?Gatto ha scritto: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)
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?
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)
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!} $
avevo contato 2 volte un caso, ergo i conti tornano di nuovo
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!} $
la frase sopra e' sbagliata.Cmq non e' giusto!! appena accorto che mi ero doimenticato un caso nel n=4, quello in cui sono alternati.
a volte il caso e' molto bastardo
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
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
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} $
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"
Uhm, a quali ti riferisci?Tibor Gallai ha scritto:Falliscono già per n=6.
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
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)
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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!
ma li avete contati tutti a mano? per n=6
per n=7 sarebbero 246. Chi controlla?
una sovrastima del 7.7 e 5%. Beh, non posso lamentarmi.
E' abbastanza esatta!
ma li avete contati tutti a mano? per n=6
per n=7 sarebbero 246. Chi controlla?
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
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