TdN for dummies

[Thomas]

Oramai sono diventato una pippa in problemini di tdn... (mai stato granchè in effetti )... saranno secoli che non ne faccio uno... vediamo cosa esce fuori....

Supponiamo di essere arrivati al passaggio k_esimo e cerchiamo brutalmente $b=a_(k+1)$.

Posto $a_1+...+a_k=A$, $a_1^2+...+a_k^2=CA$, si deve trovare $b$, t.c.:

$(A+b)|CA+b^2$

visto che $b>A=>b>a_k$, poniamo $b=Ak$

$A(1+k)|CA+A^2k^2$ <= $(k+1)|C+Ak^2$

ma si trova che $(k+1)|C+AK^2<=>(k+1)|A+C$ e quindi si può trovare un tale $k$...

a parte casi banali infatti $A+C>1$...

[fedeb]

scusami,avrei qualche perplessità:
perchè $b>A$? non era condizione che fosse $b>a_k$ ??

poi mi chiedevo perchè $(k+1)|C+Ak^2$ implica $(k+1)|C+A$
grazie

[Thomas]

Guarda fedeb la mia soluzione può essere benissimo errata... ti rispondo cmq...


- si infatti $b>=A$ (ho aggiunto un maggiore-uguale) è una condizione più forte di $b>a_k$, per come è definito A (a parte casi limite). E quindi è sufficiente soddisfare la prima. (NB: sufficiente, non necessario... molti dei passaggi fatti non sono forzati dal problema, è questo che mi fa credere che la mia sol sia errata );

- per la seconda domanda, supponi che $(k+1)|C+Ak^2$. Vale inoltre (sono identità) anche che:

- $(k+1)|(k+1)^2|A(k+1)^2=Ak^2+2Ak+A$

e quindi k+1 divide sia $C+Ak^2$ che $ak^2+2ak+a^2$ e quindi anche la loro differenza, ovvero $2Ak+A-C$...

Ora di nuovo lo stesso trucco per far andar via anche il $k$. Vale che:

-$(k+1)|2A(k+1)=2Ak+2A$

ed eseguendo la differenza $(k+1)|A+C$...

e inoltre i passaggi sono reversibili, quindi se A+C>0 si trova un $k$ positivo diverso da 0...;

[fedeb]

perfetto, la faccenda della divisibilità è chiarissima, grazie.
pero per quanto riguarda la condizione $b>A$, non mi sembra lecito assumerla come vera e procedere.
il senso è che : non andrebbe dimostrata?? inoltre la dimostrazione funziona sse tale condizione è verificata, no??
grazie

[Thomas]

nel post precedente ho corretto... basta $b>=A$ (anche perchè è quello che riesco ad ottenere alla fine )... (supponi di avere già fatto lo step 1 per esempio, da fare a mano)...

e non la ritengo soddisfatta a priori.. poi infatti cerco un $b$ del tipo $b=kA$ e se alla fine troverò un $k$ maggiore od uguale ad 1 (che deve verificare anche le altre proprietà), avrò verificato anche questa condizione, in quanto
$b=kA & k>=1=>b>=A$ (ah la chiarezza delle formule, meglio di mille parole)...

[nickstu85]

Vediamo come viene...

Si deve avere $3*(sum_(i=0)^n 10^i*a_i)=2*(sum_(i=1)^n 10^i*a_(i-1)+a_n)$. Quindi risulta $(3*10^n-2)*a_n=2*(sum_(i=1)^n 10^i*a_(i-1)) - 3*(sum_(i=0)^n 10^i*a_i).$ Con qualche manipolazione RHS diventa $17*(sum_(i=0)^(n-1) 10^i*a_i)$ o equivalentemente $17*(a_(n-1) a_(n-2) ... a_1 a_0)$, quest'ultima notazione indica il numero di $n$ cifre $a_i$. Sappiamo che $a_n$ è $<=9$ quindi $17$ deve dividere $(3*10^n-2)$. Cerco il minimo $n$ per il quale risulti $3*10^n=2 (mod 17)$. Sapendo che l'inverso di $3 (mod17)$ è $6$, si deve risolvere $10^n=12 (mod 17)$. Un po' di simpatici conti e si trova $n=15$. Per trovare il minimo poniamo $a_n=1$ e troviamo le restanti cifre con $(3*10^15-2)/17$, l'idra a sedici teste che ho scritto poco sopra.
Se ho esagerato con la sintesi o con la distrazione, fatemi sapere . I problemi proposti da tom, come al solito, sono ottimi.

riguardo al problema precedente, potreste spiegarmi questo passaggio?
Sapendo che l'inverso di $3 (mod17)$ è $6$, si deve risolvere $10^n=12 (mod 17)$. Un po' di simpatici conti e si trova $n=15$

per il resto ce l'ho fatta da solo, ma quando dovevo trovare il numero divisibile per diciassette l'ho fatto per tentativi...

grazie, ciao a tutti

[Levacci]

Riconosco che l'aggettivo "simpatici" è fuorviante per due ragioni: si parla di contabilità e inoltre i conti sono un gran numero. Risolvendo il problema, sono riuscito a saltare qualche tentativo per merito di un paio di considerazioni euristiche. Dunque, si tratta di trovare un $n$ per il risulti $10^n=12 (mod 17)$. Mi sono accorto che $12$, guarda caso, è l'inverso di $10$, a questo aggiungi che $10^15 * 10 = 1 (mod 17)$ (grazie a Fermat e al suo piccolo teorema) e il gioco è fatto. Tutto questo, contando poco .

[nickstu85]

postate qualcos'altro... mi stavo divertendo un sacco

[fedeb]

volentieri
dimostrare che 41 non puo essere scritto come differenza di potenze di due e tre
in termini decenti, non esistono $n,m,j,k$ naturali tali che

$41=2^n-3^m$ e $41=3^j-2^k$

[Levacci]

Per il primo, lavoriamo modulo $8$. $41=1$ e $2^n=0$ per $n>2$. Dobbiamo quindi dimostrare che non esiste un $m$ per cui valga $-3^m=1 (mod 8)$. Per $m$ pari abbiamo $-3^(2a)=-(3^2)^a=-1 (mod 8)$. In modo analogo si fa vedere che per $m$ dispari il residuo è $-3$. Restano solo da verificare i casi i cui $n=0,1$ e questi si fanno allegramente via manu propria.

Presto anche il secondo problema, sempre su queste reti .