Problemi esteri 2

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

eccovi altri problemi che vengono sempre da gare nazionali di paesi olimpicamente fortini.
 
 1. Show that x5 + 2x + 1 cannot be factorised into two polynomials with integer coefficients (and degree ≥ 1).
 
 2. For which n can {1, 2, 3, ... , 4n} be divided into n disjoint 4-element subsets such that for each subset one element is the arithmetic mean of the other three?
 
 3. How many permutations of 1901, 1902, 1903, ... , 2000 are such that none of the sums of the first n permuted numbers is divisible by 3 (for n = 1, 2, 3, ... , 100)?
 
 spero vi piacciano... [ Questo Messaggio è stato Modificato da: Biagio il 11-04-2004 20:45 ]

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-11 16:43, Biagio wrote:
 
 3. How many permutations of 1901, 1902, 1903, ... , 2000 are such that none of the sums of the first n permuted numbers is divisible by 3 (for n = 1, 2, 3, ... , 2000)?
 
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 maybe you wanted to write \" (for n=1, 2, ..., 100) \" <IMG SRC="images/forum/icons/icon_smile.gif">
 (attendesi conferma)
 
 comunque non sembrano male...
 
 il primo si dovrebbe fare in modo abbastanza standard, analizzando le varie alternative (1 polinomio di 2 grado e 1 di 3, etc) espandendo e verificando che vengono fuori uguaglianze mai vere

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

okay, per il primo confermo:
 
 il polinomio non ha soluzioni razionali (sostituendo + o -1 il risultato non è 0) quindi non ha fattori di 1 grado a coefficienti interi
 
 dunque l\'unica fattorizzazione può essere del tipo
 
 (ax2+bx+c)(dx3+ex2+fx+g).
 
 sviluppando e uguagliando con x5+2x+1, e considerando i 4 casi a,d=+ o -1 , c,g=+ o -1, in tutti i casi viene un\' eq di 2 grado in b che non dà soluz intere
 
 per l\'ultimo (se ho interpretato bene il testo)
 nell\'insieme (1901,...,2000) ci sono
 33 elementi ==0 (3)
 33 elementi ==1 (3)
 34 elementi ==2 (3)
 consideriamo una permutazione generica dell\'insieme: dobbiamo fare in modo che ciascuna delle somme Sn=sumxi con xi i-esimo elemento della permutazione non sia ==0 modulo 3
 
 notiamo che gli elementi ==0 (3) non cambiano la congruenza della somma, e quindi possono essere messi in qualsiasi punto della permutazione, tranne che come primo elemento: dunque ci sono (99,33)*(33!) possibili scelte per essi.
 ora, consideriamo due casi:
 - il primo elemento è ==1 (3). allora la permutazione modulo 3 (saltando gli elementi ==0) è
 1-1-2-1-2-1-2....1-2 con 32 blocchi 1-2. a questo punto però rimangono 2 elementi ==2, quindi c\'è una somma ==0 mod 3
 - il primo elemento è ==2 (3). allora la permutazione mod 3 deve essere
 2-2-1-2-1-2-1-2-1...2-1 con 33 blocchi 2-1, e qui siamo a posto (gli elementi ==2 sono 34).
 i modi di scegliere gli elementi in quest\'ultimo caso sono
 34*33*33*32*32*...*2*2=34*(33!)2
 dunque le permutazione che soddisfano sono
 
 (99,33)*(33!)*34*(33!)2
 
 un bel mostro di numero <IMG SRC="images/forum/icons/icon_confused.gif"> [ Questo Messaggio è stato Modificato da: talpuz il 11-04-2004 20:30 ]

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

si talpuz, hai ragione,c\'è un errore nel testo che mi sono dimenticato di correggere dopo il copia/incolla.
 
 è giusto, comunque [ Questo Messaggio è stato Modificato da: Biagio il 11-04-2004 20:49 ]

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

2. gli elementi di ogni quadrupla sono ovviamente distinti
 sia m l\'elemento minimo di 1 quadrupla, e n,k,h gli altri 3. allora
 m=(n+k+h)/3, e n,h,k>=m. se almeno una delle ultime disug è stretta, si ha
 m=(n+k+h)/3>(m+m+m)/3=m, assurdo. dunque le quadruple devono essere costituite da elementi uguali. quindi la richiesta è impossibile per ogni n [ Questo Messaggio è stato Modificato da: talpuz il 11-04-2004 20:49 ]

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

in questo invece hai sbagliato, mi sa.
 prova per n=2...

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

err...
 in effetti avevo interpretato
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 such that for each subset every element is the arithmetic mean of the other three
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 <IMG SRC="images/forum/icons/icon_smile.gif">

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-11 16:43, Biagio wrote:
 eccovi altri problemi che vengono sempre da gare nazionali di paesi olimpicamente fortini.
 
 2. For which n can {1, 2, 3, ... , 4n} be divided into n disjoint 4-element subsets such that for each subset one element is the arithmetic mean of the other three?
 
 [ Questo Messaggio è stato Modificato da: Biagio il 11-04-2004 20:45 ]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Proviamo per n=1 e osserviamo che non si verificano le condizioni . Ora proviamo n=2 e osserviamo che invece in tal caso si creano i sottoinsiemi disgiunti (2,3,4,7) e (1,5,6,8), che verificano la condizione. Indichiamo quindi le cifre della successione come n1, n2, n3... n8, osservando che verificano la condizione n4= (n2+n3+n7)/3 e n6=(n1+n6+n8)/3, poniamo ora le cifre della successione del numero pari successivo come n1+8, n2+8... n8+8 e osserviamo che n4+8=(n2+8+n3+8+n7+8)/3 e n6+8=(n1+8+n6+8+n8+8)/3, che semplificata sono uguali alle precedente e quindi verificano le condizioni. Il procedimento si può ripetere all’infinito e quindi le condizioni sono verificate per ogni multiplo di due, cioè ogni numero pari e sottoinsiemi creati sono sempre tutti i precedenti più i nuovi otto.
 Il ragionamento è corretto o sembrano i deliri di un pazzo???
 Con i dispari sono ancora in alto mare, ci ripenso, ma non credo di trovare la soluzione.

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

si beh, anche se il ragionamento non l\'ho seguito molto(non dico che sia errato, anzi...), è sicuramente giusto nelle conclusioni.
 ora manca il caso n dispari

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

Ci ho pensato una giornata e forse ci sono!!!
 Ogni sottoinsieme richiesto può essere visto come l\'insieme di quattro numeri che, divisi per quattro, danno un numero intero. Quindi l\'avere le somme dei numeri di ogni sottoinsieme divisibili per quattro è la condizione necessaria (non so se è sufficiente, ma non è importante) perchè la tesi sia verificata. Se ogni sottoinsieme è divisibile per 4 allora anche l\'unione dev\'essere divisibile per 4, essendo i sottoinsiemi disgiunti. L\'unione è rappresentata numericamente dalla soma di tutte le cifre della successione iniziale, che è n*(n+1)/2, nel caso di un numero dispari essa è ((2^2*DISPARI)*DISPARI)/2, che semplificato da 2*DIPARI*DISPARI, dato che il prodotto di due dispari è un dispari, tale numero non è divisibile per 4 perchè un numero dispari non contiene, ovviamente, 2 nei propri fattori primi. Quindi è impossibile che da una successione 1,2,3... 4n con n dispari si creino n sottoinsiemi disgiunti con un numero uguale alla media degli altri tre.
 Aggiungendo la dimostrazione precedente si ha che:
 Le condizioni richieste si verificano per ogni numero pari e per nessun numero dispari.
 
 Ok? Mi sembra impossibile averlo risolto.
 
 
 [ Questo Messaggio è stato Modificato da: Boll il 13-04-2004 08:32 ] [ Questo Messaggio è stato Modificato da: Boll il 14-04-2004 14:52 ]

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-11 16:43, Biagio wrote:
 1. Show that x5 + 2x + 1 cannot be factorised into two polynomials with integer coefficients (and degree ≥ 1).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Uhm...due polinomi con coefficienti interi e di primo grado, moltiplicati fra loro possono dare al più un polinomio di secondo grado, ad essere ottimisti.

ReKaio · Messaggio da **ReKaio** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-12 18:58, EvaristeG wrote:
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-11 16:43, Biagio wrote:
 1. Show that x5 + 2x + 1 cannot be factorised into two polynomials with integer coefficients (and degree ≥ 1).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Uhm...due polinomi con coefficienti interi e di primo grado, moltiplicati fra loro possono dare al più un polinomio di secondo grado, ad essere ottimisti.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 G, te l\'ho detto di smettere con l\'alcol, non ti fa bene, solo in rari soggetti aumenta le capacità mentali.

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Ero sobrio K...

Messaggio da **ma_go** » 01 gen 1970, 01:33

esiste un modo carino per farla, che non preveda il criterio di eisenstein?

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-13 11:13, ma_go wrote:
 esiste un modo carino per farla, che non preveda il criterio di eisenstein?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 cos\'è?? <IMG SRC="images/forum/icons/icon_eek.gif">