Pagina 1 di 1

n+1 interi

MessaggioInviato: 14/04/2006, 18:54
da 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$.

MessaggioInviato: 16/04/2006, 08:19
da 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.

Re: n+1 interi

MessaggioInviato: 16/04/2006, 08:56
da eafkuor
ficus2002 ha scritto: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 :-D

Re: n+1 interi

MessaggioInviato: 16/04/2006, 10:16
da ficus2002
eafkuor ha scritto: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 :-D


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

MessaggioInviato: 16/04/2006, 11:26
da Thomas
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.

MessaggioInviato: 16/04/2006, 13:44
da ficus2002
risposta esatta :wink: !

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.

Re: n+1 interi

MessaggioInviato: 16/04/2006, 21:58
da eafkuor
ficus2002 ha scritto:
eafkuor ha scritto: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 :-D


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


Lo so lo so :-D