N+1 interi

[ficus2002]

Sia $n$ un intero positivo, e siano dati $n+1$ interi positivi minori o uguali a $2n$. Dimostrare che tra i numeri dati ne esistono almeno due $a$,$b$ tali che $a|b$.

[ficus2002]

suggerimento: considerare i numeri della forma: $1, 2, 2^2, ldots; 3 cdot 1, 3 cdot 2, 3 cdot 2^2, ldots$.
Inoltre, provate che è possibile dare $n$ interi positivi minori o uguali di $2n$ tali che se $a ne b$ allora a non divide b.

[eafkuor1]

"ficus2002":Sia $n$ un intero positivo, e siano dati $n+1$ interi positivi minori o uguali a $2n$. Dimostrare che tra i numeri dati ne esistono almeno due $a$,$b$ tali che $a|b$.

Comunque si scelgano gli $n+1$ numeri, se ne dovrà per forza scegliere almeno uno $<=n$, che sarà sicuramente un sottomultiplo di uno degli altri $n$ numeri. Lo so non è una dimostrazione

[ficus2002]

"eafkuor":
Comunque si scelgano gli $n+1$ numeri, se ne dovrà per forza scegliere almeno uno $<=n$, che sarà sicuramente un sottomultiplo di uno degli altri $n$ numeri. Lo so non è una dimostrazione

Si, ma non è detto che gli altri numeri siano tutti $>n$. Può darsi che i multipli di quel numero $

Cita

Segnala

[Thomas16]

Se la sol quà sotto è giusta, era un bel quesito, ficus2002, almeno per quanto mi riguarda...

Utilizzando il suggerimento, tutti i numeri $<=2n$ possono essere divisi nei sottoinsiemi del tipo $(c*2^n)$, con c che varia nei numeri dispari $<=2n$, eccetto l'$1$, ma aggiunto il $2$ . Supponiamo $n!=1$ in quegli insiemi, anzi supponiamo che l'1 non venga scelto tra gli $n+1$ numeri, altrimenti è banale.

Ora:

- quei sottoinsiemi costituiscono una partizione dell'insieme $(2,3,4,...,2n)$;
- quei sottoinsiemi sono $n$;

Il punto è che da ogni sottoinsieme si può prendere un elemento, non di più. Perchè se ne prendessimo 2, almeno uno dei due dividerebbe l'altro (ed il risultato della divisione sarebbe una potenza di 2, per inciso).

Se prendiamo $n+1$ numeri, ne prenderemo almeno 2 da uno stesso sottoinsieme per il principio dei cassetti. Fine.

[ficus2002]

risposta esatta !

Cmq è sufficiente osservare che se $S$ è l'insieme contenente gli $n+1$ interi, allora
$S subseteq bigcup_{k=1}^{n} {(2k-1) cdot 2^m:m ge 0}$.
Non importate che gli insiemi siano disgiunti, ma, come hai osservato tu, poichè sono solo $n$, almeno uno contiene due elementi di $S$ che quindi sono uno multiplo dell'altro.

[eafkuor1]

"ficus2002":[quote="eafkuor"]
Comunque si scelgano gli $n+1$ numeri, se ne dovrà per forza scegliere almeno uno $<=n$, che sarà sicuramente un sottomultiplo di uno degli altri $n$ numeri. Lo so non è una dimostrazione

Si, ma non è detto che gli altri numeri siano tutti $>n$. Può darsi che i multipli di quel numero $
Lo so lo so