Dadi

[Anér]

Sia $ n\in\mathbb{N}\setminus\{0,1\} $. Abbiamo $ n $ dadi a tre facce (non so come sia fatto un dado a tre facce, ma non importa), e ogni dado ha le tre facce etichettate con i numeri 1,2,3. Alberto, Barbara e Cristina devono scegliere chi di loro sarà il protagonista del prossimo problema, e per farlo lanciano gli $ n $ dadi, fanno la somma dei risultati e prendono la classe di congruenza modulo 3 della somma: se viene 1 allora vince Alberto, se viene 2 vince Barbara, se viene 3 vince Cristina. Sappiamo che la probabilità di vittoria è 1/3 per ognuno. Dimostrare che almeno uno dei dadi è equo (ossia basterebbe lanciare quello per scegliere il vincitore).
Dimostrare che se al posto di 3 si mette un numero non primo alora non è più detto che esista un dado equo.
Bonus question: determinare se la tesi è vera in generale se al posto di 3 si mette un qualsiasi numero primo (a questa domanda non ho trovato una risposta).

[dario2994]

Bon... non sono convintissimo della dimostrazione, ma se è giusta è ganzissima

Assumo che un set di $n$ dadi rispetti la richiesta, dimostro che ce n'è uno equo.
Se $3\mid n$ aggiungo un dado tale che esca sempre la faccia 3... tanto le probabilità restano identiche e ho che $3\nmid n$.
Siano $a_i,b_i,c_i$ le probabilità che esca $2,1,3$ nell'i-esimo dado.
Definisco $\displaystyle P(x)=\prod_{i=1}^n(a_ix^2+b_ix+c_i)$... Allora la somma dei coefficienti di P(x) con la stessa congruenza modulo 3 deve fare $\frac13$ (per ipotesi che la somma sia equa modulo 3).
In particolare allora per "roots of unity filter" ottengo che (omega è una radice terza primitiva di 1):
$\displaystyle \frac{P(1)+P(\omega)+P(\omega^2)}3=\frac13$
Ma banalmente $P(1)=1$ da cui si ottiene $P(\omega)+P(\omega^2)=0$ ***.
Ora definisco $\displaystyle Q(x)=\prod_{i=1}^n(a_ix^3+b_ix^2+c_ix)$. Tutti i ragionamenti fatti su P(x) valgono anche su Q(x) perciò $Q(\omega)+Q(\omega^2)=0$ ed inoltre vale banalmente $Q(x)=x^nP(x)$. Perciò sostituendo ottengo: $\omega^nP(\omega)+\omega^{2n}P(\omega^2)=0\Rightarrow P(\omega)+\omega^{n}P(\omega^2)=0$ *****
Ora sottraggo *** da ***** ottenendo $P(\omega^2)(\omega^n-1)=0$ dato che $3\nmid n$ questo equivale a $P(\omega^2)=0$ perciò per qualche $i$ vale: $a_i\omega+b_i\omega^2+c_i=0$ ma questo è un polinomio a coefficienti reali che ha una radice complessa, allora ha anche il suo coniugato e quindi $x^2+x+1$ (che è il terzo polinomio ciclotomico) divide quella roba, ma questo implica banalmente $a_i=b_i=c_i$ e perciò il dado è equilibrato, che è la tesi.

Questa roba sicuramente non si può generalizzare se al posto di 3 si mette un non primo. Se ci si mette un primo qualche ragionamento del genere si può ancora fare ma non è così facile concludere (sempre che si concluda) perchè ci si ritrova con ben più radici dell'unità... dovrebbe uscire fuori una specie di sistema... che un qualche senso potrebbe anche averlo, domani ci penso, ora non mi pare l'orario giusto

[Anér]

Va bene, io avevo fatto così: dimostro che la tesi è vera per 2 dadi; questo basta perché sostanzialmente puoi sommare i dadi (sommare due dadi significa sostituirli con il dado equivalente ad essi); ora se hai 2 dadi e definisci $ a_1,b_1,c_1,a_2,b_2,c_2 $ come le probabilità che esca 2,1,3 rispettivamente nel primo e nel secondo dado, hai che $ (a_1\omega^2+b_1\omega+c_1)(a_2\omega^2+b_2\omega+c_2) $ se svolto come polinomio in $ \omega $ fa 0 in quanto si ottengono tre complessi con la stessa norma e sfasati di 120°; allora per la legge di annullamento del prodotto uno dei fattori è nullo, ma questo vuol dire che ha i coefficienti a,b,c uguali perché se $ \omega $ è radice di un polinomio a coefficienti reali, allora quel polinomio è divisibile per $ x^2+x+1 $, e qui abbiamo a che fare con un polinomio di secondo grado. Sì, in sostanza è la stessa cosa.
Con un primo non sono riuscito a fare nulla dopo aver ridotto a 2 il numero di dadi.

[fph]

non so come sia fatto un dado a tre facce, ma non importa

Well, puoi o prendere un dado a sei facce e quozientare, oppure http://www.google.it/images?q=d3+dice. In generale poi se incolli per la base due piramidi a base $n$-agono regolare e quozienti le facce a due a due ottieni un D$n$ (equo) per ogni $n\geq 3$.

EDIT: tornando in tema, quella da voi proposta sembra la way to go. Sospetto che potrebbe essere un buon esercizio da smontare con l'algebra lineare o con DFT (ma probabilmente si fa anche senza); appena ho un po' di tempo ci provo perché potrebbe essere istruttivo. By the way, Anér, tu c'eri alla lezione di "algebra lineare per problemi olimpici" mia e di Sam un paio di winter fa?

[dario2994]

EDIT: In questa soluzione dico una minchiata... sul finale: "ma se un polinomio reale ha una radice p-esima dell'unità allora ce l'ha tutte" ciò è falso La cosa forse si avvicina alla verità se aggiungo che i coefficienti devono essere positivi... cioè... non si fattorizza il p-esimo ciclotomico nei reali positivi... e questo mi pare quasi credibile...

Bon... continuo e generalizzo al caso $p$ primo. Prima di tutto prima, l'ora mi scusa, ho segato... cioè potevo imporre $Q(x)=xP(x)$ e tutto funzionava, anche senza la richiesta $3\nmid n$ quindi ora farò così...
Lavoro assumendo che i dadi abbiano $p$ primo facce.
Sia $a_{i,j}$ la probabilità che l'i-esimo dado dia j... definisco:
$\displaystyle P(x)=\prod_{i=1}^n\left(\sum_{j=1}^{p}a_{i,j}x^j\right)$
Ora applicando gli stessi ragionamenti usati nel caso p=3, cioè roots of unity filter su $P(x),xP(x),x^2P(x),\dots x^{p-1}P(x)$ ottengo:
$\displaystyle \forall 0\le k\le p-1:\ \frac{\sum_{i=0}^{p-1}\omega^{ik}P(\omega^i)}p=\frac1p\Rightarrow \sum_{i=0}^{p-1}\omega^{ik}P(\omega^i)=1$
Questo lo interpreto come un simpatico sistema che ha come incognite: $\left(P(1),P(\omega),\dots , P(\omega^{p-1})\right)$... è chiaro che $(1,0,\dots 0)$ è una soluzione del sistema... se la matrice dei coefficienti avesse determinante non nullo allora quella dovrebbe essere anche l'unica soluzione per un qualche teorema (che non saprei dimostrare e di cui neppure so il nome)... non scrivo il matricione perchè è un casino, ma è chiaro che è una matrice di Vandermonde che ha come basi le radici p-esime dell'unità... queste sono tutte diverse, quindi il determinante è nonnullo quindi quella di prima è l'unica soluzione del sistema, quindi P si annulla per tutte le radici primitive dell'unità, perciò il p-esimo polinomio ciclotomico divide quella roba, ma se un polinomio reale ha una radice p-esima dell'unità allora ce l'ha tutte (per una strana storia del polinomio minimo ) perciò per qualche i deve valere:
$\displaystyle 1+x+\dots +x^{p-1}$ divide $\displaystyle \sum_{j=1}^{p}a_{i,j}x^j$ ma allora l'i-esimo dado è equilibrato

p.s. ho usato parecchia roba che non saprei mostrare
p.p.s. poi penso anche al caso non primo

[dario2994]

Bon... se il numero di facce non è primo lo scrivo come $ab$ con $a,b>1$ e prendo un dado che mi sputa fuori solo $1,2,\dots a$ e li sputa fuori in modo equo e un dado che mi sputa fuori solo $b,2b,\dots, ab$ e lo fa in modo equo. È chiaro che in questo modo i 2 dadi insieme ne fanno uno equo. Poi per $n>2$ aggiungo dadi a caso oltre a questi e tutto continua ad essere equo.
Una cosa banale che vorrei far notare: se c'è un dado equo allora anche la somma degli n dadi è equa... quindi con un numero primo di facce quello è un sse
Comunque il problema è bellissimo, da dove l'hai preso?

[fph]

Questo lo interpreto come un simpatico sistema che ha come incognite: $\left(P(1),P(\omega),\dots , P(\omega^{p-1})\right)$... è chiaro che $(1,0,\dots 0)$ è una soluzione del sistema... se la matrice dei coefficienti avesse determinante non nullo allora quella dovrebbe essere anche l'unica soluzione per un qualche teorema (che non saprei dimostrare e di cui neppure so il nome)... non scrivo il matricione perchè è un casino, ma è chiaro che è una matrice di Vandermonde che ha come basi le radici p-esime dell'unità... queste sono tutte diverse, quindi il determinante è nonnullo quindi quella di prima è l'unica soluzione del sistema, quindi P si annulla per tutte le radici primitive dell'unità, perciò il p-esimo polinomio ciclotomico divide quella roba,

Ottimo, hai (ri)scoperto la discrete Fourier transform (DFT). Sostanzialmente l'idea è che se hai un polinomio di grado $<d$, allora puoi "rappresentarlo" come l'insieme dei valori che assume sulle radici $d$-esime dell'unità $\omega^i$, o come i coefficienti, e che la mappa che manda gli uni negli altri è biiettiva* (ed è "praticamente" una trasformazione ortogonale a meno di un fattore $\sqrt{n}$, cioè preserva la distanza euclidea).

[dario2994]

Per un numero primo generico di facce mi sa che è falso...
Se piglio 5 facce esistono 2 dadi non equi con somma equa
Sia $\omega=\cos(\frac{2\pi}5)+i\sin(\frac{2\pi}5)$ allora piglio 2 dadi descritti da questi polinomi (opportunamente omogenizzati in modo che la somma dei coefficienti sia 1):
$x(x-\omega)(x-\omega^4)(x+1)^2$ e $x^3(x-\omega^2)(x-\omega^3)$
E allora dovrebbe fungere, proprio perchè il quinto polinomio ciclotomico divide il prodotto, ma nessuno dei 2... in particolare sono abbastanza convinto che la cosa si generalizzi anche oltre il 5, che comunque dovrebbe bastare come controesempio.
L'idea per generalizzare sarebbe: presa $\omega$ una radice p-esima primitiva dell'unità allora $(x-\omega)(x-\bar{\omega})(x+1)^{p-3}$ è un polinomio a coefficienti reali positivi.
EDIT: Penso di aver ricondotto questo a: $\frac n{n+2}\ge \cos\left(\frac{2\pi}{n+3}\right)$ per ogni intero $n\ge 1$
EDIT2: Peccato che quel claim è falso ad esempio per n=10

[dario2994]

Bon... forse ho chiuso anche il caso con un primo qualsiasi: per ogni $p$ primo maggiore di 3 esistono 2 dadi con $p$ facce non equi tali che la somma sia equa modulo p.
Costruisco i 2 dadi
Sia $\omega$ una radice $p$-esima primitiva dell'unità.
Definisco
$A(x)=(x-\omega)(x-\omega^{p-1})$
$B(x)=(x-\omega^2)(x-\omega^3)\cdots (x-\omega^{p-2})$
A(x) e B(x) hanno tutti i coefficienti reali dato che ogni radice è accoppiata con la coniugata. Inoltre $A(x)B(x)=\Phi_p(x)$
Siano $a,b$ i coefficienti di A(x),B(x) con modulo massimo.
Definisco:
$\displaystyle P_1(x)=A(x)\left(B(x)+\frac1{|a|+1}\right)=\Phi_p(x)+\frac{A(x)}{|a|+1}$
$\displaystyle P_2(x)=B(x)\left(A(x)+\frac1{|b|+1}\right)=\Phi_p(x)+\frac{B(x)}{|b|+1}$
Questi hanno i coefficienti reali positivi dato che $\Phi_p(x)$ ha tutti i coefficienti uguali a 1, mentre il polinomio che gli viene aggiunto per definizione di a,b ha tutti i coefficienti con modulo minore di 1.
Definisco altri 2 polinomi, che sono poi i dadi:
$\displaystyle D_1(x)=\frac{xP_1(x)}{P_1(1)}$
$\displaystyle D_2(x)=\frac{xP_2(x)}{P_2(1)}$
Assumo che la probabilità che il dado $n\in \{1,2\}$ dia $k$ sia $[x^k]D_n(x)$. È facile notare che per $p>3$ i 2 dadi non risultano equi singolarmente.
Ma la somma è equa poichè $\Phi_p(x)\mid D_1(x)D_2(x)$ (mostrato prima)

[Anér]

@ dario2994: ottimo, mi hai tolto un bel dubbio. Dunque la tesi per cui se n dadi insieme sono equilibrati allora uno di essi è equilibrato è vera solo per dadi con 2 o 3 facce. Grazie per il "bellissimo" del problema, l'ho inventato io (in realtà tutti i problemi che propongo sul forum sono mie idee o generalizzazioni di altri problemi).
@ fph: scherzavo sul dado a 3 facce, intendevo dire che non puoi costruire un poliedro con 3 facce. La lezione di algebra lineare tua e di Sam del Senior 2009 la ricordo soltanto in parte, dovrei farmi un ripasso, ma la DFT mi pare proprio che non ci fosse (pazienza, c'erano molte altre cose interessanti).