n+1 interi

Messaggioda ficus2002 » 14/04/2006, 18:54

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
Average Member
Average Member
 
Messaggio: 102 di 596
Iscritto il: 09/02/2006, 17:35

Messaggioda ficus2002 » 16/04/2006, 08:19

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.
ficus2002
Average Member
Average Member
 
Messaggio: 113 di 596
Iscritto il: 09/02/2006, 17:35

Re: n+1 interi

Messaggioda eafkuor » 16/04/2006, 08:56

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
Gauss è morto, Euler è morto, e io stesso non mi sto sentendo molto bene...
eafkuor
Senior Member
Senior Member
 
Messaggio: 705 di 1105
Iscritto il: 08/03/2004, 15:59
Località: Italy

Re: n+1 interi

Messaggioda ficus2002 » 16/04/2006, 10:16

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.
ficus2002
Average Member
Average Member
 
Messaggio: 114 di 596
Iscritto il: 09/02/2006, 17:35

Messaggioda Thomas » 16/04/2006, 11:26

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.
Thomas
Senior Member
Senior Member
 
Messaggio: 452 di 1954
Iscritto il: 28/09/2002, 21:44

Messaggioda ficus2002 » 16/04/2006, 13:44

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.
ficus2002
Average Member
Average Member
 
Messaggio: 116 di 596
Iscritto il: 09/02/2006, 17:35

Re: n+1 interi

Messaggioda eafkuor » 16/04/2006, 21:58

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
Gauss è morto, Euler è morto, e io stesso non mi sto sentendo molto bene...
eafkuor
Senior Member
Senior Member
 
Messaggio: 707 di 1105
Iscritto il: 08/03/2004, 15:59
Località: Italy


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 12 ospiti