Un classico

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Un classico

Messaggio da Triarii » 08 lug 2013, 19:37

Propongo questo problema che credo sia abbastanza istruttivo per gli utenti più giovani . Premetto che non ho una soluzione ufficiale (anche se credo la mia sia giusta, o almeno spero :P).
Abbiamo $ 2n $ giocatori di carte, divisi in due squadre ognuna formata da $ n $ membri. Si vogliono disporre intorno ad un tavolo in modo che non vi siano 2 o più membri di una stessa squadra accanto (quindi sono alternati). Considerando che le disposizioni nelle quali ogni giocatore ha gli stessi vicini vanno contate solo una volta, in quanti modi si possono disporre?
"We' Inge!"
LTE4LYF

wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Un classico

Messaggio da wall98 » 09 lug 2013, 12:52

finalmente qualcosa di combinatoria che riesco a risolvere (sperando di non aver cannato anche questo :) )
allora dato che la tavola è rotonda,se abbiamo una configurazione ne possiamo ottenere altre 2n-1 che non ci servono,quindi se troviamo una formula che non considera le rotazioni, possiamo poi dividere per 2n trovando cio che ci serve.
se la tavola non ruota,possiamo considerarla come una fila di posti al cinema,ricordando pero che i capifila devono essere di squadre diverse
in questo caso per il primo posto abbiamo n modi per scegliere uno della prima squadra ,per il secondo ancora n per uno della seconda squadra,poi n-1 e cosi via...
siccome il primo della fila puo essere della prima o della seconda abbiamo $ \displaystyle \frac{2n!^2}{4n}=\frac{n!^2}{2n} $? (ho diviso per due perche avere A a destra e B a sinistra è la stessa cosa che avere A a sinistra e B a destra)
ok c'è sicuramente qualche errore,dov'è?
Il problema non è il problema, il problema sei tu.

Avatar utente
angelo3
Messaggi: 62
Iscritto il: 12 gen 2013, 19:31
Località: Treviso

Re: Un classico

Messaggio da angelo3 » 09 lug 2013, 14:23

Io l'ho fatto così:
Fissiamo il giocatore A della squadra A, per quello accanto avremo $ n $ possibilità , per quello dopo $ n-1 $; il successivo $ n-1 $ e cosi via...
Ottengo $ n[(n-1)!]^2=\frac{(n!)^2}{n} $
Penso che Tu abbia sbagliato a dividere per 2 perché se consideri casi diversi iniziare da A o da B conti due volte ogni disposizione perché se ne prendi una cominciata da A e poi metti l'ultimo giocatore dove era il primo e "scali" tutto ottieni una configurazione equivale alla iniziale. Spero riesca a capire quest'ultimo fatto che l'ho scritto incasinato :?
Angelo

wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Un classico

Messaggio da wall98 » 09 lug 2013, 16:18

premesso che hai molto probabilmente ragione tu dato che quasi sempre sbaglio banalmente in combinatoria.
in ogni caso io intendevo dire (l'ho scritto male anche io) che dato che due disposizioni sono uguali se ognuno ha le stesse persone di fianco, non conta se le persone stanno a destra o a sinistra.
per esempio la sequenza AXB e BXA non sono ottenibili tra loro con una rotazione,pero ne dobbiamo considerare solo una perche ognuno ha gli stessi vicini.
Il problema non è il problema, il problema sei tu.

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Un classico

Messaggio da Triarii » 09 lug 2013, 19:41

Metto la mia soluzione. (Spero di non aver cannato :P)
Testo nascosto:
Fisso il primo elemento e lo considero della prima squadra. Abbiamo $ n $ possibilità. Il giocatore successivo in senso orario è della seconda squadra. Lo possiamo scegliere in altri $ n $ modi. Abbiamo quindi $ n!\cdot n! $ permutazioni. Tuttavia alcune sono equivalenti: infatti le rotazioni e le simmetrie assiali conservano le relazioni di vicinanza. Devo quindi dividere per il numero di rotazioni e simmetrie assiali. In linea di massima queste sono 4n per un insieme si 2n elementi ($ 2n $ rotazioni e $ 2n $ simmetrie) solo che non tutte vanno considerate. Infatti io ho considerato che il primo posto appartenesse alla squadra 1, come anche tutti i posti dispari (dispari se considero il primo come posto 1, il secondo come posto 2 ecc.). Nelle mie permutazioni il primo posto non compare mai occupato da un membro della seconda squadra. Quindi le rotazioni di un numero di posti dispari (che farebbero diventare il posto 1 occupato da un membro della squadra 2) in realtà non vanno considerate. Ho quindi n rotazioni possibili. Un analogo ragionamento va fatto per le simmetrie, che da $ 2n $passano a $ n $(per vederlo bene considerate un poligono regolare di $ 2n $ lati e vedete un po' gli assi di simmetria). Per ogni permutazione abbiamo quindi $ 2n $permutazioni equivalenti. Il numero di modi in cui si possono disporre è quindi $ \tfrac {n! \cdot n!} {2n} $
"We' Inge!"
LTE4LYF

Ouroboros
Messaggi: 73
Iscritto il: 20 feb 2013, 21:42
Località: Milano

Re: Un classico

Messaggio da Ouroboros » 09 lug 2013, 23:48

Carino! Lo proporrei come quesito di maturità, vista la poca fantasia degli ultimi tempi...
"Qual é 'l geomètra che tutto s'affige
per misurar lo cerchio, e non ritrova,
pensando, quel principio ond'elli indige,
tal era io a quella vista nova:
veder voleva come si convenne
l'imago al cerchio e come vi s'indova"

☆zeta
Messaggi: 13
Iscritto il: 13 ago 2013, 20:14

Re: Un classico

Messaggio da ☆zeta » 17 ago 2013, 19:51

Ciao, ho visto che è stato già risolto, vorrei comunque provare a mettere la mia soluzione visto che mi sto allenando per problemi di difficoltà simile a questo. (Ho ottenuto il vostro stesso risultato, ma a me piacerebbe sapere se il ragionamento con cui ci sono arrivato è corretto).

Ho $ n $ giocatori di una squadra e $ n $ di un altra... prendo tutti quelli di una squadra li faccio sedere tutti, li mixo ed ottengo $ n! $ combinazioni diverse di cui la metà uguali ma invertite quindi in tutto ho $ n!/2 $ combinazioni possibili ora per essere sicuro di non avere mai combinazioni identiche degli altri giocatori ne scelgo uno a cui assegnero' ogni volta un posto sempre tra 2 giocatori diversi per i restanti ho $ n-1 $ possibili posizioni per il primo $ n-2 $ per il secondo ecc... il tutto per $ n!/2 $ combinazioni dell'altra squadra quindi in totale ho $ n!*(n-1)!/2 $ combinazioni.

Rispondi