Esercizio interessantissimo
Esercizio interessantissimo
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
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
Re: Esercizio interessantissimo
Curiosità: un utente del forum ha scritto la sua tesi di maturità su come risolvere questo problema
Re: Esercizio interessantissimo
Potresti linkarmelo?
Grazie
Grazie
Re: Esercizio interessantissimo
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?
Qualcuno ha qualche idea?
Re: Esercizio interessantissimo
Hai provato ad utilizzare il lemma di Burnside?
Re: Esercizio interessantissimo
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...
Qualcuno sa qualche altro metodo? Evidentemente non credo di riuscire a studiare una cosa del genere...
Re: Esercizio interessantissimo
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.
Re: Esercizio interessantissimo
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].
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].