$m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$
$m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$
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)
(Putnam 1966)
The only goal of science is the honor of the human spirit.
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Testo nascosto:
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Scusa l'ignoranza, ma cos'è?bummer ha scritto:per Dilworth
The only goal of science is the honor of the human spirit.
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
http://en.wikipedia.org/wiki/Dilworth's_theoremjordan ha scritto:Scusa l'ignoranza, ma cos'è?bummer ha scritto:per Dilworth
È 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
Grazie del link. Comunque puo' essere, non sono mai stato una cima qui e in geometria
The only goal of science is the honor of the human spirit.
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
È 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...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
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...
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
Wow sai addirittura l'anno in cui è stato fatto?EvaristeG ha scritto:Quindi se qualcuno che non sa cos'è sta cosa e non ha guardato il link vuole provarci, tanto meglio...
Ps. In ogni erano sufficienti due riche di pigenhole, ma conoscere teoremi del genere non fa mai male..
The only goal of science is the honor of the human spirit.
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
jordan ha scritto: Wow sai addirittura l'anno in cui è stato fatto?
jordan, poche righe più su ha scritto: (Putnam 1966)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
Di solito non metto la fonte, ma hai ragione, non ho fatto caso al fatto che l'avessi scritto io stessofph ha scritto: (Putnam 1966)
The only goal of science is the honor of the human spirit.
Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i
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.
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.