Sia S il più piccolo insieme di numeri interi positivi per cui valgano le seguenti proprietà:
P0: 2 ∈ S
P1: se n ∈ S, allora anche (n+5)² ∈ S
P2: se n² ∈ S, allora anche n ∈ S
Quali interi positivi si trovano in S?
(Nota: “il più piccolo” significa che S è contenuto in qualunque insieme per cui valgano le tre proprietà qui elencate)
(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p305.html; la risposta verrà postata lì il prossimo mercoledì. Problema A1 del Putnam 2017.)
Insomma il punto è trovare la chiusura transitiva dei tre assiomi…
La chiusura non include 1.
Come suggerisci, da P1+P2 si ottiene che se N è in S, N+5k è in S per ogni k>=0.
E:
* se 4 è in S, 3 è in S: 4 -> 9 -> 3.
* se 4 è in S, 6 è in S: 4 -> (somma 5 un po’ di volte) -> 29 -> applica P1 -> 34^2 -> (somma 5 un po’ di volte) -> 36^2 -> applica P2 -> 36 -> applica P2 -> 6.
L’osservazione qui (che non mi ricordo come si chiama né dove ho letto pre la prima volta) è che la differenza tra due quadrati di due numeri con le stesse cifre, ma uno con cifra delle unità 6 e un altro 4, è sempre un multiplo di 5. In altre parole dato un numero X4 (con X cifre a piacere), allora (X6^2 – X4^2) è divisibile per 5: (X6 + X4) * (X6-X4) e il primo fattore finisce per 0 e qundi include 5.
Quindi arrivare a un X4^2 mi permette di arrivare a X6^2 sommandoci 5 un po’ di volte.
A questo punto dimostriamo che 2 in S implica 4 in S: ovviamente ci devo arrivare applicando P2 a 16. Un modo che mi è venuto in mente è 2 -> P1 -> 49 -> somma 5 un po’ di volte -> 249 -> P1 -> 254^2 -> somma 5 un po’ di volte -> 256^2 -> 256 -> 16 -> 4.
Abbiamo quindi tutti gli interi positivi escluso 1 e i multipli di 5. Ora basta “solo” dimostrare che questo è minimale, ma è tardi e sono stanco :)