$m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i+1}$

Messaggio 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)
The only goal of science is the honor of the human spirit.
bummer
Messaggi: 3
Iscritto il: 18 set 2012, 00:05

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio da bummer »

Testo nascosto:
sia t il minimo numero di catene (secondo l'ordine dato dalla divisione) che partiziona l'insieme, per Dilworth se $ t\geq m+1 $ abbiamo finito, altrimenti deve esistere una catena con almeno $ \lceil \frac{mn+1}{t} \rceil \geq \lceil \frac{nm+1}{m}\rceil = n+1 $ elementi.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio da jordan »

bummer ha scritto:per Dilworth
Scusa l'ignoranza, ma cos'è?
The only goal of science is the honor of the human spirit.
bummer
Messaggi: 3
Iscritto il: 18 set 2012, 00:05

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio 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.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio da jordan »

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.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio 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... :roll:
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio 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...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio 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..
The only goal of science is the honor of the human spirit.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio da fph »

jordan ha scritto: Wow sai addirittura l'anno in cui è stato fatto?
jordan, poche righe più su ha scritto: (Putnam 1966)
:roll:
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio da jordan »

fph ha scritto: (Putnam 1966)
:roll:
Di solito non metto la fonte, ma hai ragione, non ho fatto caso al fatto che l'avessi scritto io stesso :|
The only goal of science is the honor of the human spirit.
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: $m+1$ tali che $x_i \nmid x_{i+1}$ o $n+1$ che $x_i|x_{i

Messaggio 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.
Rispondi