"Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Messaggio da **Admin** » ven set 08, 2006 10:17 pm

Admin ha scritto:Dalla sezione "Aritmetica russa"

Ordine delle cifre e divisibilità

Il numero naturale k ha la seguente proprietà: "Se n è divisibile per k allora il numero ottenuto da n invertendo l'ordine delle sue cifre è ancora divisibile per k".
Dimostrare che k è un divisore di 99.
(1° Tblisi 1967)

Indichiamo indichiamo con $inv(n)$ il numero che si ottiene da $n$ invertendo l'ordine delle sue cifre;

Sappiamo che un numero è divisibile per 9 se lo è la somma delle sue cifre;
quindi, nel nostro caso se $n$ è divisibile per 9, lo è anche $inv(n)$ , dato che le cifre sono le stesse (e quindi anche la somma di esse);

ancora, sappiamo che un numero è divisibile per 11 se lo è la somma a segni alterni delle sue cifre, da destra verso sinistra;
quindi, nel nostro caso se $n$ è divisibile per 11, lo è anche $inv(n)$ ;
infatti la somma a segni alterni delle cifre di $n$ , da dx a sx, è esattamente opposta a quella delle cifre di $inv(n)$ (se essa vale, per $n$ , ad es. 28, per $inv(n)$ varrà -28);
quindi se tale somma, per $n$ , è divisibile per 11, lo sarà anche la somma opposta, ossia anche $inv(n)$ .
Quindi per qualunque $n$ divisibile per un divisore di $9\cdot11=99$ lo sarà anche $inv(n)$ .

Purtroppo bisognerebbe anche dimostrare che i divisori di 99 sono gli unici valori possibili per k;
per il momento mi fermo qui!

Admin

Br1 · Messaggio da **Br1** » lun lug 23, 2007 3:01 pm

C'è qualcosa che non mi torna

Con un esempio numerico, la questione potrei
ridirla così (mi sembra):

Il numero naturale 6 ha la seguente proprietà:
"Se 612 è divisibile per 6 allora il numero ottenuto
da 612 invertendo l'ordine delle sue cifre [216] è
ancora divisibile per 6".
Dimostrare che 6 è un divisore di 99.

Chiaramente 612 e 216 sono multipli di 6, ma 99
non è divisibile per 6... E dunque?

Messaggio da **Admin** » lun lug 23, 2007 3:21 pm

Ciao Bruno,
in effetti il testo non è sufficientemente chiaro;
penso vada inteso così:

Il numero naturale k ha la seguente proprietà: "Per qualsiasi intero n divisibile per k allora il numero ottenuto da n invertendo l'ordine delle sue cifre è ancora divisibile per k".
Dimostrare che k è un divisore di 99.

Ciao
Admin

sprmnt21 · Messaggio da **sprmnt21** » gio mar 19, 2009 3:43 pm

Ciao a tutti, mi trovavo a ripassare di qua e' ho sbirciato un po' ...

volevo condividere con voi alcune mie considerazioni sul quesito.

1) il contro esempio di Br1 sarebbe valido se la tesi fosse: "Se n è divisibile per k E il numero ottenuto da n invertendo l'ordine delle sue cifre è ancora divisibile per k, dimostrare che k è un divisore di 99.".

2) forse per render la tesi piu' chiara potrebbe essere leggermente modificata cosi:

Il numero naturale k ha la seguente proprietà: "Se n è multiplo di k, allora il numero ottenuto da n invertendo l'ordine delle sue cifre è multiplo k". Dimostrare che k è un divisore di 99.

Quindi nemmeno la riformulazione di Admin va bene o comunque non e' lo stesso problema.

sprmnt21 · Messaggio da **sprmnt21** » ven mar 20, 2009 9:32 am

sprmnt21 ha scritto:Ciao a tutti, mi trovavo a ripassare di qua e' ho sbirciato un po' ...

volevo condividere con voi alcune mie considerazioni sul quesito.

1) il contro esempio di Br1 sarebbe valido se la tesi fosse: "Se n è divisibile per k E il numero ottenuto da n invertendo l'ordine delle sue cifre è ancora divisibile per k, dimostrare che k è un divisore di 99.".

2) forse per render la tesi piu' chiara potrebbe essere leggermente modificata cosi:

Il numero naturale k ha la seguente proprietà: "Se n è multiplo di k, allora il numero ottenuto da n invertendo l'ordine delle sue cifre è multiplo k". Dimostrare che k è un divisore di 99.

Quindi nemmeno la riformulazione di Admin va bene o comunque non e' lo stesso problema.

mi correggo, ora la formulazione di admin mi convince.

Io per trattarlo lo riformulerei cosi:

k e' t.c. per ogni a in Z, esiste m in Z t.c. (ak)' = m k. Provare che k e' divisore di 99.

[(n)' e' il numero intero ottenuto da n invertendo le sue cifre].

Messaggio da **Admin** » ven gen 01, 2010 9:29 pm

Salve,
stamattina girovagando in rete alla ricerca di un libro di "Computer Vision", mi sono imbattuto in un sito russo dove, tra le altre cose, era possibile scaricare un libro contenente alcuni dei problemi proposti alle olimpiadi sovietiche con relative soluzioni.
Ovviamente non ho resistito ed ho cercato subito la soluzione a questo problema irrisolto (questo topic è stato aperto più di 3 anni fa!).
Ed effettivamente c'era!

Spero non faccia un torto a nessuno riportando di seguito la soluzione.

Ecco la soluzione originale, in russo:
Immagine

Da quel che ho capito, dovrebbe essere più o meno così:

Consideriamo un numero qualsiasi le cui cifre più significative siano $500$ , ossia il numero $500abc...z$ .
Il numero che si ottiene invertendo le sue cifre sarà $z...bca005$ .
Supponiamo che entrambi siano divisibili per $k$ .
In questo caso sarà divisibile per $k$ anche la somma seguente:

$z...cba005000...000\/+\\ \qquad\qquad\qquad\qquad\qquad\quad 500abc...z =\\ -----------\\z...cba01000abc...z$

Invertendo le cifre di tale somma si ottiene il numero $z...cba01000abc...z$ , che quindi sarà anch'esso divisibile per $k$ (per le proprietà del numero $k$ ).
In questo caso sarà divisibile per $k$ anche la loro differenza, ossia:

$z...cba01000abc...z\/-\\ z...cba00010abc...z =\\ -----------\\\qquad\qquad\qquad\qquad\qquad\quad 990000...0$

Quindi ne concludiamo che $k$ è un divisore di $990000...0$ ( $99\cdot 10^n$ ).
Tuttavia $k$ non può essere un divisore di $10^n$ , dato che i multipli di $10$ non dividono mai contemporaneamente un numero ed il suo "inverso".
Dunque $k$ è un divisore di $99$ .

SE&O

Admin

fabtor · Messaggio da **fabtor** » sab mag 01, 2010 3:42 pm

Ho provato a prendere in mano anch'io questo problema e francamente la cosa mi lascia un po' perplesso (per non parlare della dimostrazione russa

) ...

Dall'analisi che ho fatto io sono portato a concludere che come è stato posto il problema inizialmente si può dimostrare che tale congettura è falsa.

A mio avviso la formulazione corretta che si può dimostrare (e che è più generale del problema visto che non pone limitazioni sulle cifre significative) è la seguente:

Dato un divisore K di 99 esistono coppie di numeri, i quali indicheremo con N e M, tali che:
1) N e M sono multipli di K,
2) M = rif(N)

dove rif(N) sta per riflesso di N.

Ciao

P.S. Peraltro la dimostrazione russa mi pare che ricordi molto quella del giochino matematico per cui si ottiene sempre 1089 se N è di 3 cifre con la cifra delle centinaia diversa di almeno due da quella dell'unità:

|643 -346| = 297

297 + 792 = 1089 (= 99x11)

Messaggio da **Admin** » dom mag 02, 2010 12:02 pm

Ciao Fabtor,
come ho scritto qualche messaggio più su, il problema va inteso come:

Admin ha scritto: Il numero naturale k ha la seguente proprietà: "Per qualsiasi intero n divisibile per k allora il numero ottenuto da n invertendo l'ordine delle sue cifre è ancora divisibile per k".
Dimostrare che k è un divisore di 99.

Oppure come lo ha riformulato sprmnt21:

sprmnt21 ha scritto:k e' t.c. per ogni a in Z, esiste m in Z t.c. (ak)' = m k. Provare che k e' divisore di 99.

Tu dici:

fabtor ha scritto:A mio avviso la formulazione corretta che si può dimostrare (e che è più generale del problema visto che non pone limitazioni sulle cifre significative) è la seguente:

Dato un divisore K di 99 esistono coppie di numeri, i quali indicheremo con N e M, tali che:
1) N e M sono multipli di K,
2) M = rif(N)

dove rif(N) sta per riflesso di N.

In realtà, questo è un'altro problema, facilmente dimostrabile, per un divisore di un qualsiasi numero (non solo 99): basta trovare delle coppie valide.

Nel primo post, io avevo dimostrato che:

Admin ha scritto:per qualunque n divisibile per un divisore di $9\cdot11=99$ lo sarà anche $inv(n)$ .
Purtroppo bisognerebbe anche dimostrare che i divisori di 99 sono gli unici valori possibili per k.

Ecco, la dimostrazione russa, dimostra proprio che i divisori di 99 sono gli unici valori possibili per k.
Il vincolo di considerare solo numeri con le cifre più significative uguali a $500$ non è restrittivo, perchè l'insieme dei numeri che hanno le cifre significative pari a 500, sarà formato da infiniti numeri, e vi saranno in esso infiniti numeri divisibili per $k$ , con $k {\tiny\in} \mathbb{Z}$ .

Ciao
Admin

fabtor · Messaggio da **fabtor** » mer mag 05, 2010 2:08 pm

Mmmh... Prometto che mi riguarderò bene tutta la dimostrazione, tuttavia non so perchè ma c'è qualcosa che non mi convince al 100%, provo a spiegarmi: ho una strana sensazione che da qualche parte ci sia una sorta di "forzatura" cmq appena posso mi prendo un po' di tempo per ragionarci sopra.

fabtor · Messaggio da **fabtor** » gio mag 06, 2010 10:11 am

Se ho capito bene la scelta del 500 non è restrittiva per via degli infiniti numeri che possono avere come cifre più significative proprio 500.

Di conseguenza se tale scelta non fosse vincolante ai fini del ragionamento anche la scelta di 500 non dovrebbe esserlo per cui a rigor di logica protremmo scegliere un qualunque numero che abbia come prime tre cifre delle cifre qualunque ed il ragionamento, se corretto, non dovrebbe venire compromesso.

Se fin qui non ho detto castronerie quindi potremmo scegliere come numero iniziale un numero
del tipo 600abc...z per esempio.

Tuttavia seguendo il ragionamento russo proposto alla fine il risultato ottenuto è

1179*10^n tuttavia a questo punto poichè 1179 = 9*131 che non è un multiplo di 99 e a meno di non considerare solo il 9 e trattare il 131 come il 10^n (ma è lecito farlo?) i conti non mi tornano più.

A questo punto mi serve aiuto: se il mio ragionamento è corretto la dimostrazione russa è valida solo per un caso particolare, cioè solo per quegli infiniti numeri che hanno come cifre più significative 500 poichè tutti gli altri numeri sono anch'essi infiniti ma con un ordine di grandezza più grande. (Naturalmente potendo trattare il 131 come il 10^n tutto si potrebbe risolvere, ma siamo sicuri che solo 9 e 11 siano i numeri primi che possano esserere al contempo divisori di n e inv(n) ? ).

Inoltre poichè la sottrazione finale è sempre del tipo X00-X se la prima cifra significativa è < di 5
e del tipo XY00-YX se la prima cifra significativa è > (o al più uguale) a 5
e tali sottrazioni danno sempre un numero divisibile per 9 la scelta di 99 = 9X11 mi sembra atta a contenere quell'undici che il tipo di dimostrazionezione riportato non contempla.

Attendo lumi

.

Messaggio da **Admin** » lun mag 10, 2010 11:18 pm

Ciao fabtor,
mi sembra che anche considerando numeri del tipo $600abc...z$ il procedimento "russo" porti al risultato finale di $99000...0$ .

Comunque in teoria è possibile scegliere numeri di qualsivoglia tipo, solo che così facendo, in gran parte dei casi si otterranno dei risultati più generici, ossia si otterranno al termine del metodo "russo" numeri che ammettono più divisori, oltre a quelli di 99.
La scelta di 500 come cifre significative non è casuale, ed è mirata proprio ad escludere tutti gli altri divisori.

Ciao
Admin

fabtor · Messaggio da **fabtor** » mar mag 11, 2010 7:32 am

Admin ha scritto:Ciao fabtor,
mi sembra che anche considerando numeri del tipo $600abc...z$ il procedimento "russo" porti al risultato finale di $99000...0$ .

Comunque in teoria è possibile scegliere numeri di qualsivoglia tipo, solo che così facendo, in gran parte dei casi si otterranno dei risultati più generici, ossia si otterranno al termine del metodo "russo" numeri che ammettono più divisori, oltre a quelli di 99.
La scelta di 500 come cifre significative non è casuale, ed è mirata proprio ad escludere tutti gli altri divisori.

Ciao
Admin

Ho verificato e confermo che solo con il 500abc...xyz (testando solo i numri del tipo K00abc...xyz con 1<K <9) si arriva a 99000...0000 tuttavia, poichè tutti i numeri ottenuti "in vece " di 99000...0000 sono cmq sempre divisibili almeno per 9 sono cmq scrivibili nella forma 9^N x Kx10^M per cui se sitratta K come già si tratta il 10^M rimane che il divisore di U e di Inv(U) è 9 che è divisore di 99... mi rimane cmq il dubbio che si possa trattare "così a cuor leggero" K come 10^M.

Spero di non aver fatto macelli o creato troppa confusione cambiando il nome alle variabili.

Messaggio da **Admin** » dom mag 23, 2010 10:43 am

Ciao fabtor,
provo a mettere un pò di ordine ai vari post con una dimostrazione completa, basata sul procedimento "russo".

Dunque, per dimostrare che $k$ è un divisore di $99$ , ci basta dimostrare che $k$ non può assumere altri valori se non i divisori di $99$ .
Per far ciò ci basta dimostrare che per ogni intero $m$ diverso dai divisori di $99$ , esiste almeno un numero intero $n$ , divisibile per $m$ , il cui inverso non lo sia (ad es. per dimostrare che $k$ non può valere $183$ ci basta trovare un intero $n$ divisibile per $183$ , il cui inverso non lo sia).
Dimostriamo ciò.
Consideriamo ora l'insieme formato da tutti gli interi di tipo $500abc...z$ .
Esso conterrà infiniti numeri divisibile per $2$ , per $3$ , per $4$ , etc.;
più in generale conterrà infiniti numeri divisibili per $m$ , con $m \small{\in} \mathbb{Z}$ .
Infatti possiamo facilmente individuare un intero di tipo $500abc...z$ , divisibile per $m$ , attraverso la seguente formula:
$n\/=\/500\cdot {10}^c+m-[(500\cdot {10}^c) \bmod m]$
dove $c$ è il numero di cifre del numero $m$ (ad es. per $m=183$ otteniamo il numero $n\/=\/500\cdot {10}^3+183-44\/=\/500139$ , che è appunto divisibile per $183$ ).
A questo punto il procedimento "russo" ci permette di affermare che, se un numero di tipo $500abc...z$ ed il suo inverso sono divisibili per $k$ , allora $k$ è un divisore di $99\cdot{10}^b\/=\/99\cdot 2^b\cdot 5^b$ .
Possiamo evidentemente escludere $2^b$ e $5^b$ come possibili valori di $k$ , dal momento che esistono infiniti interi divisibili per $2^b$ e $5^b$ il cui inverso non lo sia (basta considerare interi con la prima cifra non pari nel caso di $2^b$ , ed interi con la prima cifra diversa da $5$ nel caso di $5^b$ ).
Quindi ricapitolando, se $500abc...z$ e il suo inverso sono divisibili per $k$ , allora $k$ è un divisore di $99$ .
Ma siamo sicuri che non ci siano altri possibili valori per $k$ ?
Si, ne siamo sicuri, perchè se ad es. $k$ potesse valere $183$ , vuol dire che il numero $n\/=\/500\cdot {10}^3+183-44\/=\/500139$ sarebbe divisibile per $k$ , e lo sarebbe anche il suo inverso;
di conseguenza, alla fine del procedimento "russo", dovremmo ottenere un numero divisibile per $183$ .
Invece otteniamo sempre il numero $99\cdot {10}^b$ .
Lo stesso ragionamento vale per qualsiasi numero diverso dai divisori di $99$ .
Ciò significa che per ogni intero $m$ , diverso da un divisore di $99$ , abbiamo un controesempio, ossia almeno un intero $n$ divisibile per $m$ , il cui inverso non lo sia.
Dunque $k$ può essere solo un divisore di $99$ .

QED

SE&O

Ciao
Admin

fabtor · Messaggio da **fabtor** » lun mag 24, 2010 6:51 pm

Ok. Ora mi hai convinto

Grazie mille.

"Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

"Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità

Re: "Aritmetica Russa" - 1. Ordine delle cifre e divisibilità