[Kombinatoryka] Zbiory wierzchołków n-kątów foremnych, trójkąty

[patry93]

Witam.

Dla jakich liczb naturalnych \(\displaystyle{ n}\) zbiór wszystkich wierzchołków \(\displaystyle{ n}\)-kąta foremnego można podzielić na dwa takie podzbiory, aby w żadnym z tych podzbiorów nie znajdowały się trzy punkty, które są wierzchołkami trójkąta równoramiennego?

Oczywiście \(\displaystyle{ n \geqslant 3}\) i "z braku laku" lecę na przypadki
\(\displaystyle{ 1^{ \circ} \ n=3}\)
Nie ma co długo szukać, bierzemy 2 wierzchołki do jednego zbioru i jeden pozostały do drugiego i wszystko gra, więc \(\displaystyle{ n=3}\) spełnia warunki zadania.
\(\displaystyle{ 2^{ \circ} \ n=4}\)
Jeden zbiór zawiera dowolne dwa wierzchołki, drugi tak samo - git, więc \(\displaystyle{ n=4}\) też pasuje.
\(\displaystyle{ 3^{ \circ} \ n=5}\)
Jeśli jeden zbiór jest 1-elementowy, to w drugim będą 3 kolejne wierzchołki dające trójkąt.
Jeśli jeden zbiór jest 2-elementowy, to albo drugi ma 3 kolejne wierzchołki (co daje trójkąt), albo ma 2 kolejne i jeden równo oddalony od wierzchołków ze zbioru pierwszego, co również daje trójkąt (2 kolejne są równo oddalone od trzeciego). Zatem \(\displaystyle{ n=5}\) nie spełnia warunków zadania.
\(\displaystyle{ 4^{ \circ} \ n=6}\)
Jeśli jeden ma 1 element, to w drugim są 3 kolejne dające trójkąt.
Jeśli jeden ma 2 elementy, to wybieramy z tego zbioru pewien wierzchołek A, oraz taki drugi wierzchołek B, że AB przechodzi przez środek sześciokąta foremnego i A o oraz B są równo oddalone od tego środka. Wówczas pozostałe wierzchołku z drugiego zbioru nie utworzą trójkąta równoramiennego, więc \(\displaystyle{ n=6}\) pasuje.
Dalsze sprawdzanie "co jeden" chyba mija się z celem, więc uogólniam.
\(\displaystyle{ 5^{ \circ} \ n \geqslant 7 \lor \ n=2k+1 \ , \ k \in \mathbb{N}}\)
Możliwe kombinacje liczby elementów zbiorów (x, y), gdzie x to ilość elementów zbioru X oraz analogicznie dla Y, przy czym \(\displaystyle{ x+y=n}\) to:
\(\displaystyle{ (1, \ n-1), \ (2, \ n-2), \ldots , \ ( \frac{n-1}{2}+1 , \ \frac{n+1}{2}+1), \ ( \frac{n-1}{2}, \ \frac{n+1}{2} )}\)
Nie bardzo wiem jak to teraz ugryźć, ale pomyślałem sobie tak: ostatnia moja zapisana kombinacja jest taka, że różnica w ilości elementów wynosi 1. Więc jeśli w zbiorze posiadającym największą ilość elementów z tej kombinacji znajdziemy trójkąt równoramienny, to tym bardziej znajdziemy takowy w pozostałych kombinacjach, ponieważ zawsze znajdziemy tam zbiór o większej ilości elementów.
Muszę więc rozważyć zbiór \(\displaystyle{ \frac{n+1}{2}}\)-elementowy.
Skoro \(\displaystyle{ n \geqslant 7 \ to \ \frac{n+1}{2} \geqslant 4 \ oraz \ \frac{n-1}{2} \geqslant 3}\)
Ech, niestety nie mam pojęcia jak teraz wykazać możność albo niemożność znalezienia takiego trójkąta.... :/

[EDIT]
Troszkę dalej mam, choć to pewnie nic nie daje...
Niech rozpatrywany zbiór będzie zbiorem X.
\(\displaystyle{ n= 2 \frac{n+1}{2}-1}\) więc na mocy ZSD zawsze w tym zbiorze znajdą się 2 wierzchołki kolejne (niech będą to wierzch. A i B). Jeśli znajdziemy taki punkt \(\displaystyle{ C\in X}\), że jest kolejnym wierzchołkiem po A lub B, to otrzymamy trójkąt równoramienny, więc załóżmy, że na tych miejscach wierzchołku należą do zbioru Y. Jeżeli punkt C będzie odbiciem względem środka figury takiego punktu D, że D leży w połowie odcinka AB to również otrzymamy trójkąt równoramienny ABC.
Można też zauważyć, że pomiędzy opisywanym punktem C, a punktami A i B są po obu stronach \(\displaystyle{ \frac{n-3}{2}}\) wierzchołki.
Czyli jak na razie wiem, że te trzy punkty należą do zbioru Y, aby nie mieć trójkąta równoramiennego.
Dalej już mi się pomysły wyczerpują....

Z góry dziękuję za pomoc.

[timon92]

Rozważ sobie jeszcze osobno \(\displaystyle{ n=7 \lor n=8}\)
Numerujemy punkty: \(\displaystyle{ 1, 2, 3, ... , n}\) dla \(\displaystyle{ n \geqslant 9}\). Łatwo wykazać, że istnieje sytuacja XYX (lub YXY, wszystko jedno). Gdyby tak nie było, to musiałoby być X.Y.X.Y.X (kropka to punkt dowolny, tj. może należeć do obu zbiorów), no ale te trzy iksy tworzą szukany trójkąt. Zatem mamy sytuację XYX. Bierzemy ...XYX... , no ale widać, że musi być .Y.XYX.Y. , ale trzy igreki tworzą szukany trójkąt.

[patry93]

Ok, rozpisałem sobie dla \(\displaystyle{ n=7 \ oraz \ n=8}\), ale może nie będę tego pisał na forum, bo właściwie bardzo to przypomina przypadki 3 i 4 (przy czym dla tych 'n' oczywiście nie można wierzchołków podzielić na takie podzbiory).
Co do przypadku dla \(\displaystyle{ n \geqslant 9}\) - nie bardzo rozumiem.... :/
Czy tak jak napisałem w przypadku nr 5 rozważasz podzbiory, których ilość elementów różni się o 1?
Bardzo proszę o rozpisanie w miarę możliwości tego, bo nie mogę się połapać w Twoich oznaczeniach "iksowo-igerkowo-kropkowych"

[timon92]

Załóżmy, że punkty można rozdzielić na dwa zbiory tak, aby nie było tego trójkąta równoramiennego. Punkty będę nazywał czarnymi i białymi.

W tym celu wykazuję, że można wskazać dwa jednokolorowe punkty (dla ustalenia uwagi czarne) oddzielone jednym punktem białym. Dowód nie wprost. Zakładamy, że nie można wskazać takich punktów. Wówczas jeśli pierwszy punkt jest biały, to trzeci jest czarny, piąty jest biały, siódmy jest czarny i dziewiąty jest biały. No ale widzimy, że pierwszy, piąty i dziewiąty punkt tworzą nam jednokolorowy trójkąt równoramienny. Sprzeczność z założeniem.

A zatem możemy wskazać sytuację, że dwa czarne punkty są oddzielone jednym białym. Możemy sobie przyjąć, że punkt czwarty i szósty są czarne, a punkt piąty jest biały. Zastanówmy się, jakiego koloru musi być punkt drugi. Jeśli jest czarny, to punkty numer 2, 4, 6 tworzą trójkąt równoramienny. Zatem punkt 2 jest biały. Analogicznie, punkt 8 musi być biały. I teraz zauważamy, że punkty 2, 5 i 8 tworzą jednokolorowy trójkąt równoramienny. Sprzeczność z założeniem.

Więc dla \(\displaystyle{ n \geqslant 9}\) zawsze, niezależnie od rozdzielenia punktów na dwa zbiory, dostaniemy trójkąt równoramienny. Założenie \(\displaystyle{ n \geqslant 9}\) zostało wykorzystane w akapicie drugim.

[patry93]

Wówczas jeśli pierwszy punkt jest biały, to trzeci jest czarny, piąty jest biały, siódmy jest czarny i dziewiąty jest biały. No ale widzimy, że pierwszy, piąty i dziewiąty punkt tworzą nam jednokolorowy trójkąt równoramienny. Sprzeczność z założeniem.

Hm.... zaraz.... dlaczego wybierasz co drugi punkt?
Rozrysowałem sobie to co napisałeś i skoro dochodzimy do sprzeczności na końcu, to jeden z tych białych punktów musi być czarny, prawda? Ale nawet gdy stanie się czarny to nie uzyskujemy dwóch czarnych punktów oddzielonych białym przecież... chyba, że punkt drugi pokoloruję na czarno, ale równie dobrze mogę go pomalować na biało i nie będę miał trójkąta równoramiennego...

A zatem możemy (...)

To pominę, bo nie rozumiem tego wyżej, ale przeczytałem i ...

Założenie \(\displaystyle{ n \geqslant 9}\) zostało wykorzystane w akapicie drugim

Ja tam widzę ciągle \(\displaystyle{ n=9}\)....


Przy okazji tak się zastanawiam - czy nie można od np. \(\displaystyle{ n=7}\) zrobić dalej indukcją?

[timon92]

Hm.... zaraz.... dlaczego wybierasz co drugi punkt?

Może tak będzie prościej:
Chcemy wykazać, że można wskazać dwa jednokolorowe punkty oddzielone jednym innym (wiadomo, że musi być drugiego koloru, ale nie korzystamy z tego). Dowodzimy nie wprost, to jest zakładamy, że nie ma takich punktów, czyli, że co drugi punkt jest róznego koloru. Ale to oznacza, że co czwarty jest tego samego koloru. Skoro \(\displaystyle{ n=9}\), to pierwszy, piąty i dziewiąty punkt są tego samego koloru, i one tworzą trójkąt równoramienny. Zatem założenie, że co drugi punkt jest innego koloru jest fałszywe. Więc można wskazać dwa jednokolorowe punkty oddzielone jednym innym.

Dla \(\displaystyle{ n>9}\) bierzemy dziewięć kolejnych punktów i rozumujemy tak, jak wyżej.

[patry93]

Może tak będzie prościej: (...)

Tak jest 10x prościej! Nadal nie rozumiem tego poprzedniego, ale to już łapię i tyle mi wystarczy

A co do indukcji - wie ktoś czy można?

[limes123]

Rozwaz sobie przypadki 3-10 recznie (troche ich jest ale wiekszosc prosta). Dla n>10 mozna tak:
zalozmy, ze mamy podzial i nie ma rownoramiennych. Latwo wtedy wykazemy, ze znajdziemy dwa sasiednie punkty tego samego zbioru (powiedzmy A). Mamy taka sytuacje
B A A B
bo nie ma rownoramiennych zgodnie z zalozeniem, czyli musi tez byc
B A A B . . A
gdzie kropki sa punktami zbioru (nie wiemy jakiego) i musi byc
B . B A A B . . A
zatem zgodnie z zalozeniem musi tez byc
A . B . B A A B . . A
ale wtedy wytluszczone A tworza rownoramienny - sprzecznosc.