Japanese Mathematical Olympiad 2009 - 1
Buon lavoro!
Nazionali giapponesi
Nazionali giapponesi
Trovare tutti i numeri positivi $ $n$ $ tali che $ $2^n+n | 8^n+n$ $.
Japanese Mathematical Olympiad 2009 - 1
Buon lavoro!
Japanese Mathematical Olympiad 2009 - 1
Buon lavoro!
Si offende qualcuno se un miserabile vecchietto risponde? 
Il fatto è che è la classica giornata afosa di inizio primavera,dove fare il proprio dovere richiede un atto di volontà insostenibile
(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 :
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(beh in realtà un caso a mano l'ho fatto,n=1, ed è vera )
Ciaociao!
Il fatto è che è la classica giornata afosa di inizio primavera,dove fare il proprio dovere richiede un atto di volontà insostenibile
(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
: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
(beh in realtà un caso a mano l'ho fatto,n=1, ed è vera ) 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"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
-
Gogo Livorno
- Messaggi: 99
- Iscritto il: 14 gen 2010, 14:56
- Località: Livorno
-
Gogo Livorno
- Messaggi: 99
- Iscritto il: 14 gen 2010, 14:56
- Località: Livorno
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...
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
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
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?
Correggetemi e smentitemi, ma per esempio, 16=2*3 + 10
La scomposizione è giusta, ma non è certo una divisione con quoziente e resto...
Dove sbaglio?
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.
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
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
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.
$ 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.
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.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.
Mi dispiace per aver generato cotanta confusione, la prossima volta farò più attenzione.
qualunque "confusione" genera chiarimenti. E il forum serve a chiarirengshya ha scritto:Mi dispiace per aver generato cotanta confusione, la prossima volta farò più attenzione.
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
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
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.
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.