$a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n\}$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n\}$

Messaggio da jordan »

Sia $n$ un intero maggiore di $3$. Dimostrare che il numero di sottoinsiemi $S\subseteq \{1,2,\ldots,2n\}$ con $n$ elementi e tale che $a$ non divide $b$ per ogni $a,b$ distinti in $S$ è maggiore di $2^{n/4}$.
The only goal of science is the honor of the human spirit.
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da gpzes »

:oops: ...si può usare Postulato (Teorema) di Bertrand o c'è via più semplice?? :oops:
darkcrystal
Messaggi: 706
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

$a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n\}$

Messaggio da darkcrystal »

C'è una soluzione perfettamente elementare, che non usa praticamente niente ed è anche abbastanza semplice. Anzi, per come l'ho fatto io mi sembra che $2^{n/4}$ si possa migliorare (almeno) in $2^{n/3}$...

Aiutino:
Testo nascosto:
Cosa succede se prendiamo tutti gli elementi di S "grandi"? Per esempio così grandi che il rapporto tra due di loro sia necessariamente $> \frac{1}{3}$?
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da jordan »

Si volevo solo stare sicuro ;)

Possiamo vedere la soluzione con Bertrand?
The only goal of science is the honor of the human spirit.
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da gpzes »

ehh falso allarme Bertrand..ovviamente :oops: :oops: :( :wink: ...
metto un Up su questo problema :wink: :wink: ..qualcosa ho pensato ma non riesco ufgfug :oops: :( ..
ad esempio n+1, n+2,.., 2n soddisfano richiesta di NON divisibilità...si può anche shiftare verso n-1, n-2, rimpiazzando i corrispettivi divisibili e maggiori di n..ma poi?!?! :oops:

Quel $2^{n/3}$ è terribile :( :lol:
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da jordan »

Un hint per la soluzione:
Testo nascosto:
Una sappiamo qual è, ok, ma come possiamo modificarla affinchè tutte le (non) divisibilità continuano ancora?
The only goal of science is the honor of the human spirit.
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da gpzes »

:oops: :( è passato parecchio tempo e mi scuso per non riuscire a "vedere" soluzione nonostante tutti gli hints :oops: ( :lol: )
Mi sembra opportuno anche solo fare un UP perchè il problema è superinteressante (come tutti quelli di jordan :wink: :wink:, anche se non so come risolverli :lol: )
Posto comunque qualcosa assolutamente non definitivo, molto approssimativo e mal formalizzato..comunque..

Sia S uno degli insiemi con la caratteristica richiesta.
Ogni naturale è della forma ${{2}^{{{m}_{i}}}}\cdot {{q}_{i}}$ dove ${{q}_{i}}$ è dispari.
Ma allora gli elementi di un generico S devono avere tutti i ${{q}_{i}}$ diversi affinchè NON ci sia divisibilità tra essi.
Ma i numeri dispari fino a 2n sono n. Bisognerebbe cercare di sistemare gli esponenti ${{m}_{i}}$.
Siano $\alpha ,\beta $ i massimi naturali tale che $3\cdot {{2}^{\alpha }}\le 2\cdot n$ e ${{2}^{\beta }}\le 2\cdot n$. Ho considerato il 3 perché da lui in poi gli altri dispari sono maggiori quindi i rispettivi ${{m}_{i}}$ decrescono e strettamente.
Prima di proseguire, volevo esaminare un caso particolare per maggiore chiarezza ( o maggior confusione??).
Se n=9, considero $S=\left\{ {{2}^{{{m}_{1}}}}\cdot 1\ ;{{2}^{{{m}_{2}}}}\cdot 3\ ;{{2}^{{{m}_{3}}}}\cdot 5\ ;... \right\}$. In questo caso i numeri ${{2}^{4}}$ e ${{2}^{3}}$ sono due possibili scelte per il numero dispari 1 perché per tutti gli altri elementi di S posso, se maggiori di n, non mettere potenze di due, e, se minori o uguali ad n, mettere potenze di due in numero minore ad $\alpha $.
Così ragionando ${{2}^{2}}$ e $2$ sarebbero due possibilità per il numero dispari 3 etc..
Ma ${{2}^{2}}\cdot 3$ può essere presente nell’insieme S solo contemporaneamente a $2\cdot {{3}^{2}}$ oppure al solo ${{3}^{2}}$.
E analogamente, $2\cdot 3$ può essere presente solo con ${{3}^{2}}$.

Bisogna, inoltre, tener conto che alcuni ${{q}_{i}}$ possono essere prodotti di altri dispari precedenti.
$
S = \left\{ {\left. \begin{array}{l}
{2^4}\\
{2^3}
\end{array} \right\};\;{2^2} \cdot 3\;;\left\{ \begin{array}{l}
2 \cdot {3^2}\\
{3^2}
\end{array} \right.\quad ;\quad ...\quad ;\;11\;;\;13\;;\;15\;;\;17} \right\}\\$

$
S = \left\{ {\left. \begin{array}{l}
{2^4}\\
{2^3}\\
{2^2}
\end{array} \right\};2 \cdot 3\;;\left\{ {{3^2}} \right.\quad ;\quad ...\quad ;\;11\;;\;13\;;\;15\;;\;17} \right\}\\$
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da jordan »

Beh si, quanto hai scritto è giusto: in altre parole, se scegliamo $2^\alpha a$ e $2^\beta b$ in $S$ con $a<b$ entrambi dispari e tali che $a\mid b$ allora $\alpha > \beta \ge 0$. :)
The only goal of science is the honor of the human spirit.
RiccardoKelso

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da RiccardoKelso »

Vago tentativo:
Testo nascosto:
Per $n$ dispari ne abbiamo almeno $2^{(n-1)/2}$ mentre per $n$ pari mi pare $2^{(n-2)/2}$ .. son giunto qui dividendo successivamente per due gli elementi pari più grandi di ogni $S$ finché si è sicuri di non far nascere sottomultipli di del nuovo $S$ così ottenuto
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da jordan »

L'idea è corretta. Sui dettagli sono un po' scettico, perchè il tuo esponente è po' troppo grande :roll:
The only goal of science is the honor of the human spirit.
RiccardoKelso

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da RiccardoKelso »

Ammetto di aver fatto un ragionamento spannometrico ben poco virtuoso. (Che novità :oops: )
Testo nascosto:
Dovrebbe essere possibile dividere per $2$ elementi di $S$ senza preoccuparsi che siano divisori fino a quando, come ha detto darkcrystal, l'elemento ottenuto rimane maggiore di $2N/3$. Quindi puoi dividere per due tutti gli elementi $K \in S$ con $K>4N/3$, rimanendo ovviamente con $2N\ge K$. Abbiamo di conseguenza almeno $(2N/3)/2$ elementi $K$ pari ognuno dei quali ci permette di costruire due diversi sottoinsiemi, si ottiene quindi $2^{N/3}$. (Anche se così non si dimostra che si ottiene sempre almeno un numero maggiore di $2^{N/3}$, cosa che dalle parole di darkcrystal mi era parso di intuire)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da jordan »

Nah, credo questo fosse anche il suo argomento (confermi?).. Comunque, molto bene :wink:
The only goal of science is the honor of the human spirit.
darkcrystal
Messaggi: 706
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n

Messaggio da darkcrystal »

Yep, l'idea era sostanzialmente quella! Riscrivo la soluzione in un modo che mi sembra più pulito (lo faccio solo per $n$ multiplo di 3 per non dovermi preoccupare delle parti intere... ma funziona lo stesso).
Testo nascosto:
Costruisco i sottoinsiemi $S$ nel modo seguente. Sia $S_1$ l'insieme dei numeri interi nell'intervallo $\left[n+1,\frac{4n}{3}\right]$ (sono $n/3$), $S_2$ l'insieme degli interi dispari nell'intervallo $\left[\frac{4n}{3}+1,2n \right]$ (anche questi sono $n/3$), e sia infine $S_3=\left\{m_1,\ldots,m_{n/3} \right\}$ l'insieme degli interi nell'intervallo $\left[ \frac{2n}{3}+1,n \right]$ (a questi purtroppo mi tocca dare un nome; è chiaro che pure loro sono $n/3$). Costruisco ora $2^{n/3}$ sottoinsiemi $S$ che funzionano. Scegliamo $n/3$ esponenti $e_1,\ldots,e_{n/3}$ che possono valere $0$ oppure $1$ (chiaramente abbiamo $2^{n/3}$ tali scelte), e scegliamo
\[
S=S_1 \cup S_2 \cup \left\{ 2^{e_i} m_i \bigm\vert i=1,\ldots,n/3 \right\}.
\]
Gli $S$ che si ottengono in questo modo sono tutti diversi; inoltre il minimo degli interi contenuti in un tale insieme $S$ è almeno $2n/3+1$.
Verifichiamo che questi sottoinsiemi rispettano la condizione $a \nmid b$ per ogni $a,b$ in $S$. Chiaramente possiamo supporre $b>a$; allora $b/a \leq \frac{2n}{2n/3+1} < 3$, quindi l'unico caso che potrebbe potenzialmente andare male è $b=2a$. Tuttavia questo non può succedere: i numeri in $S_2$ sono dispari, quindi non sono il doppio di niente, e i numeri in $S_1$ non possono essere il doppio di un elemento di $S$, perché la loro metà è al più $2n/3$ (che è minore di tutti i numeri in $S$). Resta da vedere che i numeri $b \in \left\{ 2^{e_i} m_i \bigm\vert i=1,\ldots,n/3 \right\}$ non sono il doppio di un elemento di $S$, ma questo è chiaro per costruzione: se $b$ è uno degli $m_i$ (cioè se il corrispondente $e_i$ è zero) allora $m_i/2 \leq n/2 < 2n/3+1$ non sta in $S$, mentre se $b=2m_i$ allora per costruzione $m_i$ non sta in $S$ (visto che in $S$ abbiamo messo esattamente uno tra $m_i$ e $2m_i$).
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO
Rispondi