Un passo avanti e due indietro

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
franco
Livello 8
Livello 8
Messaggi: 1193
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Un passo avanti e due indietro

Messaggio da franco »

Partiamo da un numero intero $m$ >0.
L'operazione $R(m)$ consiste nel sostituirlo con l'intero $3m+1$ oppure con la parte intera di $m/2$.
Ad esempio, $m=7$ ... $R(7)=22$ oppure $R(7)=3$.

1. Dimostrare che qualunque siano gli interi $m$ e $n$ >0, è possibile passare passare da $m$ a $n$ in un numero finito di operazioni $R$.
2. Scrivere le sequenze che ci permettono di fare un passo avanti (da $2020 $ a $2021$) e due indietro (da $2021$ a $2019$).


www.diophante.fr
E599

Un entier m > 0 est écrit au tableau. L’opération R consiste à le remplacer soit par l’entier 3m + 1 soit par la partie entière par défaut de m/2.Par exemple m = 7, R(7) = 22 ou bien R(7) = 3.
Q1 Démontrer que quels que soient les entiers a et b > 0, on peut passer de a à b en un nombre fini d’opérations R.
Q2 Donner deux suites d’opérations permettant de faire respectivement un pas en avant (2020 à 2021) puis deux pas en arrière (2021 à 2019).
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Pasquale
Livello 11
Livello 11
Messaggi: 2628
Iscritto il: mer mag 25, 2005 2:14 am

Re: Un passo avanti e due indietro

Messaggio da Pasquale »

Proposte, scritte in modo sintetico, senza indicare cioè il simbolo della parte intera nelle divisioni:

2020:2=1010
1010:2=505
505:2=252
252:2=126
126x3+1=379
379:2=189
189x3+1=568
568x3+1=1705
1705:2=852
852:2=426
426x3+1=1279
1279:2=639
639:2=319
319:2=159
159x3+1=478
478:2=239
239:2=119
119:2=59
59x3+1=178
178:2=89
89:2=44
44x3+1=133
133:2=66
66x3+1=199
199x3+1=598
598:2=299
299x3+1=898
898x3+1=2695
2695:2=1347
1347x3+1=4042
4042:2=2021

Quindi:

2021x3+1=6064
6064:2=3032
3032:2=1516
1516:2=758
758x3+1=2275
2275x3+1=6826
6826x3+1=20479
20479:2=10239
10239:2=5119
5119:2=2559
2559x3+1=7678
7678:2=3839
3839:2=1919
1919:2=959
959:2=479
479:2=239
239:2=119
119:2=119
119:2=59
59x3+1=178
178:2=89
89:2=44
44x3+1=133
133:2=66
66x3+1=199
199x3+1=598
598x3+1=1795
1795:2=897
897x3+1=2692
2692x3+1=8077
8077:2=4038
4038:2=2019
Ultima modifica di Pasquale il mar nov 03, 2020 7:07 pm, modificato 3 volte in totale.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1249
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Un passo avanti e due indietro

Messaggio da Gianfranco »

franco ha scritto:
ven ott 30, 2020 5:38 pm
1. Dimostrare che qualunque siano gli interi $m$ e $n$ >0, è possibile passare passare da $m$ a $n$ in un numero finito di operazioni $R$.
Pasquale, olè.

Ecco una risposta rozza alla prima domanda.
1) Dare un solo nome a due funzioni mi sembra un po' fuorviante, perciò definisco:
T(x)=3x+1
M(x)=int(x/2)

2) Mi ricordano le regole del problema 3n+1 di Collatz. Prendo per buona la congettura di Collatz.
Perciò se parto da m e applico le regole citate, arrivo a 1 dopo un numero finito di passi.
In alternativa, continuo ad applicare M(x) finche arrivo a 1.

3) Mi chiedo: è possibile fare il percorso inverso? Cioè partire da 1 e arrivare a un numero n qualsiasi applicando un numero finito di volte T e M?
Sì, è possibile, applicando opportunamente, in sequenza le seguenti coppie:
T(M(x))
M(T(x))
(da dimostrare)

4) In conclusione, si può passare da m a n in un numero finito di passaggi andando prima da m a 1 e poi da 1 a n. Ovviamente non è detto che questa sia la strada più breve, come si nota nelle soluzioni di Pasquale.

A supporto del punto 3 c'è questo programmino in BASIC.

Codice: Seleziona tutto

FUNCTION T(n)
   LET T=3*n+1
END FUNCTION
FUNCTION M(n)
   LET M=INT(n/2)
END FUNCTION

FOR a=1 TO 1000
   PRINT a;T(M(a))
   PRINT a;M(T(a)) 
NEXT a  
END
Pace e bene a tutti.
Gianfranco

Pasquale
Livello 11
Livello 11
Messaggi: 2628
Iscritto il: mer mag 25, 2005 2:14 am

Re: Un passo avanti e due indietro

Messaggio da Pasquale »

Non è male l'idea di scendere fino ad 1 per poi risalire. Segue un esempio di risalita fino a 100.000 in 33 passaggi:

1-4-13-6-19-9-28-85-256-769-384-1153-576-288-144-433-1300-650-1951-5854-2927-1463-4390-2195-1097-3292-9877-4938-14815-7407-22222-66667-33333-100000

( lettura: se il numero che segue cresce, vuol dire che con i criteri stabiliti il precedente è stato moltiplicato, altrimenti è stato diviso )
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Rispondi