Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.
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$.
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.
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
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
Si, ma non è detto che gli altri numeri siano tutti $>n$. Può darsi che i multipli di quel numero $<n$ non ci siano.
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.
16/04/2006, 13:44
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.
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
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
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.