Nazionali giapponesi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Nazionali giapponesi

Messaggio da ngshya » 25 apr 2010, 15:14

Trovare tutti i numeri positivi $ $n$ $ tali che $ $2^n+n | 8^n+n$ $.

Japanese Mathematical Olympiad 2009 - 1

Buon lavoro! :D

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 25 apr 2010, 17:14

Si offende qualcuno se un miserabile vecchietto risponde? :oops:
Il fatto è che è la classica giornata afosa di inizio primavera,dove fare il proprio dovere richiede un atto di volontà insostenibile :P(D'altronde mi sono ricordato ci una volta che il buon ani-sama quando stava al secondo anno come me ora, non riuscendo a tenere a bada l'impulso si espose alla vergogna,come sto per fare io ora, di togliere la pazziella dalle mani dei creaturiXD).
E poi,provando a darmi un tono, forse ho trovato un modo per esporre la metàsoluzione con delle considerazioni istruttive e didattiche;quindi magari può essere utile provare a scriverle(non mi è uscito bene eh?..xd), vabbeh procedo,esponendomi al pubblico ludibrio :D :
Se ho un pò di manualità con le congruenze, la prima cosa che penso è: devo stimare la quantità $ 2^{3n}+n\pmod{2^n+n} $, le due quantità sono ben visibilmente correlate(cioè si assomigliano parecchio)e la libertà del lavorare con le congruenze sta proprio nel poter modificare $ 2^{3n}+n $ trovando dei rappresentanti di quella classe di congruenza "opportuni". La domanda che deve sorgere dunque è cos'è opportuno? Risposta vaga: un modo in cui l'oggetto trasformato abbia una relazione più comprensibile con $ 2^n+n $.
A questo punto possiamo individuare 2 classi di cambiamento apparentemente utili:
potremmo trasformare $ 2^{3n}+n $ facendo diventare n una potenza di 2,ossia scrivere la relazione $ 2^{3n}+n \equiv 2^{3n}-2^n \pmod{2^n+n} $ oppure possiamo fare al contrario $ 2^{3n}+n \equiv -n^3+n $.entrambe le relazioni vengono dal fatto che $ 2^n\equiv -n \pmod{2^{n}+n} $. Ora, la prima è apparentemente interessante, ed è una strada puramente congruenzosa, chessò uno può provare a mettere $ 2^n(2^{2n}-1) \equiv 0 $ e provare a fare ragionamenti di divisibilità con fatti che collegano l'esponente(2n) e il modulo (2^n+n), ma se provate a vedere i più noti e semplici di questi(eulero-fermat e compagnia cantando),tenendo conto anche di quello che fa 2^n,vedrete che non esce niente di controllabile, quindi no strada bocciata. L'altra invece: la relazione $ n^3-n \equiv 0 \pmod{2^n+n} $, se uno la guarda un pò in faccia, si accorge che è insostenibile per n abbastanza grande: $ n^3-n<2^n+n $;quindi come disse un tale,se a|b a non potrà essere tanto più grande di b, in pratica abbiamo finito. Per n maggiore di 9 vale quella disuguaglianza, e poi si tratta di controllare qualche caso a mano,oppure di trovare qualche minicriterio ad hoc per diminuire i casi,oppure (consiglio prezioso per chi dovendo affrontare una gara deve imparare ad aggirare processi lunghi a mente)lo chiedete al vostro pc xd, io questo non l'ho fatto per ragioni analoghe a quelle della riga 2 :P(beh in realtà un caso a mano l'ho fatto,n=1, ed è vera :D )
Ciaociao!
Ultima modifica di Carlein il 25 apr 2010, 17:28, modificato 1 volta in totale.
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 25 apr 2010, 17:27

Io non avevo applicato le congruenze e ho diviso rozzamente i due polinomi e poi ho concluso allo stesso modo. :D

Gogo Livorno
Messaggi: 99
Iscritto il: 14 gen 2010, 14:56
Località: Livorno

Messaggio da Gogo Livorno » 25 apr 2010, 21:43

Come fai a dividere i polinomi se sono esponenziali? :roll:

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 25 apr 2010, 22:11

Intendevo questo:
$ $2^{3n}+n=(2^n+n)(2^{2n}-2^{n}n+n^2)+(n-n^3)$ $

Guardo il 2 come x.

Gogo Livorno
Messaggi: 99
Iscritto il: 14 gen 2010, 14:56
Località: Livorno

Messaggio da Gogo Livorno » 25 apr 2010, 22:54

e da qui? imponi resto = 0 e quindi n uguale a 0 o a 1?

chi ti garantisce l'unicità della scomposizione?

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 26 apr 2010, 00:22

si riconduce a quanto detto da Carlein:
il resto deve essere minore del divisore. Da qui una conclusione.
se il resto trovato non e' minore, allora...
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Gogo Livorno
Messaggi: 99
Iscritto il: 14 gen 2010, 14:56
Località: Livorno

Messaggio da Gogo Livorno » 26 apr 2010, 00:28

Beh, ma dopotutto quella è una scomposizione che torna come vogliamo noi, mica è per forza una divisione canonica dove il resto è minore del divisore.

Correggetemi e smentitemi, ma per esempio, 16=2*3 + 10

La scomposizione è giusta, ma non è certo una divisione con quoziente e resto...

Dove sbaglio?

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 26 apr 2010, 01:20

Non sbagli, piu' o meno

16=2*8+0 e' una divisione rispetto a 2 con resto 0
16=3*5+1 e' una divisione rispetto a 3 con resto 1
come dicevo, nella divisione il resto per definizione e' "minore" del divisore
poi quel minore dipende dal contesto. Nel caso di numeri e' il "comune minore", nel caso di polinomi "minore come grado".

diverso e' una scomposizione che serve a manipolare il nostro oggetto in qualcosa piu' facilmente maneggiabile.

quella di ngshya e' una "scomposizione", o meglio una "riscrittura vantaggiosa" (non e' una vera scomposizione in fattori). Poi ci si basa sul fatto che la divisione di una somma e' la somma delle divisioni.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

EvaristeG
Site Admin
Messaggi: 4780
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 26 apr 2010, 03:04

Se io riesco a dire che
$ A=kB+C $
e che $ C<B $, allora sicuramente A è divisibile per B solo quando C=0.

Non ci si appella alla divisione tra polinomi, semplicemente a questo fatto.

Quindi bisogna vedere quando $ C<B $ e discutere a mano gli altri casi. Trattandosi qui di un esponenziale contro un polinomio, la disuguaglianza richiesta sarà vera per n abbastanza grandi.

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 26 apr 2010, 12:44

Gogo Livorno ha scritto:Beh, ma dopotutto quella è una scomposizione che torna come vogliamo noi, mica è per forza una divisione canonica dove il resto è minore del divisore.
Ok, mi correggo, quando ho detto "ho diviso rozzamente i due polinomi" intendevo "riscrivo il dividendo come il prodotto fra il divisore e qualcosa più qualcos'altro", mi era venuta in mente il temine "dividere" perché il procedimento che ho usato per trovare quel "qualcos'altro" assomiglia vagamente a una divisione fra i polinomi.

Mi dispiace per aver generato cotanta confusione, la prossima volta farò più attenzione. :wink:

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 26 apr 2010, 20:13

ngshya ha scritto:Mi dispiace per aver generato cotanta confusione, la prossima volta farò più attenzione. :wink:
qualunque "confusione" genera chiarimenti. E il forum serve a chiarire ;)
L'unico consiglio e' di abituarsi sempre ad essere precisi, per evitare rogne nelle gare con le correzioni.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

Messaggio da danielf » 01 mag 2010, 11:49

ngshya ha scritto:Intendevo questo:
$ $2^{3n}+n=(2^n+n)(2^{2n}-2^{n}n+n^2)+(n-n^3)$ $

Guardo il 2 come x.
ma quindi si deve dimostrare che$ (2^{2n}-2^{n}n+n^2)>(n-n^3) $
e poi porre $ (n-n^3)=0 $?

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 01 mag 2010, 18:54

Non esattamente... o forse non ho capito la tua domanda.

Quello che volevo dire è:
$ $\frac{2^{3n}+n}{2^n+n}=\frac{(2^n+n)(2^{2n}-2^{n}n+n^2)+(n-n^3)}{2^n+n}=(2^{2n}-2^{n}n+n^2)+\frac{(n-n^3)}{2^n+n}$ $
Tutto questo deve essere intero.

E quindi $ $2^n+n|(n-n^3)$ $, cioè $ $|2^n+n| \le |n-n^3|$ $, altrimenti $ $\frac{(n-n^3)}{2^n+n}$ $ non sarà mai intera.

Pochi sono i valori di n tali che quella disuguaglianza sia verificata, si provano tutti questi valori a mano e si risolve.

Rispondi