Układy regularne

[mol_ksiazkowy]

Jest \(\displaystyle{ n \geq 4}\) punktów na okręgu, które poetykietowane są liczbami \(\displaystyle{ 1, ..., n}\). Dowolne niesąsiednie punkty z etykietami \(\displaystyle{ a}\) i \(\displaystyle{ b}\) nazywa się regularnymi (lub: układem regularnym), jeśli wszystkie liczby na łuku \(\displaystyle{ ab}\) bądź na łuku \(\displaystyle{ ba}\) są mniejsze od \(\displaystyle{ a}\) i od \(\displaystyle{ b}\).
Udowodnić, że jest ich \(\displaystyle{ n-3}\) (układów regularnych).

[arek1357]

Coś mi się nie zgadza ponieważ jeżeli na okręgu umieścimy punkty w kolejności np.:

\(\displaystyle{ 1,2,3,4}\)

to będą dwa układy spełniające warunki etykiet:

\(\displaystyle{ (4,3) \rightarrow 1,2}\) między nimi na jednym z łuków

oraz:

\(\displaystyle{ (2,4) \rightarrow 1}\)

Jak widać są dwa układy, czyli nie.: \(\displaystyle{ 4-3=1}\)

Chyba że źle odczytałem intencje słowa "bądź" i powinno być to jako i a nie lub...

[Blazo2000]

arek1357 \(\displaystyle{ a}\) i \(\displaystyle{ b}\) mają nie sąsiadować ze sobą, w tym układzie \(\displaystyle{ 3}\) i \(\displaystyle{ 4}\) są sąsiadami, więc nie są układem regularnym.

-- 5 mar 2019, o 14:33 --

Rozwiązanie:

Ukryta treść:    

Przeprowadzimy dowód indukcyjny. Nazwijmy sobie parę etykietowanych punktów na okręgu dobrą, wtedy i tylko wtedy gdy nie leżą one obok siebie na tym okręgu. Para punktów może być regularna jedynie wtedy, gdy jest dobra.
Wniosek \(\displaystyle{ 1}\)
Para \(\displaystyle{ (1, a)}\) nie jest regularna, dla dowolnego \(\displaystyle{ a}\).
Dowód:
Aby ta para była regularna to musi być dobra, więc na każdym z łuków \(\displaystyle{ 1a}\), \(\displaystyle{ a1}\) leży jakiś punkt większy od \(\displaystyle{ 1}\), więc para ta nie jest regularna.
Dla \(\displaystyle{ n=4}\) mamy dwie pary dobre, z których jedna zawiera \(\displaystyle{ 1}\), więc nie jest regularna. Druga para \(\displaystyle{ (a, b)}\) na jednym z łuków \(\displaystyle{ ab}\) lub \(\displaystyle{ ba}\) zawiera tylko \(\displaystyle{ 1<a, b}\), więc jest regularna. Teraz pokażemy dowód kroku indukcyjnego. Dodanie \(\displaystyle{ 1}\) do każdej z etykiet niczego nie zmienia, więc skoro każde etykietowanie liczbami \(\displaystyle{ 1, 2, ..., n}\) ma \(\displaystyle{ n-3}\) pary regularnych, to także każde etykietowanie liczbami \(\displaystyle{ 2, 3, ..., n+1}\) ma \(\displaystyle{ n-3}\) pary regularnych. Dodajmy teraz pomiędzy dowolne dwa punkty \(\displaystyle{ X, Y}\) punkt \(\displaystyle{ 1}\). Skoro dodaliśmy punkt o najmniejszej etykiecie, to wszystkie pary regularne pozostały regularne, dodatkowo żadna nowo utworzona para \(\displaystyle{ (1, a)}\) nie jest regularna. Co do par \(\displaystyle{ (a, b)}\), które nie były regularne, ale były dobre to oczywiście nadal nie są regularne, bo na każdym z łuków \(\displaystyle{ ab}\) i \(\displaystyle{ ba}\) nadal znajduje się liczba większa od \(\displaystyle{ a}\) lub \(\displaystyle{ b}\). Pozostaje sprawdzić zatem pary, które nie były dobre, a spośród tych par tylko para \(\displaystyle{ X, Y}\) stała się dobra, jest ona także regularna, ponieważ na jednym z łuków \(\displaystyle{ XY}\) lub \(\displaystyle{ YX}\) znajduje się tylko punkt \(\displaystyle{ 1}\), oznacza to, że liczba par regularnych zwiększyła się o \(\displaystyle{ 1}\), co kończy dowód indukcyjny.

[arek1357]

To w takim razie masz racje...