Ironia Matematica

Avverto i gentili lettori che, solo coloro che si divertono con numeri e dimostrazioni, potrebbe trovare il seguente post interessante. Per questo motivo ne sconsiglio a tutti la lettura.
Inoltre il post è particolarmente lungo... In genere suddivido tali post in più puntate però visto che l'argomento non troppo esaltante credo sia meglio annoiare i lettori in un colpo solo: dopotutto il post è diviso in numerosi passi e, chi lo preferisce, può leggersi un passo alla volta...

Nel “Corto” dello scorso 26 aprile, Insonnia matematica, scrissi che ero rimasto sveglio pensando a un problemino matematico e che, se ne venivo a capo, ci avrei forse fatto un post.
In realtà il giorno dopo lo risolsi ma la mia dimostrazione è così ingarbugliata da risultare divertente: di seguito quindi i vari passaggi del mio ragionare.

Il Problema
Il problema è molto semplice ma, che io sappia, non esiste una terminologia adatta a descriverlo efficacemente. Per questo partirò col descrivere il caso pratico che me lo ha inspirato.
Dunque, io ho una cartella con N sottocartelle. Periodicamente voglio controllarle tutte; la soluzione di esaminarle l'una dopo l'altro è senza dubbio fattibile solo che, per i miei gusti, è troppo noiosa. Così scelgo un numero primo piccolo (ad esempio 13) e controllo la tredicesima sottocartella, poi la ventiseiesima e così via: quando arrivo all'ultima continuo a contare dall'inizio, fino ad arrivare a 13, dal numero a cui ero arrivato. Ad esempio, se ho 30 sottocartelle potrei enumerarle usando il numero 7: in questa maniera guarderei la sottocartella 7, poi la 14, la 21 e la 28. Qui conterei fino a 2 per arrivare alla sottocartella 30 e poi ripartirei dalla sottocartella 1 ma contando a partire da 3: in pratica dopo la sottocartella 28, verrebbe la 5, poi da qui normalmente, la 12, la 19, la 26 e, da capo, la 3, etc.
Uso un numero primo perché mi pare di ricordare, dai tempi dell'università, che in questa maniera riesco a enumerare tutte le sottocartelle (ovviamente se il numero di cartelle non è multiplo del numero primo da me scelto! Es. 70 sottocartelle e 7 come numero primo...).
Il problema che mi sono posto è quindi il seguente: “Dato un numero N come devo scegliere il numero I affinché I possa “enumerare” completamente N?” Dove con “enumerare” intendo il concetto espresso nell'esempio delle sottocartelle, ovvero riuscire a visitare tutte le cartelline controllandone 1 ogni I e, una volta arrivato all'ultima cartella, ripartendo a contare dall'inizio come visto.

Passo 1
Il primo passo che ho fatto è stato quello di rendermi conto che se il massimo comune divisore (MCD) fra I e N è maggiore di 1, allora certamente I non potrà enumerare completamente N. La dimostrazione geometrica è particolarmente informale (e in effetti il seguente risultato non viene utilizzato nella dimostrazione finale: trovo però che aiuti a visualizzare il problema...).

T0:
Se MCD(I,N)=K>1 allora I non enumera completamente N.
Dimostrazione:
Per definizione di MCD, K divide sia I che N. Entrambi questi numeri possono quindi essere immaginati come rettangoli con un lato di lunghezza K e area rispettivamente pari ad I ed N. Vedi figura:

Visto che entrambi i rettangoli hanno un lato della stessa dimensione allora posso sovrapporli nel seguente modo:

Alla prima iterazione verrà quindi visitata la cartella contrassegnata dal cerchietto azzurro. Alla successiva ripartiremo a contare fino ad I da quel punto. Vedi figura:

Alla seconda iterazione un nuovo cerchietto verrà lasciato. Alla terza, visto che il rettangolo N è “finito”, il cerchietto azzurro verrà lasciato all'inizio del rettangolo N e così via.
È quindi evidente che i cerchietti azzurri cadranno solamente sull'ultima riga di N mentre gli elementi sotto la riga nera disegnata non verranno mai raggiunti.
In altre parole I non enumera completamente N.

Passo 2
Il passo precedente ci ha detto come NON deve essere I per poter enumerare N. Non abbiamo però assolutamente chiarito come deve essere! In particolare sappiamo che se MCD(I,N)>1 allora sicuramente I non enumera N ma ancora non sappiamo cosa succede quando MCD(I,N)=1.
Il seguente risultato ci servirà in seguito. Prima mostro una dimostrazione geometrica e di seguito una algebrica più formale.

T1:
Se MCD(I,N)=1 allora J=N Mod I non è divisore di I
Dimostrazione informale:
Supponiamo per assurdo che J divida I. Allora I potrebbe essere visualizzato come un rettangolo di lati J e I/J (nota: I/J corrisponde a un numero intero).
Adesso aggiungiamo sul rettangolo I gli elementi di N (non scrivo il rettangolo N perché ancora non sappiamo se N sia esattamente divisibile per J). Vedi figura:

Come si vide dall'immagine non conosciamo la forma della parte “finale” di N: non sappiamo cioè quanti quadratini (=unità) avanzano.
Ora ricordando però che N Mod I=J sappiamo che I sta “dentro” N un numero X di volte (non è importante quante) e che avanza J. In altre parole, la parte a destra indeterminata di N equivale esattamente a J. Vedi figura:

Questo significa che anche N, oltre a I, è divisibile per J. Ma questo è assurdo perché MCD(I,J)=1
Quindi J non è un divisore di I.

Dimostrazione formale:
Supponiamo per assurdo che J sia un divisore di I.
Allora I/J è un intero. (1)
Per ipotesi, dato che J=N Mod I, si ha che N=I*X+J (dove X è un intero). (2)
Allora N/J sarebbe uguale a (I*X+J)/J cioè (I/J)*X+1.
Per (1) e (2) sappiamo che sia (I/J) che X sono numeri interi e quindi anche il loro prodotto + 1 sarà ancora intero.
Questo equivale a dire che J è un divisore anche per N ma ciò è assurdo perché MCD(I,N) è 1.
Quindi J non è un divisore di I. CVD

Passo 3
Un piccolo corollario è necessario...

C1
Se MCD(I,N)=1 e J=N Mod I allora MCD(I,J)=1
Dimostrazione:
Supponiamo per assurdo che MCD(I,J)=K>1.
Allora con dimostrazione analoga alla precedente (sostituendo J con K) si arriverebbe all'assurdo che anche N è divisibile per K e pertanto MCD(I,J)=1.

{Modificato (28/4/2013): Se per assurdo assumo MCD(I,J)=K>1 questo significa che I/K e J/K sono interi.
Da J=N Mod I si ricava che N=I*X+J quindi N/K= (I*X)/K+J/K = (I/K)*X+J/K
Ma X è intero per definizione di Mod, e I/K e J/K sono interi per l'ipotesi assurda: da questo deriverebbe che anche N/K è un numero intero ma questo è in contraddizioni con MCD(I,N)=1 perché sia I che N sarebbero divisibili per K!
Quindi MCD(I,J) deve essere 1.
}

Passo 4
Un ultimo, apparentemente strano, teorema è necessario: il suo scopo diventerà chiaro successivamente...

T2:
Se MCD(I,J)=1 e I>J allora MCD(I,I-J)=1
Dimostrazione Informale:
Supponiamo per assurdo che MCD(I,I-J)=K>1
Allora sarebbe possibile visualizzare i numeri I e (I-J) come due rettangoli con un lato pari a K. Vedi la figura:

D'altra parte I deve essere uguale a (I-J) + J e quindi J è uguale al rettangolo I meno il rettangolo (I-J) ed è quindi uguale al rettangolo J disegnato in figura e divisibile per K (di lato K).
Ciò però è assurdo perché MCD(I,J)=1 e non K. Quindi MCD(I,I-J)=1

Dimostrazione formale:
Supponiamo per assurdo che MCD(I,I-J)=K>1
Quindi, per definizione di MCD, I/K e (I-J)/K sono interi (1).
J=I-(I-J)
Dividendo entrambi i membri per K si ottiene:
J/K=I/K-(I-J)/K
ma I/K e (I-J)/K per (1) sono interi e di conseguenza lo è anche la loro differenza. (2)
Allora, per (2), anche J/K è intero: questo significa che sia J che I sono divisibili per K: questo però è assurdo in quanto MCD(I,J)=1. Quindi MCD(I,I-J)=1. CVD

Passo 4b
Ehm... fa comodo inserire un lemmino a questo punto prima del passo finale...

L1
Se MCD(I,N)=1 e I>1 allora N Mod I <>0
Dimostrazione:
La dimostrazione è banale: N Mod I è uguale a zero solo se I è un divisore di N, ma per ipotesi questo non è il caso in quanto MCD(I,N)=1 e I>1

Passo 5
Adesso qualche osservazione.

O1
I enumera N se I-(N Mod I) enumera I.

Come si vede dalla figura, N è diviso in 4 intervalli di ampiezza I di cui i primi 3 sono completi mentre l'ultimo non lo è e ha dimensione pari a N Mod I.
Dalla figura si vede come ciascun valore enumerato (marcato con un cerchietto) nel primo intervallo sarà replicato negli intervalli successivi. Che il quarto e ultimo intervallo sia incompleto è irrilevante.
Si può inoltre vedere che terminata la prima iterazione, quella con i cerchietti neri, inizia la seconda iterazione con i cerchietti verdi. Limitandoci al primo intervallo si può osservare come i cerchietti marcati all'interno di esso si comportano come si si contasse I-(N Mod I) elementi ogni volta. Da qui l'osservazione O1.
Un esempio: supponiamo N=19 e I=7. Avremo due intervalli completi di 7 elementi e un terzo di 5.
Alla prima iterazione verranno enumerati gli elementi 7 e 14, poi, visto che il 21 non esiste si passerà al 2. Facciamo un'altra iterazione: dopo il 2 avremo il 9, poi il 16 e poi, visto che N termina a 19, il 4.
Se ci limitiamo a guardare il primo intervallo si vede che il primo valore a essere enumerato è il 7, poi il 2, poi il 4 etc... Cioè ci enumeriamo un elemento ogni due nel primo intervallo.
Questo corrisponde a quanto indicato dalla formula, cioè: I-(N Mod I) ovvero 7-(19 Mod 7)=7-5=2

O2
Sicuramente I enumera N quando N Mod I = 1.
È infatti immediato verificare che ad ogni iterazione vengono marcati gli elementi alla sinistra di quelli marcati nell'iterazione precedente.
Esempio numerico: N=15 e I=7 (cioè N Mod I = 15 Mod 7 = 1). Alla prima iterazione vengono marcati gli elementi 7 e 14, alla seconda iterazione gli elementi 6 e 13 e così via.

O3
Per O1 sappiamo che I enumera N quando I-(N Mod I) enumera I.
All'iterazione ennesima ci ritroveremo quindi a verificare se In enumera Nn con la particolarità che In < I(n-1) e Nn < N[n-1] per costruzione. Infatti si può osservare che, per costruzione, I-(N Mod I) è sempre < I purchè (N Mod I) sia diverso da zero. Mettiamo tutto insieme
L'idea è di dimostrare che per enumerare N basta prendere I tale che MCD(I,N)=1.
Ovvero: Se MCD(I,N)=1 allora I enumera N.

Dimostrazione:
Per (O1) dimostrare che I enumera N equivale a dimostrare che I-(N Mod I) enumera I.
poiché MCD(I,N)=1 allora per (C1) MCD(N Mod I, I)=1
poiché MCD(N Mod I, I)=1 allora per (T2) MCD(I,I-(N Mod I))=1
Il fatto che MCD(I,I-(N Mod I))=1 implica un paio di cose: 1) Possiamo applicare iterativamente (O1) sicuri di andare a enumerare sempre due numeri tali che il loro MCD è sempre 1; 2) Per (O3) e (L1) sappiamo che, ad ogni iterazione, In sarà strettamente minore di I(n-1) ma che comunque Nn Mod In sarà diverso da 0.
Di conseguenza, dopo al massimo I-2 iterazioni, In sarà pari a 2 e quindi Nn Mod In potrà essere solo 1 o 0. Ma non sarà mai 0 per (L1) e quindi dovrà essere 1.
Ma per (O2) dire che Nn Mod In =1 equivale a dire che In enumera Nn; questo a sua volta, per (O1), equivale a dire che I enumera N che è ciò che volevamo dimostrare. Semplice, no!!?

Conclusione
Temo che il problema abbia una soluzione algebrica molto molto più semplice della mia!
Io però non ho voluto cercare su internet e mi sono divertito a ragionare autonomamente inventandomi qualche dimostrazione qua e là.
Sono inoltre consapevole che le mie dimostrazioni (a parte un paio di eccezioni) sono alquanto informali e farebbero storcere il naso a un Matematico con la M maiuscola...
Che dire? Io sono contento di essere riuscito a soddisfare, nonostante le elementari conoscenze matematiche, la mia curiosità iniziale.
L'ironia del titolo sta nel fatto che, ciò che a me ha richiesto 3 o 4 ore di ragionamenti e altrettante pagine di dimostrazioni, su qualsiasi libro di algebra sarà riassunto in meno di mezza paginetta!

Share