Pagina 1 di 1
$m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$
Inviato: 22 set 2012, 17:31
da jordan
Siano fissati $x_1,x_2,\ldots,x_{mn+1}$ interi positivi distinti. Mostrare che ne possiamo trovare $m+1$ tali che ognuno non è divisibile per un altro di essi, o $n+1$ tali che ognuno di essi divide il seguente
(Putnam 1966)
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 24 set 2012, 12:36
da bummer
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 24 set 2012, 16:50
da jordan
bummer ha scritto:per Dilworth
Scusa l'ignoranza, ma cos'è?
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 24 set 2012, 17:43
da bummer
jordan ha scritto:bummer ha scritto:per Dilworth
Scusa l'ignoranza, ma cos'è?
http://en.wikipedia.org/wiki/Dilworth's_theorem
È parte del bagaglio olimpico per quanto mi risulta.
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 24 set 2012, 17:59
da jordan
Grazie del link. Comunque puo' essere, non sono mai stato una cima qui e in geometria
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 26 set 2012, 10:42
da fph
È parte del "bagaglio olimpico" (se sufficientemente avanzato), ma su un forum di allenamento, quando il testo dell'esercizio è praticamente "dimostra Dilworth", non è molto istruttivo usarlo...
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 26 set 2012, 10:45
da EvaristeG
Tant'è che l'esercizio è del '66, quando di sicuro Dilworth NON ERA parte del "bagaglio olimpico" XD
Quindi se qualcuno che non sa cos'è sta cosa e non ha guardato il link vuole provarci, tanto meglio...
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 26 set 2012, 14:16
da jordan
EvaristeG ha scritto:Quindi se qualcuno che non sa cos'è sta cosa e non ha guardato il link vuole provarci, tanto meglio...
Wow sai addirittura l'anno in cui è stato fatto?
Ps. In ogni erano sufficienti due riche di pigenhole, ma conoscere teoremi del genere non fa mai male..
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 26 set 2012, 15:13
da fph
jordan ha scritto:
Wow sai addirittura l'anno in cui è stato fatto?
jordan, poche righe più su ha scritto:
(Putnam 1966)
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 26 set 2012, 15:35
da jordan
fph ha scritto:
(Putnam 1966)
Di solito non metto la fonte, ma hai ragione, non ho fatto caso al fatto che l'avessi scritto io stesso
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Inviato: 26 set 2012, 17:07
da EvaristeG
E vabbeh, visto che tanto qui le discussioni divagano, posto una soluzione.
Se da un numero $x_j$ parte una successione di multipli più lunga di $n$, abbiamo vinto, quindi da ogni numero parte al più una successione di $n$ multipli.
Per i cassetti, ci sono $m+1$ numeri che hanno esattamente $k$ multipli, per un qualche $k$ tra $1$ e $n$; questi numeri non possono dividersi l'un l'altro: se $b$ ha esattamente $k$ multipli, e $a|b$, allora $a$ deve avere almeno $k+1$ multipli. In definitiva, ho ottenuto $m+1$ numeri in cui nessuno divide l'altro.
NOTA: con la stessa dimostrazione, si dimostra che, data una successione di $mn+1$ numeri reali, possiamo trovare o una sottosuccessione crescente di $n+1$ elementi o una decrescente di $m+1$ elementi.