Keresés

Részletes keresés

A hozzászólás:
Gergo73 Creative Commons License 2006-10-31 17:53:38 239

Örömmel jelentem, hogy megoldottam ezt a feladatomat, a válasz az, hogy NEM.

Állítás. Van olyan f:N->N permutáció, ami nem monoton egyetlen 6-tagú számtani sorozaton sem.

Bizonyítás. Először vegyük észre, hogy a természetes számok minden intervallumának van olyan "szép" permutációja, ami nem monoton egyetlen 3-tagú számtani sorozaton sem. Ezt elég belátni az {1,2,...,2n-1} alakú intervallumokra, ott pedig jó konstrukciót ad az n-hosszú bináris jegysorozatok megfordítása. Ezek után a tételben kívánt f permutációt úgy adjuk meg, hogy minden [5n,5n+1) alakú intervallumnak külön vesszük egy-egy "szép" permutációját és aztán vesszük ezek unióját. Belátjuk, hogy f jó. Legyen ehhez a1<...<a6 egy tetszőleges 6-tagú számtani sorozat. Legyen n olyan, hogy 5n<=a2<5n+1. Ekkor a6=5a2-4a1<5a2<5n+2, tehát vagy az [5n,5n+1) intervallum tartalmazza az a2<a3<a4 számtani sorozatot, vagy az [5n+1,5n+2) intervallum tartalmazza az a4<a5<a6 számtani sorozatot. Mindkét esetben azt kapjuk, hogy f nem monoton az ai-ken a konstrukció miatt.

 

Megjegyzés. Továbbra is kérdés, hogy az állítás élesíthető-e 5-tagú, netán 4-tagú számtani sorozatokra. 3-tagú számtani sorozatokra nem igaz a tétel, amint az könnyen belátható (minden f növekszik végtelen sok 3-tagú számtani sorozaton, még az első tagot is tetszőlegesen elő lehet írni).

 

Előzmény:
Gergo73 Creative Commons License 2003-03-11 01:12:52 153
A hibas bizonyitasom felvet egy kerdest, ami szerintem nem erdektelen es nem nyilvanvalo. Legyen f:w->w injektiv. Igaz-e mindig, hogy f monoton tetszolegesen hosszu szamtani sorozaton?

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!