Due strade

[axpgn]

Consideriamo i numeri generati dalle seguenti espressioni: $n -> 2n+2$ e $n -> 6n+6$, dove $n$ è un intero e il punto di partenza è $n=1$ per entrambi.

Dopo il primo passo si ottengono i numeri $4$ e $12$, alla seconda generazione abbiamo $10, 30, 26, 78$, alla terza $22, 66, 62, 186, 54, 162, 158, 474$ e così via.

Se li riordiniamo tutti abbiamo la seguente sequenza $1, 4, 10, 12, 22, 26, 30, 54, 62, 66, 68, 78, 158, 162, 186, 474, ...$

Capiterà mai, prima o poi, che (almeno) un numero appaia due volte? Oltre all'$1$ s'intende


Se poi avete tempo potete provare con queste altre ...

- $n -> 2n+2$ e $n -> n+1$
- $n -> 2n+2$ e $n -> 4n+4$
- $n -> 2n+2$ e $n -> 5n+5$
- $n -> 2n+2$ e $n -> 7n+7$


Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

No!
Supponiamo che esista almeno una soluzione \( n,m \), allora abbiamo che \( 2n+2 = 6m+6 \) da cui deduciamo che \( n=3m+2 \equiv 2 \mod 3 \) pertanto abbiamo che \( n= 2k_0 +2 \) con \( k_0 \equiv 0 \mod 3 \). Pertanto \(k_0= 3\ell \) da cui otteniamo che \( n=6\ell + 2 \) e \( m =2 \ell \). Siccome abbiamo che \( n,m \) sono anche a loro volta della forma \( 2x+2 \) oppure \(6x+6\) per qualche \(x \) abbiamo che \( n=2(3\ell)+2 \) quindi abbiamo che \( x=3\ell \) ma anche \( x \) è di una di queste due forme, da cui deduciamo che se \( 3 \ell = 2n_1 + 2 \) allora \( n_1 = 3 m_1 + 2 \) da cui \( 2n_1 + 2 = 3 \ell = 6m_1 + 6 \) da cui abbiamo un'altra soluzione con \( n_1 < n \) e \( m_1 < m \) e per la discesa infinita concludiamo che \(n,m \) non esistono.
Quindi abbiamo che \( 3 \ell = 6m_1 + 6 \) da cui \( \ell= 2m_1 + 2 \). Ora siccome \( m=2 \ell \) è anche lui di una di quella forma abbiamo che \( m=2(\ell -1 ) + 2 \) oppure \( m= 6 \left( \ell/3 -1 \right) + 6 \). Dove \( \ell-1 \) oppure rispettivamente \( \left( \ell/3 -1 \right) \) sono della forma \( 2x+2 \) oppure \(6x+6 \). Nel primo caso se \( m=2(\ell -1 ) + 2 \) abbiamo che \( \ell-1=2m_1 + 1 \equiv 1 \mod 2 \) cosa che non è possibile poiché \( 2x+2 \equiv 6x+6 \equiv 0 \mod 2 \).

Edit:
Penso che quest'ultima riga sia sbagliata in realtà perché \( \ell \) non deve necessariamente stare nella successione. Ma si può risolvere comunque in altro modo
-------------------------------
Allora abbiamo che \( m= 6 \left( \ell/3 -1 \right) + 6 \) quindi \( 3 \mid \ell \) da cui \( m_1 = 3n_1 + 2 \) da cui di nuovo abbiamo che \( \ell = 2m_1 + 2 = 6n_1 + 6 \) e di nuovo per la discesa infinita abbiamo un assurdo.
--------------------------------

Conclusione che penso sia giusta:
Allora abbiamo che \( m= 6 \left( \ell/3 -1 \right) + 6 \) quindi \( 3 \mid \ell \) da cui \( m_1 = 3n_1 + 2 \) da cui di nuovo abbiamo che \( \ell = 2m_1 + 2 = 6n_1 + 6 \) e dunque \( \ell/3-1 = 2n_1 + 1 \equiv 1 \mod 2 \) assurdo poiché \( \ell/3-1 \) dev' essere della forma \(2x+2 \) o \( 6x+6\).

[axpgn]

@3m0o

C'ho capito poco (come al solito d'altronde ), prima o poi mi perdo ... (anche perché hai scritto tre finali diversi, dovresti postare la versione definitiva in un nuovo messaggio, non modificando il vecchio però).
Detto ciò, devo aggiungere però che non so se esista una soluzione (e neppure se sia possibile dimostrarlo). Lo dico perché l'autore non l'ha ancora trovata, pur con l'ausilio di un computer.
"E ti credo" mi dirai tu "ti ho appena dimostrato che non esiste"
No, voglio dire che se esistesse una dimostrazione, mi parrebbe strano che l'autore, un matematico ed i suoi colleghi non l'abbiano trovata.
Per inciso, tre delle altre sequenze hanno sicuramente soluzione (due alla portata).

Come detto, nella tua dimostrazione mi perdo ma, per esempio, perché affermi che $n_1=3m_1+2$?

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Premetto che sta volta ti do ragione sul fatto che sono stato confusionario. Dal momento che tu mi dici che l'autore non ha trovato una soluzione probabilmente il mio ragionamento contiene un errore. Comunque sia io non lo trovo.
Cercherò di essere più chiaro
Da quello che ho capito, abbiamo due successioni, \( 2n+2 \), \(6n+6\), entrambe partono con \( n =1 \) e poi \( n \) è o della forma \( 2x+2 \) oppure \( 6x+6 \), nel senso che sostituisci ad \( n \) nelle due successioni i termini precedenti di entrambe le forme.

Ora supponiamo per assurdo che esiste una soluzione che renda \( 2n+2 = 6m+6 \).
Step 1:
Allora abbiamo che esiste la soluzione più piccola, minimale tra gli interi positivi, consideriamo questa soluzione minimale. Deduciamo ( e penso sia chiaro) che \( n=3m+2 \equiv 2 \mod 3 \).
Ora questo è possibile solo se \( n =2k_0 + 2 \) perché \( n \) dev'essere o della forma \( 2x+2 \) oppure della forma \( 6x+6 \), se fosse della forma \( 6x + 6 \) avremmo che \( n \equiv 0 \mod 3 \) quindi per forza di cose è della forma \( 2x+2 \). Dico quindi che \(n =2k_0+2 \) per qualche \( k_0 \).
Ora siccome ho un numero \( 2k_0 + 2 \equiv 2 \mod 3 \), poiché \( n \equiv 2 \mod 3 \) allora abbiamo tre possibili casi:
Caso 1.1: \( k_0 =3 \ell \)
Ed in questo caso abbiamo che \( n= 6 \ell + 2 \equiv 2 \mod 3 \), ed è consistente con il fatto che \( n \equiv 2 \mod 3 \)

Caso 1.2: \( k_0 = 3 \ell + 1 \)
Ed in questo caso abbiamo che \( n= 6 \ell +4 \equiv 1 \mod 3 \), e non è consistente con il fatto che \( n \equiv 2 \mod 3 \)

Caso 1.3: \( k_0 = 3\ell + 2 \).
Ed in questo caso abbiamo che \( n= 6 \ell + 6 \equiv 0 \mod 3 \), e non è consistente con il fatto che \( n \equiv 2 \mod 3 \).

Concludiamo che \( n= 2k_0 + 2 \) dove \( k_0 = 3 \ell \).

Conclusione step 1: \( n= 6 \ell + 2 \) ed \(m =2 \ell \).

Domanda 1: Fin qui ci sei?

Step 2:
Per semplice sostituzione otteniamo che \( n= 6 \ell + 2 \) e dunque \( 6 \ell + 2 = 3m+2 \) da cui deduciamo che \( m=2 \ell \). Ora però se \( 2n+2 \) e \(6m+6 \) sono numeri della nostra successione ordinata vuol dire che \( n \) (rispettivamente \(m \)) è della forma \( 2x_n + 2 \) oppure \( 6x_n+6 \) (rispettivamente \(m \) è della forma \( 2x_m + 2 \) oppure \( 6x_m+6 \) ). A loro volta abbiamo che \( x_n \) (rispettivamente \( x_m \)) devono essere della forma \( 2y_n+2 \) oppure \( 6y_n + 6 \) (rispettivamente della forma \( 2y_m+2 \) oppure \( 6y_m + 6 \) ), etc.

Caso 2.1: \( n = 6x_n + 6 \).
Questo vuol dire che che \(n= 6\ell + 2 =6x_n + 6 \). Abbiamo che \( \ell \) è fissato, e da qui deduciamo facilmente che \( 6 \ell - 4 =6x_n \). Però questa equazione non ha soluzioni negli interi (rispetto a \( x_n \) ) poiché \( \ell \) è un intero e abbiamo che \( \ell - 4/6 \) non è intero.
Concludiamo che il caso 2.1 non è possibile.

Conclusione: grazie al caso 2.1 deduciamo che la sola possibilità è il caso 2.2 ovvero \( n= 2x_n + 2 \).

Domanda 2: Fin qui ci sei?

Step 3:
Da step 2 deduciamo che \( 6 \ell + 2 = 2x_n + 2 \), da cui deduciamo che \( x_n = 3 \ell \). Poiché \( x_n \) deve essere della forma \( 2y_n+2 \) oppure \( 6y_n + 6 \), in modo analogo per \(x_m \), abbiamo allora 4 casi

Caso 3.1:
\(x_n = 2y_n + 2 \) e \( x_m =2y_m + 2 \)

Caso 3.2:
\(x_n = 2y_n + 2 \) e \( x_m =6y_m + 6 \)

Caso 3.3:
\(x_n = 6y_n + 6 \) e \( x_m =2y_m + 2 \)

Caso 3.4:
\(x_n = 6y_n + 6 \) e \( x_m =6y_m + 6 \)

Domanda 3: fin qui ci sei?

Step 4:
Lemma 4.1: Abbiamo che \( x_n \) non è della forma \( 6k+6 \) indipendentemente della forma che possiede \(k \).
Lemma 4.1 esclude automaticamente i casi 3.3 e 3.4.

Dimostrazione Lemma 4.1:
Abbiamo che \( m=2\ell \) e supponiamo che \( x_n=6k+6 \) poiché abbiamo che \( x_n = 3 \ell \) deduciamo che \( \ell = 2k+2 \).
Caso 1:
Supponiamo che \( m = 2x_m + 2 \) allora abbiamo che \( x_m = \ell -1 \) ma \( x_m = 2k+2 - 1 = 2k+1 \equiv 1 \mod 2 \) e in entrambi (3.3 e 3.4) abbiamo che \( x_m \equiv 0 \mod 2 \). Assurdo
Caso 2:
Supponiamo che \( m = 6x_m + 6 \) allora abbiamo che \( x_m = \ell/3 -1 \) da cui deduciamo che \( x_m = (2k+2)/3 -1 \). Se \( 3 \not\mid (2k+2) \) non è possibile ma allora abbiamo che \( 3 \mid (2k+2) \) da cui deduciamo (per un ragionamento analogo a quello di step 1) che \( k = 3k_1 + 2 \)[nota]Infatti poiché \( 3 \mid (2k+2) \) abbiamo che \( 2k+2 \equiv 0 \mod 3 \). Per \(k \) abbiamo tre possibilità, \( k=3k_1 \), \(k=3k_1 + 1 \) oppure \( 3k_1 +2 \). Nei primi due casi abbiamo rispettivamente \( 2k+2 \equiv 2 \mod 3 \) e \( 2k+2 \equiv 1 \mod 3 \), resta dunque come unica possibilità \( k=3k_1 + 2 \) che porta appunto a \( 2k+2 \equiv 0 \mod 3 \).[/nota] da cui deduciamo che
\[ x_m = (6k_1+6)/3 - 1 = 2k_1 + 2 -1 = 2k_1 + 1 \equiv 1 \mod 2 \]
in entrambi (3.3 e 3.4) abbiamo che \( x_m \equiv 0 \mod 2 \). Assurdo

Sia nel caso 1 che nel caso 2 abbiamo un assurdo poiché indipendentemente dal fatto che \( x_m = 2y_m+2 \) che \( x_m =6y_m + 6 \) abbiamo che \( x_m \equiv 0 \mod 2 \).
Questo dimostra Lemma 1.

Domanda 4: Fin qui ci sei?

Step 5:
Abbiamo dimostrato che i casi 3.3 e 3.4 non sono possibili supponiamo quindi di trovarci nel caso 3.1 oppure 3.2, questo vuol dire che \( x_n = 3 \ell = 2y_n + 2 \) ma allo stesso tempo abbiamo che \( n=2x_n + 2 \) (vedi step 2) quindi \( n= 2 (3 \ell) + 2 \) pertanto siccome \( 2y_n + 2 = 3 \ell \equiv 0 \mod 3 \) abbiamo 3 casi

Caso 5.1:
Se \( y_n = 3 k_2 \) abbiamo che \( 2y_n+2=6k_2+2 \equiv 2 \mod 3 \) che non è possibile.
Caso 5.2:
Se \( y_n = 3 k_2 +1 \) abbiamo che \( 2y_n+2=6k_2+4 \equiv 1 \mod 3 \) che non è possibile.
Caso 5.3:
Se \( y_n = 3 k_2 +2 \) abbiamo che \( 2y_n+2=6k_2+6 \equiv 0 \mod 3 \) che l'unico caso possibile.

Però se \( y_n = 3k_2 + 2 \) abbiamo che \( 3 \ell = 6k_2 + 6\). Concludiamo grazie al Lemma 4.1 che non sono possibili nemmeno i casi 3.1 e 3.2

Assurdo

Questo termina la dimostrazione.

Ps: se è giusta ditemelo che la giro all'autore e ai suoi colleghi

[axpgn]

Mi prendo tutto il fine settimana (e oltre) per capirla (non per demeriti tuoi ma per incapacità mia sia chiaro )

"3m0o":Ps: se è giusta ditemelo che la giro all'autore e ai suoi colleghi

Oh, questo è sicuro

È carino il fatto che metti tutto sotto spoiler ma la nota no, quella spunta fuori


Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":Mi prendo tutto il fine settimana (e oltre) per capirla (non per demeriti tuoi ma per incapacità mia sia chiaro )

Certo.

"axpgn":
[quote="3m0o"]Ps: se è giusta ditemelo che la giro all'autore e ai suoi colleghi

Oh, questo è sicuro
[/quote]
Se posso chiedere chi è? E dove hai letto il problema?

"axpgn":
È carino il fatto che metti tutto sotto spoiler ma la nota no, quella spunta fuori


Cordialmente, Alex

Ahahah come mai? Comunque mi ero reso conto che non avevo spiegato proprio la domanda che avevi fatto così ho fatto la nota pensando che sarebbe finita in spoiler automaticamente, con l'anteprima ho visto che no ma poi ho anche pensato che siccome era l'unica domanda che avevi posto andava bene lasciarla fuori.

[axpgn]

Prime considerazioni:

Ai primi due passi c'ero già arrivato da solo ragionando sui "resti modulo $3$", prodotti dalle due sequenze (sx=2 e dx=6); la dx produce solo resti $0$ mentre la sinistra produce resti $1$ da resti $1$ mentre produce alternativamente resti $0$ e $2$.
Perciò dato che il punto di arrivo, che chiamo $c$, ha resto $0$, l'input sx è resto $2$ e di conseguenza il suo input è solo da sx (però quest'ultimo input può essere il prodotto sia di sx che di dx).

Le perplessità (mie) iniziano col passo 3: che cos'è $x_m$? Quell'$x_m$ non ha niente a che fare con l'$m$ che porta a $c$.

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Risposta a prime considerazioni:

"axpgn":
Le perplessità (mie) iniziano col passo 3: che cos'è $x_m$? Quell'$x_m$ non ha niente a che fare con l'$m$ che porta a $c$.

Il modo più chiaro per rispondere credo sia con un "esempio". Supponi che \( 2n+2=6m+6 \) con \( m=158 \) e per qualche \( n \). Come ci siamo arrivati ad \( m\)?

\[ 1 \rightarrow 6 \cdot 1 + 6 =12 \rightarrow 6 \cdot 12 + 6 =78 \rightarrow 2 \cdot 78 + 2 = 158 \]
in questo caso \( m=158 \), \( x_m = 78 \) e \( y_m = 12 \). Abbiamo dunque che

\[ m = 2x_m+2 , x_m = 6y_m + 6 \]

In modo analogo \( x_n \) e \(y_n \) sono gli ultimi due step per arrivare ad \( n \) che poi rende \( 2n+2 = 6m+6 \).

[Quinzio]

"3m0o":

Ora siccome ho un numero \( 2k_0 + 2 \equiv 2 \mod 3 \), poiché \( n \equiv 2 \mod 3 \) allora abbiamo tre possibili casi:
Caso 1.1: \( k_0 =3 \ell \)
Ed in questo caso abbiamo che \( n= 6 \ell + 2 \equiv 2 \mod 3 \), ed è consistente con il fatto che \( n \equiv 2 \mod 3 \)

Caso 1.2: \( k_0 = 3 \ell + 1 \)
Ed in questo caso abbiamo che \( n= 6 \ell +4 \equiv 1 \mod 3 \), e non è consistente con il fatto che \( n \equiv 2 \mod 3 \)

Caso 1.3: \( k_0 = 3\ell + 2 \).
Ed in questo caso abbiamo che \( n= 6 \ell + 6 \equiv 0 \mod 3 \), e non è consistente con il fatto che \( n \equiv 2 \mod 3 \).

Ho provato a leggere la tua dimostrazione, e ho provato a cimentarmi da solo sul problema ma senza risultati.
Inizio a perdermi gia' da questo punto (nella citazione).

\( 2k_0 + 2 \equiv 2 \mod 3 \) non e' la stessa cosa di \( 2k_0 \equiv 0 \mod 3 \) ?
Quindi significa che $k_0$ e' divisibile dal 3.
Poi procedi a fare i 3 casi, ma dal momento che e' divisibile dal 3, avrei solo il caso 1.1.
Forse mi sbaglio o non ho capito.

Comunque la ricorsione e' equivalente a
$2(n+1)$ e $6 (n+1)$
Il fatto che per tornare al numero precedente bisogna sottrarre 1 secondo me rende molto difficile ragionare in termini di resti e fattorizzazioni.
Questa sequenza ricorda abbastanza la congettura di Collatz, noto problema non risolto nella matematica.