32. Insiemi senza doppi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

32. Insiemi senza doppi

Messaggio da Mist »

Chiamiamo $S_n:= \{ x\leq n, x\in S \rightarrow 2x \not \in S \}$. Calcolare il valore massimo di $|S_{3000}|$.
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: 32. Insiemi senza doppi

Messaggio da scambret »

Sia $d$ un intero dispari e sia $A_d$ l'insieme degli interi minori o uguali a $n$ esprimibili come $2^k \cdot d$. Per questo motivo il massimo di $A_d$ è $2^kd \leq n$ e quindi $\displaystyle k \leq \log_2 \frac{n}{d}$ e quindi il numero di elementi di $A_n$ è $\displaystyle \lfloor \log_2 \frac{n}{d}+1 \rfloor$

Allora $S_n=\sum_{d=1}^n \frac{\mid A_d \mid}{2}$

Dovrebbe essere questo e a me sembra abbastanza ovvio, magari dopo lo dettaglio meglio..
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: 32. Insiemi senza doppi

Messaggio da Mist »

scambret ha scritto:Sia $d$ un intero dispari e sia $A_d$ l'insieme degli interi minori o uguali a $n$ esprimibili come $2^k \cdot d$. Per questo motivo il massimo di $A_d$ è $2^kd \leq n$ e quindi $\displaystyle k \leq \log_2 \frac{n}{d}$ e quindi il numero di elementi di $A_n$ è $\displaystyle \lfloor \log_2 \frac{n}{d}+1 \rfloor$

Allora $S_n=\sum_{d=1}^n \frac{\mid A_d \mid}{2}$

Dovrebbe essere questo e a me sembra abbastanza ovvio, magari dopo lo dettaglio meglio..
Forse non ho capito bene io, ma http://www.wolframalpha.com/input/?i=\s ... ntegerPart[log%283000%2Fd%29%2Flog%282%29+%2B1]+%2F2 mi sembra un po' troppo perché le ipotesi siano rispettate...
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: 32. Insiemi senza doppi

Messaggio da scambret »

Allora diciamo che considero tipo $A_1=\{1,2,4,8,16,32,64,128,256,512,1024,2048\}$ e prendo $\{1,4,16,64,256,1024\} $
Poi considero $A_3$ e cosi via..
Questo è ovvio che massimizza l'insieme $S_n$ (infatti è un algoritmo che prende $x$ ma non $2x$, quindi prende $4x$ etc, quando esaurisce gli interi esprimibili come $2^kx$ passa al dispari più piccolo rimasto nell'insieme da 1 a 3000.

Detto $d=2k+1$ abbiamo

$$\displaystyle S_n=\sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} \lceil \frac{\lfloor \log_2 \frac{n}{2k+1} \rfloor+1}{2} \rceil$$

che cos è tutto questo pastrocchio?? Allora il numero degli elementi di $A_{2k+1}$ sono $\lfloor \log_2 \frac{n}{2k+1} \rfloor+1$. Ora se gli elementi sono in numero dispari (tipo 11), devo prendere il 1, il 3, fino al 11-esimo.. la funzione $\lceil x \rceil$ di $\lceil \frac{x}{2} \rceil$ con $x$ dispari da la parte intera +1, altrimenti con i pari non fa nulla.. Ora faccio la somma su tutti i $k$ da $0$ (che rappresenta $d=1$) fino a 1499, che rappresenta $d=2999$. E la somma (excel) mi da tipo 1999.
mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: 32. Insiemi senza doppi

Messaggio da mat94 »

Sì la risposta è 1999 :)
Mi chiedevo se si poteva fare in questo modo. Dato che la differenza tra un numero $n$ e la sua metà è maggiore tanto è più grande il numero, per massimizzare l'insieme senza doppi dobbiamo cercare di inserirvi gli elementi più grandi possibili per inserire le sequenze più grandi formate da $n$ fino a $\frac{n}{2}-1$. Detto ciò è naturale che 3000 debba esserci dato che è l'elemento più grande, quindi consiedero la sequenza 1501-3000. A questo punto gli elemnti da 751 a 1500 non sono utili perché il loro doppio appartiene all'insieme. Così procedendo ottengo l'insieme composto da 1,6-11,24-46,94-187,376-750,1501-3000 che ha esattamente 1999 elementi.
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: 32. Insiemi senza doppi

Messaggio da Mist »

Sì, bene, scasmbret vada pure col prossimo :) Io l'avevo fatto come mi pare abbia fatto anche mat94, ovvero calcolando (come mi sembra che abbia fatto lui) $\displaystyle \sum_{j=0}^{\infty} \left \lfloor \frac{n}{2^j} \right \rfloor$
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: 32. Insiemi senza doppi

Messaggio da ma_go »

Mist ha scritto:Chiamiamo $S_n:= \{ x\leq n, x\in S \rightarrow 2x \not \in S \}$. Calcolare il valore massimo di $|S_{3000}|$.
giusto per fare i pignoli, quella cosa che hai scritto non ha nessun senso. neanche se metti $S_n$ invece di $S$. semplicemente, stai circa definendo un insieme (peraltro, in maniera simil-ricorsiva, dalla notazione, e questo non si può fare), mentre quella che hai è una famiglia di insiemi (circa).
mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: 32. Insiemi senza doppi

Messaggio da mat94 »

Mist ha scritto: Io l'avevo fatto come mi pare abbia fatto anche mat94, ovvero calcolando (come mi sembra che abbia fatto lui) $\displaystyle \sum_{j=0}^{\infty} \left \lfloor \frac{n}{2^j} \right \rfloor$
Esatto :)
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: 32. Insiemi senza doppi

Messaggio da scambret »

Data la mia scarsità in combinatoria, non ho mai trovato problemi difficili che ho saputo risolvere, quindi cederei il testimone a mat94 che ha risolto lo stesso il problema oppure, se non vuole, a chi ha un bel problema :D
mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: 32. Insiemi senza doppi

Messaggio da mat94 »

scambret ha scritto:Data la mia scarsità in combinatoria, non ho mai trovato problemi difficili che ho saputo risolvere, quindi cederei il testimone a mat94 che ha risolto lo stesso il problema oppure, se non vuole, a chi ha un bel problema :D
Ma il problema non deve essere per forza difficile e poi non è vero che sei scarso! Comunque proporre un problema che non sia una funzionale ti fa bene di tanto in tanto :lol:
Rispondi