Un problema alquanto rognoso

Azarus · Messaggio da **Azarus** » 01 gen 1970, 01:33

Sia P un insieme di cardinalità M di interi positivi.
 Sia Q l\'insieme dei numeri nella forma 2^k + n con n appartenente a P o Q e k appartenente a Z+.
 Determinare se è possibile trovare M finito per cui ogni intero positivo appartiene a P o Q.
 
 Non so minimamente quale possa essere la soluzione.
 Sono circa 2 giorni che tiro fuori considerazioni lapalissiane e null\'altro.
 
 [/mode Supplica ON]
 VI PREGO RISOLVETELO <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">
 [/mode Supplica OFF]
 
 
 [ Questo Messaggio è stato Modificato da: Azarus il 17-03-2003 14:04 ]

Messaggio da **ma_go** » 01 gen 1970, 01:33

Uhm... potrebbe essere una cazzabubbola, ma se M=1, e P={1}, non è già verificata l\'ipotesi? Ogni numero positivo può essere scritto come somma di un numero finito di potenze di 2... sparatemi se ho sparato una cazzata.

Azarus · Messaggio da **Azarus** » 01 gen 1970, 01:33

uff...mi scordo sempre qualcosa...in P non ci può essere 1...in realtà \'sta roba è parte di un problema più grosso e figo...forse mi sono infognato in una soluzione senza uscita!
 
 avevo scritto M invece di P...Scusa Evariste (messaggio sotto) [ Questo Messaggio è stato Modificato da: Azarus il 17-03-2003 16:15 ]

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Quando dici che in M non ci può essere 1 intendi dire che M>1, giusto, cioè che P deve avere almeno 2 elementi ? Perchè se invece 1 non può essere in P basta che P={0} e M=1.
 Btw: tra gli interi positivi fai rientrare anche lo 0?

sprmnt21 · Messaggio da **sprmnt21** » 01 gen 1970, 01:33

Non mi e\' chiara questa parte:
 
 \"Sia Q l\'insieme dei numeri nella forma 2^k + n con n appartenente a P o Q e k appartenente a Z+. \"
 
 mi sembra una definizione ricorsiva ( che, di per se\', potrebbe essere corretta, pero\' ...) che non riesco ad interpretare. Puoi fare qualche esempio di elementi dell\'insieme Q?

Azarus · Messaggio da **Azarus** » 01 gen 1970, 01:33

no,non faccio rientrare lo 0, altrimenti...
 
 cmq che so prendo P = {2} e in Q ci stanno tutti i pari

Azarus · Messaggio da **Azarus** » 01 gen 1970, 01:33

ora purtroppo non posso, cmq stasera posto il lungo post del problema originario + la mia parte di soluzione.

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-03-17 16:13, Azarus wrote:
 no,non faccio rientrare lo 0, altrimenti...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Allora è semplicemente impossibile che in PUQ siano contenuti tutti i naturali: 1=2^k+n se n=0 e k=0. Se invece vuoi che nell\'insieme detto siano contenuti tutti i naturali tranne 1...bhe, ci penso! <IMG SRC="images/forum/icons/icon_wink.gif">

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

P={2;3}
 4=2^1+2
 5=2^1+3
 6=2^2+2
 7=2^2+3
 8=2^2+2
 9=2^2+5
 10=2^2+6
 11=2^2+7
 ...
 M=2 e ci rientrano tutti i naturali tranne 1! <IMG SRC="images/forum/icons/icon_biggrin.gif">
 Può andare?

Azarus · Messaggio da **Azarus** » 01 gen 1970, 01:33

mi sono reso conto che, così formulato, il problema risulta essere banale (come Evariste ha dimostrato).
 
 in realtà il problema è che i k del 2^k + n sottostanno a precise regole, dovendo essere una funzione di n.
 
 Mi spiego meglio:
 
 definiamo una f(n) in questo modo con n naturale in questo modo:
 
 f(n) = 3n+1 se n dispari
 f(n) = n/2 se n pari
 
 reiteriamo la funzione sul risultato in modo da costruire una successione,ad esempio
 
 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
 
 la congettura di Syracuse afferma che per ogni n la successione prima o poi passerà per 1.
 
 Diamo un po\' di definizioni: chiamiamo \"volo alto\" i passaggi in cui la successione è maggiore del numero di partenza,incluso il passaggio finale
 (insomma nell\'esempio fino a 2)
 
 Chiamiamo \"numero di riduzione\" il numero di divisioni per 2 nel volo alto(nell\'esempio 4, essendo incluso il passaggio finale), e definiamo una funzione g(n) che associa ad n il suo Num. Rid.
 
 Chiamiamo contraddittore un numero la cui successione diverge ad infinito oppure ha un ciclo periodico diverso da 1,2,4,1.
 Supponiamo poi per assurdo (?) che la congettura sia falsa,dunque deve esistere un minimo contraddittore.
 
 risulta teorema imediato e di dimostrazione triviale che se k>=g(n)
 allora 2^k + n non è mai il più piccolo contraddittore.
 
 se non è il più piccolo contraddittore allora g(2^k + n) è un valore finito, dunque so che esiste m per cui 2^m + 2^k + n non contraddice.
 
 ora, se è possibile trovare un sottoinsieme finito dei naturali per cui la congettura è vera allora è vera per tutti gli N, ma non so minimamente come trovare questo insieme.
 
 ecco qua il vero problema ^_^

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Alla faccia...la sequenza 3x+1, sive problema di Collatz, sive congettura di Syracuse...certo stai affrontando Golia con una fionda, caro il mio Azarus.
 Se vuoi ho più o meno una marea di links sull\'argomento, con una pretesa dimostrazione di un certo Shorer, anche se non mi convince molto...Cmq in bocca al lupo <IMG SRC="images/forum/icons/icon_wink.gif">

Azarus · Messaggio da **Azarus** » 01 gen 1970, 01:33

gh, adoro questo problema...anche se so che non ha minimamente senso affrontarlo....cmq mi faresti un enorme piacere a linkare