---

Hej gruppe!

I bogen "Manden som kun elskede tal" af Paul Hoffman (dansk udgave,
Borgen 2001) omtales Ramsey-teori, og der gives et eksempel, der - som
jeg læser det - går ud på at uanset hvordan man blander tallene 1-101,
så vil der altid være en sekvens på mindst 11 tal, hvor sekvensen er
stigende eller faldende.

Det kan da ikke passe, eller hvad er det jeg misforstår? Hvis man fx.
stiller de 101 tal op på følgende måde:
1,101,2,100,3,99,...49,53,50,52,51 så er der da ingen sekvens på
mindst 11 tal, hvor sevensen er stigende eller faldende; faktisk så
skifter den hele tiden

qrt

---

Hej qrt

> I bogen "Manden som kun elskede tal" af Paul Hoffman (dansk udgave,
> Borgen 2001) omtales Ramsey-teori, og der gives et eksempel, der - som
> jeg læser det - går ud på at uanset hvordan man blander tallene 1-101,
> så vil der altid være en sekvens på mindst 11 tal, hvor sekvensen er
> stigende eller faldende.
>
> Det kan da ikke passe, eller hvad er det jeg misforstår? Hvis man fx.
> stiller de 101 tal op på følgende måde:
> 1,101,2,100,3,99,...49,53,50,52,51 så er der da ingen sekvens på
> mindst 11 tal, hvor sevensen er stigende eller faldende; faktisk så
> skifter den hele tiden

Fidusen er at man har lov til at "hoppe over".

Tallene 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 og 11 står i rækkefølge i dit
eksempel. Det er en delsekvens på 11 tal, som er voksende.


Hvis du vil eksperimentere, så er det nemmere med en lidt kortere
talrække.

Med 10 tal kan man altid finde en delfølge på 3, som enten er
voksende eller aftagende.

I bogen vises en rækkefølge af 100 tal, hvor man ikke kan
finde en 10-delfølge som enten er voksen eller aftagende.
Prøv at se om du kan finde en rækkefølge af 9 tal, hvor man
ikke kan finde 3-delfølger.

--
Jens Axel Søgaard

---

Jens Axel Søgaard <usenet@soegaard.net> writes:

> Prøv at se om du kan finde en rækkefølge af 9 tal, hvor man
> ikke kan finde 3-delfølger.

Det er vist ikke muligt, hvis jeg forstår Erdos-Szekeres teorem rigtige
<URL:http://mathworld.wolfram.com/Erdos-SzekeresTheorem.html>

De 9 = 2*4+1 har en række af ni forskellige reelle tal en monotont voksende
eller faldende delsekvens af længde 3 eller 5 (og derfor specielt 3).

Men du sagde også:
> I bogen vises en rækkefølge af 100 tal, hvor man ikke kan
> finde en 10-delfølge som enten er voksen eller aftagende.

Da 100 = 9 * 11 + 1, så burde der være en 10-delfølge.

Har jeg misset noget?
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen wrote:
> Jens Axel Søgaard <usenet@soegaard.net> writes:
>
>>Prøv at se om du kan finde en rækkefølge af 9 tal, hvor man
>>ikke kan finde 3-delfølger.
>
> Det er vist ikke muligt, hvis jeg forstår Erdos-Szekeres teorem rigtige
> <URL:http://mathworld.wolfram.com/Erdos-SzekeresTheorem.html>

Den kendte jeg ikke, takker.

> De 9 = 2*4+1 har en række af ni forskellige reelle tal en monotont voksende
> eller faldende delsekvens af længde 3 eller 5 (og derfor specielt 3).

Bogens udgave af sætningen er:

"...: to guarantee either a rising or falling sequence
of length n+1, you need n^2+1 numbers; with n^2 numbers
you may not get it."

Jeg troede (fejlagtigt) at ovenstående skulle læses, som om,
det altid gik galt, når man kun brugte n^2 tal - men det lader
til at det skal læses som "for nogle n går det galt".

Hm. Mon det er dem hvor a=b?

Hvis a=b=2 så er n=5 og man skal lede efter 3-delfølger.
Så skulle 4 tal ikke være nok:

3 4 1 2

Hvis a=b=3 så er n=10 og man skal lede efter 4-delfølger.
Så skulle 9 tal ikke være nok:

7 8 9 4 5 6 1 2 3

>>I bogen vises en rækkefølge af 100 tal, hvor man ikke kan
>>finde en 10-delfølge som enten er voksen eller aftagende.
>
> Da 100 = 9 * 11 + 1, så burde der være en 10-delfølge.

Rækkefølgen i bogen er:

91 92 93 94 95 96 97 98 99 100 81 82 83
84 85 86 87 88 89 90 71 72 73 74 75 76
77 78 79 80 61 62 63 64 65 66 67 68 69
70 51 52 53 54 55 56 57 58 59 60 41 42
43 44 45 46 47 48 49 50 31 32 33 34 35
36 37 38 39 40 21 22 23 24 25 26 27 28
29 30 11 12 13 14 15 16 17 18 19 20 1 2 3
4 5 6 7 8 9 10

Uh! Der står faktisk "100 tal, hvor man ikke kan finde
en 11-delfølge".

> Har jeg misset noget?

Tværtimod.

Ved du forresten, hvor man finder et bevis for
Erdös-Szekeres-sætningen?

--
Jens Axel Søgaard

---

Jens Axel Søgaard <usenet@soegaard.net> writes:

> Hvis a=b=3 så er n=10 og man skal lede efter 4-delfølger.
> Så skulle 9 tal ikke være nok:
>
> 7 8 9 4 5 6 1 2 3

Det giver endda en god idé til at konstruere sekvensen
generelt :)


> Ved du forresten, hvor man finder et bevis for
> Erdös-Szekeres-sætningen?

Ikke den fjerneste idé, jeg havde aldrig hørt om det før jeg
Googlede for at finde ud af hvad Ramsey-teori er for en fisk.

Hmm, men Google giver også siden:
<URL:http://www.ams.org/new-in-math/cover/mulcahy7.html>
som siger
---
For a proof of the Erdös-Szekeres theorem see page 124 of Martin
Aigner & Gunter M. Ziegler's Proofs from The Book (Springer, 1998).
---
Det svarer så på spørgsmålet. Google ved alt!

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen wrote:

>>Ved du forresten, hvor man finder et bevis for
>>Erdös-Szekeres-sætningen?

> Ikke den fjerneste idé, jeg havde aldrig hørt om det før jeg
> Googlede for at finde ud af hvad Ramsey-teori er for en fisk.

Jeg har på fornemmelsen, at den sætning er et meget lille
hjørne af Ramsey-teori.

> Hmm, men Google giver også siden:
> <URL:http://www.ams.org/new-in-math/cover/mulcahy7.html>
> som siger
> ---
> For a proof of the Erdös-Szekeres theorem see page 124 of Martin
> Aigner & Gunter M. Ziegler's Proofs from The Book (Springer, 1998).

Hov! Den har jeg da på reolen. Bladre. Sørme så. Beviset er kort
og elementært, men ikke umiddelbart indlysende.

--
Jens Axel Søgaard

---

Jens Axel Søgaard <usenet@soegaard.net> writes:

> Lasse Reichstein Nielsen wrote:
>
> > For a proof of the Erdös-Szekeres theorem see page 124 of Martin
> > Aigner & Gunter M. Ziegler's Proofs from The Book (Springer, 1998).
>
> Hov! Den har jeg da på reolen. Bladre. Sørme så. Beviset er kort
> og elementært, men ikke umiddelbart indlysende.

Altså et rigtigt "Proof from the Book".

For ikke-indviede: Der hentydes til "Guds bog med matematiske
beviser", som indholder de mest elegante beviser på matematiske
sætninger.

Torben

---

Torben Ægidius Mogensen wrote:
> Jens Axel Søgaard <usenet@soegaard.net> writes:
>>Lasse Reichstein Nielsen wrote:

>>>For a proof of the Erdös-Szekeres theorem see page 124 of Martin
>>>Aigner & Gunter M. Ziegler's Proofs from The Book (Springer, 1998).
>>
>>Hov! Den har jeg da på reolen. Bladre. Sørme så. Beviset er kort
>>og elementært, men ikke umiddelbart indlysende.

> Altså et rigtigt "Proof from the Book".
>
> For ikke-indviede: Der hentydes til "Guds bog med matematiske
> beviser", som indholder de mest elegante beviser på matematiske
> sætninger.

Bogen kan forresten varmt anbefales, hvis man kan lidt
(førsteårs)-matematik.

--
Jens Axel Søgaard

---

Scripsit Jens Axel Søgaard <usenet@soegaard.net>
> Torben Ægidius Mogensen wrote:

>> For ikke-indviede: Der hentydes til "Guds bog med matematiske
>> beviser", som indholder de mest elegante beviser på matematiske
>> sætninger.

> Bogen kan forresten varmt anbefales, hvis man kan lidt
> (førsteårs)-matematik.

Øh, ja. Men den er stort set ikke til at opdrive.

--
Henning Makholm "I Guds Faders namn, och Sonens, och den Helige
Andes! Bevara oss från djävulens verk och från Muhammeds,
den förbannades, illfundigheter! Med dig är det värre än med
någon annan, ty att lyssna till Muhammed är det värsta av allt."

---

Henning Makholm wrote:
> Scripsit Jens Axel Søgaard <usenet@soegaard.net>

>>Bogen kan forresten varmt anbefales, hvis man kan lidt
>>(førsteårs)-matematik.
>
> Øh, ja. Men den er stort set ikke til at opdrive.

Det var jeg ikke klar over.

--
Jens Axel Søgaard

---

Scripsit Jens Axel Søgaard <usenet@soegaard.net>
> Henning Makholm wrote:
>> Scripsit Jens Axel Søgaard <usenet@soegaard.net>

>>>Bogen kan forresten varmt anbefales, hvis man kan lidt
>>>(førsteårs)-matematik.

>> Øh, ja. Men den er stort set ikke til at opdrive.

> Det var jeg ikke klar over.

Vi er RIGTIG MANGE på verdensplan der gerne vil vide det hvis du
kender et sted hvor man kan låne/købe den.

--
Henning Makholm "Manden med det store pindsvin er
kommet vel ombord i den grønne dobbeltdækker."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
> > Henning Makholm wrote:
> >> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
>
> >>>Bogen kan forresten varmt anbefales, hvis man kan lidt
> >>>(førsteårs)-matematik.
>
> >> Øh, ja. Men den er stort set ikke til at opdrive.
>
> > Det var jeg ikke klar over.
>
> Vi er RIGTIG MANGE på verdensplan der gerne vil vide det hvis du
> kender et sted hvor man kan låne/købe den.

Fra forlaget?

<http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-10042-22-9255958-0,00.html?changeHeader=true>

Simon

--
Dr Simon Kristensen <http://www.maths.ed.ac.uk/~simonk/>
School of Mathematics
University of Edinburgh
Scotland

---

Scripsit Simon Kristensen <sik@imf.au.dk>
> Henning Makholm <henning@makholm.net> writes:
>> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
>> > Henning Makholm wrote:
>> >> Scripsit Jens Axel Søgaard <usenet@soegaard.net>

>> >>>Bogen kan forresten varmt anbefales, hvis man kan lidt
>> >>>(førsteårs)-matematik.

>> >> Øh, ja. Men den er stort set ikke til at opdrive.

>> > Det var jeg ikke klar over.

>> Vi er RIGTIG MANGE på verdensplan der gerne vil vide det hvis du
>> kender et sted hvor man kan låne/købe den.

> <http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-10042-22-9255958-0,00.html?changeHeader=true>

Det er da kun et uddrag.

--
Henning Makholm "Lad min høne være."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Simon Kristensen <sik@imf.au.dk>
> > Henning Makholm <henning@makholm.net> writes:
> >> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
> >> > Henning Makholm wrote:
> >> >> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
>
> >> >>>Bogen kan forresten varmt anbefales, hvis man kan lidt
> >> >>>(førsteårs)-matematik.
>
> >> >> Øh, ja. Men den er stort set ikke til at opdrive.
>
> >> > Det var jeg ikke klar over.
>
> >> Vi er RIGTIG MANGE på verdensplan der gerne vil vide det hvis du
> >> kender et sted hvor man kan låne/købe den.
>
> > <http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-10042-22-9255958-0,00.html?changeHeader=true>
>
> Det er da kun et uddrag.

Ahhh.... nu er jeg med. Jeg er ikke helt sikker på, hvilket forlag der
har udgivet den bog, du taler om

Simon

--
Dr Simon Kristensen <http://www.maths.ed.ac.uk/~simonk/>
School of Mathematics
University of Edinburgh
Scotland