Teoria dei numeri

[giulylanza06]

Consideriamo X = {1, 2, 3, . . . , 2n − 2, 2n − 1, 2n}. Sia A un sottoinsieme di X con n + 1 elementi.
1. Dimostrare che in A vi sono almeno due numeri coprimi.
2. Dimostrare che in A vi sono almeno due numeri tali che uno divide l’altro.

[kobeilprofeta]

2

Supponiamo che ci siano $n$ numeri maggiori di $n$ ed uno solo ($k$) minore o uguale ad $n$. Allora $2k$ appartiene all'insieme.
Togliamo allora un altro numero "grande" per metterne uno "piccolo". Se non tolgo $2k$ ho finito, togliamo quindi $2k$. Mettiamo un'altro $j!=k$ piccolo. Ma $2j!=2k$ appartiene all'insieme e siamo da capo.
Iterando troveró sempre due numeri uno doppio dell'altro

[axpgn]

"kobeilprofeta":

... Allora $2k$ appartiene all'insieme. ...

None.

Poni $n=10$ e $k=3$ ...

[axpgn]

Penso che perfezionando l'idea di kobe si possa arrivare a meta ...

Non è detto che ci sia $2k$ ma sicuramente ci sarà o $3k$ o $4k$ o ... anzi ce ne saranno più d'uno, quindi togliendo questi e ragionando su quelli da aggiungere forse si arriva ...

Cordialmente, Alex

[orsoulx]

2

Si può dimostrare per assurdo con il metodo della discesa infinita. Supponendo che per un dato $ n $ esista un sottoinsieme $ A_{n+1} $ privo di coppie di elementi in cui uno dei due divida l'altro, si può ricavare, distinguendo i due casi $ 2n $ appartiene/non appartiene a $ A_{n+1} $, un $ A_n $ sottoinsieme di $ [1...2(n-1)] $ con la medesima proprietà.
Da cui l'assurdo visto che la proprietà non può valere per $ n=1 $

Ciao
B.

[axpgn]

1

L'ampiezza dell'insieme è $2n-1$ mentre le distanze dei numeri del sottoinsieme sono $n$ perciò la distanza media tra due numeri del sottoinsieme è inferiore a $2$; ciò significa che almeno due numeri del sottinsieme sono consecutivi perciò coprimi

Cordialmente, Alex

[orsoulx]

Ebbravo Alex! La soluzione dell'(1) mi è piaciuta molto. Si fan le ore piccole
Ciao
B.

[kobeilprofeta]

"axpgn":[quote="kobeilprofeta"]

... Allora $2k$ appartiene all'insieme. ...

None.

Poni $n=10$ e $k=3$ ...

[/quote]

Vorresti dire $k=2$?

Comunque sì, ho capito

[axpgn]

Ma anche $k=3$ o $k=4$ o $k=5$ ...

[kobeilprofeta]

ah sì, ragionavo sul 10...