Esercizio interessantissimo

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
Rispondi
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Esercizio interessantissimo

Messaggio da nico lol »

Ciao ragazzi, mi stavo esercitando su combinatoria e ho trovato un esercizio interessantissimo della gara a squadre 2014.
Riporto per comodità il testo:

Sebbene HOMero non lo dica, i Proci sono molto generosi nei confronti di Penelopell. Un giorno pensano di regalarle
ognuno una collana fatta di 17 pietre perfettamente sferiche scelte tra smeraldi e rubini. Ovviamente vogliono evitare
di regalare alla regina di Itôca due collane che opportunamente ruotate nello spazio risultino uguali. Quante collane
diverse possono far confezionare i Proci? Gli smeraldi sono tutti uguali tra loro e inseriti nella collana nello stesso
modo, e così i rubini.
Allora, la mia idea era quella di utilizzare i rubini come dei segni "+", mi spiego meglio:
Esempio, supponiamo di avere una collana con 5 pietre tra smeraldi e rubini, supponiamo che ci siano un numero di rubini prima pari ad r=0,poi r=1, poi r=2 e cosi via:
r=0: la collana è fatta tutta da smeraldi e quindi n=1.
r=1: la collana è fatta da 1 rubino da 4 smeraldi e poiché fissato un rubino ho sempre lo stesso modo di "disporre" i smeraldi, allora ho n=1.
r=2: Fisso 1 rubino, mi resta quindi da disporre 1 rubino e 3 smeraldi. A questo punto, ho immaginato di contare le varie disposizioni in questo modo:
contare queste disposizioni è equivalente a contare in quanti modi posso sommare 2 interi NON NEGATIVI a prescindere dall'ordine, quindi ho sostanzialmente A+B=3, dove il segno + indica il rubino "rosso" che separa i smeraldi.
Quindi per r=2, ho sostanzialmente (3,0),(1,2) quindi n=2.
r=3: Fisso 1 rubino, mi restano da disporre 2 rubini e 2 smeraldi. Allo stesso modo conto i modi di sommare 3 interi NON NEGATIVI:
A+B+C=2., ottengo quindi (2,0,0),(1,1,0).
r=4. Fisso 1 rubino, suddivido altri 3 rubini e 1 smeraldo. quindi non mi resta altro che
A+B+C+D=1, quindi (1,0,0,0).
Infine rimarrebbe il caso in cui la collana è composta da tutti rubini, quindi n=1.
In conclusione per una collana formata da 5 pietre da smeraldi e rubini ottengo:
1+1+2+1+1=6.
Ho verificato il tutto per via grafica (costruendomi un pentagono e contando i casi e mi trovo.)
Adesso, non so proprio come fare per quanto riguarda il conteggio per n=17, a mano diventa una tortura.
Qualche anima pia che può aiutarmi?Grazie davvero ma sto impazzendo :lol:
matpro98
Messaggi: 75
Iscritto il: 24/04/2017, 11:36

Re: Esercizio interessantissimo

Messaggio da matpro98 »

Curiosità: un utente del forum ha scritto la sua tesi di maturità su come risolvere questo problema
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Esercizio interessantissimo

Messaggio da nico lol »

Potresti linkarmelo?
Grazie
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Esercizio interessantissimo

Messaggio da nico lol »

Ok, Ho risolto il problema delle somme ma non ho risolto il problema originale, infatti mi sono accorto che ho sbagliato ad impostarlo.
Qualcuno ha qualche idea? :evil:
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Esercizio interessantissimo

Messaggio da afullo »

Hai provato ad utilizzare il lemma di Burnside?
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Esercizio interessantissimo

Messaggio da nico lol »

Ok, sostanzialmente per risolvere questo problema bisogna conoscere una quantità non indifferente di teoria.
Qualcuno sa qualche altro metodo? Evidentemente non credo di riuscire a studiare una cosa del genere...
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Esercizio interessantissimo

Messaggio da afullo »

Come strumento è teorico, ma dal punto di vista applicativo può essere contestualizzato all'ambito olimpionico facendo a meno di tutta l'algebra astratta che caratterizza la sua dimostrazione generale. Guarda questo esempio.
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Esercizio interessantissimo

Messaggio da ronny »

seguo
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Esercizio interessantissimo

Messaggio da afullo »

Noto ora che nel caso di 5 pietre hai dimenticato un addendo, le possibilità sono in realtà [tex]1+1+2+2+1+1=8[/tex].

In generale, l'identità [tex]id[/tex] fissa tutte le [tex]2^n[/tex] configurazioni (per ogni pietra si può scegliere smeraldo o rubino, indipendentemente l'una dall'altra); la rotazione di uno scatto [tex]R[/tex] fissa solo le due in cui ci sono solo smeraldi o solo rubini; riguardo la rotazione di due scatti [tex]R^2[/tex], ogni pietra deve essere la stessa di quella a distanza 2, secondo il verso di rotazione scelto (indifferente considerare orario od antiorario), se [tex]n[/tex] è dispari questo significa che la determinazione di una pietra implica tutte le altre (2 genera [tex]\mathbb{Z}_n[/tex]), mentre se [tex]n[/tex] è pari vengono determinate una sì e una no, e si ha libertà su di un'altra pietra.

Proseguendo il ragionamento, e tenuto conto anche del fatto che [tex]\gcd(0,n) = n[/tex], si trova come risultato [tex]\displaystyle \sum_{i=0}^{n-1} \frac{2^{\gcd(i,n)}}{n}[/tex]; nel caso [tex]n=17[/tex], il valore è di [tex]\bf{7712}[/tex].
Rispondi