[Kombinatoryka] Zbiory wierzchołków n-kątów foremnych, trójkąty
: 29 gru 2008, o 18:15
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.
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.