Per farmi perdonare che rovino subito i problemi belli, ne posto uno carino anche se facile. Per favore chi e' esperto non posti subito, senno' poi dovra' farsi perdonare anche lui eccetera...
Allora, sia $ \displaystyle p(x_1,\dots ,x_n)=\prod_{1\le i<j\le n}\frac{x_j-x_i}{j-i} $
Dimostrare che se gli $ x_i $ sono interi, allora anche $ p(x_1,\dots ,x_n) $ e' intero...
Bonne chance...
polinomio buffo: dara' sempre valori interi?
polinomio buffo: dara' sempre valori interi?
"Sei la Barbara della situazione!" (Tap)
Allora, il denominatore è banalmente $ $\prod_{1\le k<n} (n-k)^k $ (per esempio il fattore $ $n-2 $ lo otteniamo da $ $j=n $ e $ $i=2 $ o da $ $j=n-1 $ e $ $i=1 $)
I piccioni dicono che al numeratore abbiamo almeno $ $k $ coppie di $ $x_i $ con la stessa congruenza modulo $ $n-k $ quindi la loro differenza è congrua a 0 modulo $ $n-k $, quindi abbiamo per ogni fattore $ d $ al denominatore un fattore $ $m $ al numeratore tali che $ $d|m $ quindi $ $p(x_1,\dots,x_n) $ è intero.
Il tutto modulo errori stupidi.
I piccioni dicono che al numeratore abbiamo almeno $ $k $ coppie di $ $x_i $ con la stessa congruenza modulo $ $n-k $ quindi la loro differenza è congrua a 0 modulo $ $n-k $, quindi abbiamo per ogni fattore $ d $ al denominatore un fattore $ $m $ al numeratore tali che $ $d|m $ quindi $ $p(x_1,\dots,x_n) $ è intero.
Il tutto modulo errori stupidi.
Non è chiaro come usi il principio dei piccioni, poi stai attento al fatto che se ad ogni fattore cattivo del denominatore associ un fattore buono del numeratore che lo annulla, se a tanti fattori cattivi associ lo stesso fattore buono poi non torna... cioè, sarà anche giusto, ma con sto raffreddore io non ci capisco niente 
Per i piccioni: al numeratore abbiamo n $ $x_i $, mentre le classi di congruenza di $ $n-k $ sono $ $n-k $ quindi ci sono k $ $x_i $ di troppo, ognuno di essi forma una coppia con un un'altra $ $x_j $ appartenente alla stessa classe di congruenza. Per il seccondo punto ora che mi ci fai pensare hai ragione... ora però sono troppo stanco per pensarci, domani vedo se riesco a metterci una pezza 
@ julio 14: non metterti a discutere con edriv alle 11 di sera, a un certo punto iniziera' a farti credere che ogni problema del forum coimplica l'assioma della scelta...
@wolverine: quanto oschura? Se non ti secca troppo scriverla in LaTeX magari mandamela per mp..
ciaociao
@wolverine: quanto oschura? Se non ti secca troppo scriverla in LaTeX magari mandamela per mp..
ciaociao
"Sei la Barbara della situazione!" (Tap)
E' cosi' oSCHURa e non-olimpica che posso anche metterla qui in chiaro... di sicuro non toglie a nessuno il gusto di cercare una soluzione elementare
Per prima cosa osserviamo che $ p(x_1+k,x_2+k,\dots,x_n+k)=p(x_1,x_2,\dots,x_n) $ e dunque possiamo supporre che tutti gli $ x_i $ siano negativi, e che permutare tra loro le $ x_i $ cambia $ p(x_1,x_2,\dots,x_n) $ moltiplicandolo per $ \pm1 $ (+1 o -1 a seconda se la permutazione e' pari o dispari). Dunque non e' restrittivo supporre $ 1-x_1\geq2-x_2+\cdots n-x_n\geq0 $. A questo punto poniamo $ \lambda_j=j-x_j $, indichiamo con $ s_{\lambda_1,\dots,\lambda_n}(z_1,\dots,z_n) $ il polinomio di Schur associato alla successione decrescente di interi positivi $ \lambda_1\geq\lambda_2\geq\cdots\geq \lambda_n\geq0 $, e ci ricordiamo che i polinomi di Schur sono polinomi simmetrici a coefficienti interi e che vale la formula (si trova dimostrata su qualunque libro di teoria delle rappresentazioni)
$ \displaystyle{s_ {\lambda_1,\dots,\lambda_n}(1,1,\dots,1)=\prod_{1\leq i<j\leq n}\frac{\lambda_i-\lambda_j+j-i}{j-i} $
ovvero, ricordandoci che $ \lambda_j=j-x_j $,
$ \displaystyle{s_ {\lambda_1,\dots,\lambda_n}(1,1,\dots,1)= \prod_{1\leq i<j\leq n}\frac{x_j-x_i}{j-i} $
Per prima cosa osserviamo che $ p(x_1+k,x_2+k,\dots,x_n+k)=p(x_1,x_2,\dots,x_n) $ e dunque possiamo supporre che tutti gli $ x_i $ siano negativi, e che permutare tra loro le $ x_i $ cambia $ p(x_1,x_2,\dots,x_n) $ moltiplicandolo per $ \pm1 $ (+1 o -1 a seconda se la permutazione e' pari o dispari). Dunque non e' restrittivo supporre $ 1-x_1\geq2-x_2+\cdots n-x_n\geq0 $. A questo punto poniamo $ \lambda_j=j-x_j $, indichiamo con $ s_{\lambda_1,\dots,\lambda_n}(z_1,\dots,z_n) $ il polinomio di Schur associato alla successione decrescente di interi positivi $ \lambda_1\geq\lambda_2\geq\cdots\geq \lambda_n\geq0 $, e ci ricordiamo che i polinomi di Schur sono polinomi simmetrici a coefficienti interi e che vale la formula (si trova dimostrata su qualunque libro di teoria delle rappresentazioni)
$ \displaystyle{s_ {\lambda_1,\dots,\lambda_n}(1,1,\dots,1)=\prod_{1\leq i<j\leq n}\frac{\lambda_i-\lambda_j+j-i}{j-i} $
ovvero, ricordandoci che $ \lambda_j=j-x_j $,
$ \displaystyle{s_ {\lambda_1,\dots,\lambda_n}(1,1,\dots,1)= \prod_{1\leq i<j\leq n}\frac{x_j-x_i}{j-i} $
I'm the best there is at what I do. But what I do best isn't very nice.
A julio: quando una dimostrazione non funziona perchè dividendi e divisori si confondono troppo tra di loro, spesso il problema si risolve facendo lo stesso ragionamento per le potenze di primi (e assumendo tacitamente l'assioma della scelta, ma forse qui dovrei non dirlo). In particolare, mi pare che qui funzioni, ma serve qualche stima più dettagliata di quella che hai fatto.
P.S. Detesto le soluzioni non olimpiche!
P.S. Detesto le soluzioni non olimpiche!
@ wolverine: ahhhhhhhhhhh, non avevo colto il gioco di parole (forse perche' ignoro completamente cosa sia un polinomio di Schur 
), comunque non pensavo fosse cosi' tanto oscura la soluzione...
@ julio: per stavolta (ma solo per stavolta) da' retta al buon edriv
@ edriv: lol
), comunque non pensavo fosse cosi' tanto oscura la soluzione...@ julio: per stavolta (ma solo per stavolta) da' retta al buon edriv
@ edriv: lol
"Sei la Barbara della situazione!" (Tap)
Non e' difficile definire i polinomi di Schur, ne' dimostrare l'identita'
$ \displaystyle{S_{\lambda_1,\dots,\lambda_n}(1,1,\dots,1)=\prod_{1\leq i< j\leq n} \frac{\lambda_i-\lambda_j+j-i}{j-i}}, $
ma per farlo serve la nozione di determinante di una matrice ed e' utile avere familiarita' con il concetto di limite di una funzione (in effetti qui serve solamente un limite molto semplice:
$ \displaystyle{ \lim_{x\to 1}\frac{x^a-1}{x^b-1}=\frac{a}{b}} $
). Quando ho un po' di tempo posto un po' di esercizi mirati in Matematica non elementare.
$ \displaystyle{S_{\lambda_1,\dots,\lambda_n}(1,1,\dots,1)=\prod_{1\leq i< j\leq n} \frac{\lambda_i-\lambda_j+j-i}{j-i}}, $
ma per farlo serve la nozione di determinante di una matrice ed e' utile avere familiarita' con il concetto di limite di una funzione (in effetti qui serve solamente un limite molto semplice:
$ \displaystyle{ \lim_{x\to 1}\frac{x^a-1}{x^b-1}=\frac{a}{b}} $
). Quando ho un po' di tempo posto un po' di esercizi mirati in Matematica non elementare.
I'm the best there is at what I do. But what I do best isn't very nice.
Re: polinomio buffo: dara' sempre valori interi?
Fa molto piacere essere ascoltato, pero' $ \mbox{dopo una settimana}\neq\mbox{subito} $, quindi chiunque trova una soluzione olimpica puo' postare..piever ha scritto:Per favore chi e' esperto non posti subito...
Tra un po' metto la mia.
"Sei la Barbara della situazione!" (Tap)
L'idea della mia soluzione è questa: in questo problema la divisibilità funziona non come un budino ma come un panino. Vediamo di spiegare meglio il concetto
Siano $ ~ a_1,\ldots,a_n, b_1,\ldots,b_m $ interi nonnulli.
Se, per ogni potenza di primo $ ~ p^{\alpha} $, gli $ ~ a_i $ che sono divisibili per $ ~ p^{\alpha} $ sono minori o uguali dei $ ~ b_i $ che sono divisibili per $ ~ p^{\alpha} $, allora:
$ ~ a_1a_2\cdots a_n \mid b_1b_2 \cdots b_m $
(attenzione: non è un se e solo se!)
Visto che è facile e che se lo dimostro rischiate di non capirlo, lo lascio dimostrare a voi. Vogliamo applicare questo lemma al problema. Da una parte abbiamo:
$ ~ \prod (i-j) $
e dall'altra:
$ ~ \prod (x_i - x_j) $
Fissiamo la nostra potenza di primo (anzi, a noi bastano le potenze di primo, ma vale per un generico k) e dividiamo $ ~ \{1,2,\ldots, n\} $ e $ ~ \{x_1,\ldots,x_n\} $ nelle classi di congruenza modulo k.
Chiaramente $ ~ \{x_1,\ldots,x_n\} $ sono distribuiti a caso, ma invece $ ~ \{1,2,\ldots, n\} $ sono distribuiti nella maniera più omogenea possibile (i.e., la differenza tra le cardinalità di due classi è al più 1). Il numero di elementi è lo stesso. Useremo l'AM-GM per far vedere che il modo omogeneo minimizza il numero di coppie congrue modulo n.
Cioè:
Siano $ ~ a_1,\ldots,a_n $ il numero di elementi di $ ~ \{1,2,\ldots, n\} $ rispettivamente congrui a 1,2,...,n modulo n.
Siano $ ~ b_1,\ldots,b_n $ il numero di elementi di $ ~ \{x_1,x_2,\ldots, x_n\} $ rispettivamente congrui a 1,2,...,n modulo n.
Quanti fattori del divisore sono divisibili per n?
Beh, sono esattamente:
$ \displaystyle d_1 = {a_1 \choose 2} + \ldots + {a_n \choose 2} $
Mentre i fattori del divisore divisibili per n sono:
$ \displaystyle d_2 = {b_1 \choose 2} + \ldots + {b_n \choose 2} $
Inoltre abbiamo la condizione che $ ~ \sum a_i = \sum b_i $. Vogliamo far vedere che $ ~ d_2 \ge d_1 $. Sviluppando i binomiali, moltiplicando per 2 e semplificando la parte lineare che resta (perchè $ ~ \sum a_i = \sum b_i $) resta da far vedere che:
$ \displaystyle \sum b_i^2 \ge \sum a_i^2 $
Questo funziona perchè gli a_i sono ben distribuiti. Lo dimostriamo così: se due b_i hanno differenza maggiore di 1, possiamo alzare di 1 il più grande e abbassare di 1 il più piccolo facendo calare LHS. Ma se due b_i hanno differenza al più 1, possiamo far vedere che le n-uple $ ~ (a_1,\ldots,a_n),(b_1,\ldots,b_m) $ sono uguali a meno di permutazioni.
Siano $ ~ a_1,\ldots,a_n, b_1,\ldots,b_m $ interi nonnulli.
Se, per ogni potenza di primo $ ~ p^{\alpha} $, gli $ ~ a_i $ che sono divisibili per $ ~ p^{\alpha} $ sono minori o uguali dei $ ~ b_i $ che sono divisibili per $ ~ p^{\alpha} $, allora:
$ ~ a_1a_2\cdots a_n \mid b_1b_2 \cdots b_m $
(attenzione: non è un se e solo se!)
Visto che è facile e che se lo dimostro rischiate di non capirlo, lo lascio dimostrare a voi. Vogliamo applicare questo lemma al problema. Da una parte abbiamo:
$ ~ \prod (i-j) $
e dall'altra:
$ ~ \prod (x_i - x_j) $
Fissiamo la nostra potenza di primo (anzi, a noi bastano le potenze di primo, ma vale per un generico k) e dividiamo $ ~ \{1,2,\ldots, n\} $ e $ ~ \{x_1,\ldots,x_n\} $ nelle classi di congruenza modulo k.
Chiaramente $ ~ \{x_1,\ldots,x_n\} $ sono distribuiti a caso, ma invece $ ~ \{1,2,\ldots, n\} $ sono distribuiti nella maniera più omogenea possibile (i.e., la differenza tra le cardinalità di due classi è al più 1). Il numero di elementi è lo stesso. Useremo l'AM-GM per far vedere che il modo omogeneo minimizza il numero di coppie congrue modulo n.
Cioè:
Siano $ ~ a_1,\ldots,a_n $ il numero di elementi di $ ~ \{1,2,\ldots, n\} $ rispettivamente congrui a 1,2,...,n modulo n.
Siano $ ~ b_1,\ldots,b_n $ il numero di elementi di $ ~ \{x_1,x_2,\ldots, x_n\} $ rispettivamente congrui a 1,2,...,n modulo n.
Quanti fattori del divisore sono divisibili per n?
Beh, sono esattamente:
$ \displaystyle d_1 = {a_1 \choose 2} + \ldots + {a_n \choose 2} $
Mentre i fattori del divisore divisibili per n sono:
$ \displaystyle d_2 = {b_1 \choose 2} + \ldots + {b_n \choose 2} $
Inoltre abbiamo la condizione che $ ~ \sum a_i = \sum b_i $. Vogliamo far vedere che $ ~ d_2 \ge d_1 $. Sviluppando i binomiali, moltiplicando per 2 e semplificando la parte lineare che resta (perchè $ ~ \sum a_i = \sum b_i $) resta da far vedere che:
$ \displaystyle \sum b_i^2 \ge \sum a_i^2 $
Questo funziona perchè gli a_i sono ben distribuiti. Lo dimostriamo così: se due b_i hanno differenza maggiore di 1, possiamo alzare di 1 il più grande e abbassare di 1 il più piccolo facendo calare LHS. Ma se due b_i hanno differenza al più 1, possiamo far vedere che le n-uple $ ~ (a_1,\ldots,a_n),(b_1,\ldots,b_m) $ sono uguali a meno di permutazioni.
Uhm, mi sfugge il ruolo del panino, ma vabbeh, edriv e' edriv 
Se invece foste stati a conoscenza del lemma 0: "ogni problema di piever e' corollario di un precedente problema di piever", avreste potuto usare un lemma che ho postato da qualche parte quest'estate e che non trovo, comunque e' questo:
LEMMA PRECEDENTE:
Sia $ p(x_1,\dots ,x_n) $ un polinomio a coefficienti in $ \mathbb{C} $ di grado $ g_i $ nella variabile $ x_i $
Se esistono $ a_1,\dots ,a_n\in\mathbb{Z} $ tali che $ \forall x\in\{ a_1,a_1+1,\dots, a_1+g_1\}\times\dots\times\{ a_n,a_n+1,\dots ,a_n+g_n\}\; $$ p(x)\in\mathbb{Z} $ allora $ \forall x\in\mathbb{Z}^n\;p(x)\in\mathbb{Z} $
Dimostrazione del problema:
usando il LEMMA PRECEDENTE, notiamo che $ g_i=n-1 $, poniamo $ a_i=1 $ per ogni $ i $ e ci rimane da dimostrare che il nostro polinomiaccio da' risultati interi quando gli $ x_i $ sono interi da 1 a n. Se $ x_i=x_j $ con $ i\neq j $, allora il polinomiaccio si annulla e siamo felici... Se invece gli $ x_i $ sono tutti distinti, allora la funzione che ad $ i $ associa $ x_i $ e' una permutazione, e il polinomiaccio fa $ \pm 1 $ a seconda del segno della permutazione, e siamo ancora piu' felici, perche' abbiamo detto la parola "permutazione" e potevamo farne a meno.
Ma questo e' molto piu' incasinato dela soluzione di edriv, e non ho neanche dimostrato il LEMMA PRECEDENTE ma vabbeh, edriv e' edriv...
Se invece foste stati a conoscenza del lemma 0: "ogni problema di piever e' corollario di un precedente problema di piever", avreste potuto usare un lemma che ho postato da qualche parte quest'estate e che non trovo, comunque e' questo:
LEMMA PRECEDENTE:
Sia $ p(x_1,\dots ,x_n) $ un polinomio a coefficienti in $ \mathbb{C} $ di grado $ g_i $ nella variabile $ x_i $
Se esistono $ a_1,\dots ,a_n\in\mathbb{Z} $ tali che $ \forall x\in\{ a_1,a_1+1,\dots, a_1+g_1\}\times\dots\times\{ a_n,a_n+1,\dots ,a_n+g_n\}\; $$ p(x)\in\mathbb{Z} $ allora $ \forall x\in\mathbb{Z}^n\;p(x)\in\mathbb{Z} $
Dimostrazione del problema:
usando il LEMMA PRECEDENTE, notiamo che $ g_i=n-1 $, poniamo $ a_i=1 $ per ogni $ i $ e ci rimane da dimostrare che il nostro polinomiaccio da' risultati interi quando gli $ x_i $ sono interi da 1 a n. Se $ x_i=x_j $ con $ i\neq j $, allora il polinomiaccio si annulla e siamo felici... Se invece gli $ x_i $ sono tutti distinti, allora la funzione che ad $ i $ associa $ x_i $ e' una permutazione, e il polinomiaccio fa $ \pm 1 $ a seconda del segno della permutazione, e siamo ancora piu' felici, perche' abbiamo detto la parola "permutazione" e potevamo farne a meno.
Ma questo e' molto piu' incasinato dela soluzione di edriv, e non ho neanche dimostrato il LEMMA PRECEDENTE ma vabbeh, edriv e' edriv...
"Sei la Barbara della situazione!" (Tap)
Ho capito il tuo piano diabolico... volevi sfidarci a trovare una soluzione elementare quando poi tiravi fuori dal cappello da mago la banana cubica... peccato che wolverine è uscito con una banana più cubica della tua
Che poi il lemma precedente non l'ho mai visto... ricorda vagamente un IMO di non mi ricordo che anno ma potrei sbagliarmi.
Che poi il lemma precedente non l'ho mai visto... ricorda vagamente un IMO di non mi ricordo che anno ma potrei sbagliarmi.