Esistono $a,b$ tali che $a$ divide $b$?

[jordan]

Own. Sia fissata una costante positiva $k$ e un insieme $\mathcal{N} \subset \{1,2,\ldots,2n\}$ tale che $|\mathcal{N}|\ge n$ e $\min \mathcal{N} \le k\sqrt{n}$.

Mostrare che esistono $a,b \in \mathcal{N}$ distinti tali che $a$ divide $b$ ogni volta che $n$ è sufficientemente grande.

[maurizio43]

Non so se ho interpretato bene il testo (a volte sono debole nell'interpretazione della simbologia). Io lo ho interpretato come :
<< Qualunque sia un numero reale $ k > 0 $ e qualunque sia un insieme $ N $ di $ n $ elementi (il minimo dei quali sia $ m \le {k \sqrt{n}} $ ) , scelti tra i primi $ 2n $ numeri naturali,
purchè $ n $ sia abbastanza grande esiste almeno una coppia di elementi di $ N $ , che indichiamo con $ a $ e $ b $ tali che $ b $ sia multiplo di $ a $ >> .
Questo testo può essere contraddetto con un esempio :

Testo nascosto:

Se $k \lt \sqrt{n}$ , allora $ k \sqrt{n} < n $ e quindi $ m \le {n-1}$ .
E assumendo $ m=n-1 $ si può configurare un caso che contraddice l' ipotesi su $ a $ e $ b $ :
Escludendo i casi in cui $a \ge {n+1}$ , (per i quali dovrebbe essere $b \ge {2n+2}$ e $ b $ non apparterrebbe a $ N $) , restano solo i casi :
$ a=n $ , (per il quale dobrebbe essere $ b=2n $ ), oppure $ a=n-1 $ , (per il quale dovrebbe essere $ b=2n-2 $)
E la n-pla di elementi costituita dall' elemento $ 2n-1 $ unitamente agli $n-1$ elementi consecutivi che vanno da $ n-1 $ (compreso) fino a $ 2n-3 $ (compreso)
costituisce un insieme $ N $ che contraddice l' ipotesi su $ a $ e $ b $ in entrambi i casi.

[jordan]

Ci sono alcune imprecisioni, e un errore logico:

1. $\mathcal{N}$ è un insieme di almeno $n$ elementi: resta il fatto che provare la tesi per $|\mathcal{N}|=n$ implicherebbe anche il resto

2. Gli elementi che prendi da $\mathcal{N}$ devono essere necessariamente distinti

3. L'ipotesi del problema è che $m:=\min \mathcal{N}$ è al massimo $k\sqrt{n}$. Bene, come fai ad assumere che $m=n-1$? Non ti pare che $k\sqrt{n}$ è molto piu' piccolo di $n-1$ per ogni $n$ sufficientemente grande e $k \in \mathbb{R}_{>0}$ fissato? Il tuo errore sta nel fatto che la disuguaglianza $m\le k\sqrt{n} \le n-1$ è corretta, nel senso che è necessario che sia verificata: non implica certo sia anche sufficiente..


Ad ogni modo, ti posso assicurare che la tesi è corretta; potresti iniziare a dimostrarla nel caso in cui $|\mathcal{N}|\ge n+1$

[maurizio43]

Ti ringrazio della tua risposta, che mi ha chiarito le idee .
Come al solito il principale dei miei difetti (non certo l'unico) è che io parto in tromba a risolvere un problema che non è quello proposto (se ti par poco...).
E infatti stavolta nella premessa avevo prudentemente indicato il "mio" testo di riferimento.
A questo proposito indico le mie spiegazioni :
- punto 1 --> mia cappella di lettura (...spiegabile solo con un micro-ictus passeggero !)
- punto 2 --> considerando $ N $ un insieme di n elementi, mi sembra che andasse da sè che fossero distinti
- punto 3 --> considerato che tutto doveva valere per qualsiasi valore di $k$ , doveva valere anche per $ k=\sqrt{n-1} $ , e in questo caso $ m=k \sqrt n= \sqrt {n(n-1)}< n $ ; e quindi era lecito partire da $ m=n-1 $
(ma appunto solo nell'ipotesi scelto un $n$ fisso un $k$ , e non viceversa !... : altro microictus )

Per fortuna sparare soluzioni al volo mi diverte (nonostante le figure barbine), ma temo che non vi divertiate voi... (Nel caso ... reprimetemi !)

[jordan]

Esatto, non puoi scegliere $k$ in funzione di $n$..