OliForum Matematico

il forum ufficiale delle olimpiadi della matematica
https://www.oliforum.it/

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

https://www.oliforum.it/viewtopic.php?t=19598

Pagina 1 di 1

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

Inviato: 27 ago 2015, 12:19
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}$.

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

Inviato: 28 ago 2015, 02:44
da gpzes
:oops: ...si può usare Postulato (Teorema) di Bertrand o c'è via più semplice?? :oops:

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

Inviato: 28 ago 2015, 13:53
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}$?

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

Inviato: 28 ago 2015, 15:38
da jordan
Si volevo solo stare sicuro ;)

Possiamo vedere la soluzione con Bertrand?

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

Inviato: 16 set 2015, 22:52
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:

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

Inviato: 16 set 2015, 23:13
da jordan
Un hint per la soluzione:
Testo nascosto:
Una sappiamo qual è, ok, ma come possiamo modificarla affinchè tutte le (non) divisibilità continuano ancora?

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

Inviato: 27 set 2015, 23:15
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\}\\$

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

Inviato: 28 set 2015, 10:50
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$. :)

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

Inviato: 28 set 2015, 11:18
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

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

Inviato: 28 set 2015, 18:51
da jordan
L'idea è corretta. Sui dettagli sono un po' scettico, perchè il tuo esponente è po' troppo grande :roll:

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

Inviato: 28 set 2015, 21:57
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)

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

Inviato: 30 set 2015, 00:23
da jordan
Nah, credo questo fosse anche il suo argomento (confermi?).. Comunque, molto bene :wink:

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

Inviato: 30 set 2015, 19:54
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$).
Tutti gli orari sono UTC+02:00
Pagina 1 di 1

Creato da phpBB® Forum Software © phpBB Limited

Traduzione Italiana phpBB-Italia.it