Środki odcinków
- mol_ksiazkowy
- Użytkownik
- Posty: 11415
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Środki odcinków
Na płaszczyźnie jest zbiór \(\displaystyle{ X}\) złożony z \(\displaystyle{ n}\) różnych punktów. Zbiór \(\displaystyle{ Y}\) to zbiór środków odcinków, których końce są elementami \(\displaystyle{ X}\). Ile maksymalnie a ile minimalnie elementów może mieć zbiór \(\displaystyle{ Y }\)
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Środki odcinków
Maksymalnie to oczywiście może być \(\displaystyle{ \frac{n\left( n-1\right) }{2}}\) punktów- łączymy punkt każdy z każdym i znajdujemy środek takiego odcinka. Widać, że działa to dla \(\displaystyle{ n=2}\), i dla \(\displaystyle{ n=3}\). Dalej to nie wiem...
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Środki odcinków
Przy minimach wydaje się, że figury środkowosymetryczne mają najmniej punktów typu \(\displaystyle{ Y}\) a więc np. punktowe foremniaki...
Bo każda figura ograniczona ma tylko jeden środek symetrii...Ale może są jeszcze mniejsze Y-greki
Bo każda figura ograniczona ma tylko jeden środek symetrii...Ale może są jeszcze mniejsze Y-greki
-
- Użytkownik
- Posty: 1594
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 247 razy
Re: Środki odcinków
N-kąt foremny ma n/2 odcinków o wspólnym środku, ale równie dobrze możemy te n punktów umieścić na jednej prostej w taki sposób, żeby były symetrycznie względem środka, też n/2 będzie miało wspólny
- Dasio11
- Moderator
- Posty: 10227
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Środki odcinków
Minimalna moc zbioru \(\displaystyle{ Y}\) wynosi \(\displaystyle{ 2n-3}\) i jest osiągana dla \(\displaystyle{ X = \{ 0, 1, \ldots, n-1 \} \times \{ 0 \}}\).
Istotnie: rozważmy dowolny zbiór \(\displaystyle{ X \subseteq \mathbb{R}^2}\) mocy \(\displaystyle{ n}\). Dla każdej pary różnych punktów \(\displaystyle{ p, q \in X}\) istnieje dokładnie jedna prosta przechodząca przez początek układu współrzędnych, taka że rzuty prostopadłe \(\displaystyle{ p}\) i \(\displaystyle{ q}\) na tę prostą są identyczne - oczywiście jest to prosta prostopadła do wektora \(\displaystyle{ \vec{pq}}\). Istnieje zatem taka prosta, na którą rzuty wszystkich punktów z \(\displaystyle{ X}\) są różne. Poprzez obrót możemy założyć, że tą prostą jest \(\displaystyle{ \mathbb{R} \times \{ 0 \}}\), tj. pierwsze współrzędne punktów z \(\displaystyle{ X}\) są różne.
Mamy zatem \(\displaystyle{ X = \{ (x_i, y_i) : 1 \le i \le n \}}\), gdzie \(\displaystyle{ x_1 < \ldots < x_n}\). Wtedy też
\(\displaystyle{ \frac{x_1+x_2}{2} < \frac{x_1+x_3}{2} < \ldots < \frac{x_1+x_n}{2} < \frac{x_2+x_n}{2} < \ldots < \frac{x_{n-1}+x_n}{2}}\).
Oczywiście \(\displaystyle{ Y = \left\{ \left( \frac{x_i+x_j}{2}, \frac{y_i+y_j}{2} \right) : 1 \le i < j \le n \right\}}\). Z powyższych rozważań wynika, że pewne \(\displaystyle{ 2n-3}\) spośród wszystkich elementów \(\displaystyle{ Y}\) mają różne pierwsze współrzędne. Stąd \(\displaystyle{ |Y| \ge 2n-3}\), zatem w istocie jest to najmniejsza możliwa moc \(\displaystyle{ Y}\).
Istotnie: rozważmy dowolny zbiór \(\displaystyle{ X \subseteq \mathbb{R}^2}\) mocy \(\displaystyle{ n}\). Dla każdej pary różnych punktów \(\displaystyle{ p, q \in X}\) istnieje dokładnie jedna prosta przechodząca przez początek układu współrzędnych, taka że rzuty prostopadłe \(\displaystyle{ p}\) i \(\displaystyle{ q}\) na tę prostą są identyczne - oczywiście jest to prosta prostopadła do wektora \(\displaystyle{ \vec{pq}}\). Istnieje zatem taka prosta, na którą rzuty wszystkich punktów z \(\displaystyle{ X}\) są różne. Poprzez obrót możemy założyć, że tą prostą jest \(\displaystyle{ \mathbb{R} \times \{ 0 \}}\), tj. pierwsze współrzędne punktów z \(\displaystyle{ X}\) są różne.
Mamy zatem \(\displaystyle{ X = \{ (x_i, y_i) : 1 \le i \le n \}}\), gdzie \(\displaystyle{ x_1 < \ldots < x_n}\). Wtedy też
\(\displaystyle{ \frac{x_1+x_2}{2} < \frac{x_1+x_3}{2} < \ldots < \frac{x_1+x_n}{2} < \frac{x_2+x_n}{2} < \ldots < \frac{x_{n-1}+x_n}{2}}\).
Oczywiście \(\displaystyle{ Y = \left\{ \left( \frac{x_i+x_j}{2}, \frac{y_i+y_j}{2} \right) : 1 \le i < j \le n \right\}}\). Z powyższych rozważań wynika, że pewne \(\displaystyle{ 2n-3}\) spośród wszystkich elementów \(\displaystyle{ Y}\) mają różne pierwsze współrzędne. Stąd \(\displaystyle{ |Y| \ge 2n-3}\), zatem w istocie jest to najmniejsza możliwa moc \(\displaystyle{ Y}\).