$a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n\}$
$a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n\}$
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.
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
...si può usare Postulato (Teorema) di Bertrand o c'è via più semplice??
-
- 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\}$
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:
Aiutino:
Testo nascosto:
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
Si volevo solo stare sicuro
Possiamo vedere la soluzione con Bertrand?
Possiamo vedere la soluzione con Bertrand?
The only goal of science is the honor of the human spirit.
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
ehh falso allarme Bertrand..ovviamente ...
metto un Up su questo problema ..qualcosa ho pensato ma non riesco ufgfug ..
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?!?!
Quel $2^{n/3}$ è terribile
metto un Up su questo problema ..qualcosa ho pensato ma non riesco ufgfug ..
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?!?!
Quel $2^{n/3}$ è terribile
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
Un hint per la soluzione:
Testo nascosto:
The only goal of science is the honor of the human spirit.
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
è passato parecchio tempo e mi scuso per non riuscire a "vedere" soluzione nonostante tutti gli hints ( )
Mi sembra opportuno anche solo fare un UP perchè il problema è superinteressante (come tutti quelli di jordan , anche se non so come risolverli )
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\}\\$
Mi sembra opportuno anche solo fare un UP perchè il problema è superinteressante (come tutti quelli di jordan , anche se non so come risolverli )
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\}\\$
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
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.
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
Vago tentativo:
Testo nascosto:
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
L'idea è corretta. Sui dettagli sono un po' scettico, perchè il tuo esponente è po' troppo grande
The only goal of science is the honor of the human spirit.
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
Ammetto di aver fatto un ragionamento spannometrico ben poco virtuoso. (Che novità )
Testo nascosto:
Re: $a\nmid b$, per ogni $a,b \in S\subseteq \{1,2,\ldots,2n
Nah, credo questo fosse anche il suo argomento (confermi?).. Comunque, molto bene
The only goal of science is the honor of the human spirit.
-
- 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
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:
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO