Łamana w przestrzeni

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Thingoln
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 27 lip 2019, o 22:19
Płeć: Mężczyzna
Lokalizacja: województwo śląskie
Podziękował: 48 razy
Pomógł: 13 razy

Łamana w przestrzeni

Post autor: Thingoln » 3 sie 2020, o 23:45

Witajcie. Rozwiązywałem takie zadanie i moje rozwiązanie (o ile jest poprawne) wygląda trochę inaczej niż wzorcowe i byłbym wdzięczny, gdyby ktoś je sprawdził albo wskazał błąd. :D
Dany jest taki skończony zbiór \(\displaystyle{ B}\) punktów przestrzeni, że każde dwie odległości między punktami tego zbioru są różne. Każdy punkt zbioru \(\displaystyle{ B}\) łączymy odcinkiem z najbliższym mu punktem zbioru \(\displaystyle{ B}\). Jeden (dowolnie wybrany) z otrzymanych odcinków malujemy na czerwono, wszystkie pozostałe na zielono. Dowieść, że istnieją takie dwa punkty zbioru \(\displaystyle{ B}\), których nie można połączyć łamaną złożoną z odcinków zielonych.
Niech zbiór \(\displaystyle{ B}\) zawiera \(\displaystyle{ n \in \mathbb{N^{+}}}\) punktów oraz \(\displaystyle{ n > 1}\). Jeśli każde dwa z tych punktów są oddalone od siebie o różną odległość, to istnieje taka para pewnych punktów \(\displaystyle{ X, Y}\), między którymi odległość jest najmniejsza. Zauważmy, że jeśli wśród dowolnych odległości w tym zbiorze \(\displaystyle{ |XY|}\) jest najmniejsza, to zarówno z punktu \(\displaystyle{ X}\) prowadzimy odcinek do punktu \(\displaystyle{ Y}\), jak i z punktu \(\displaystyle{ Y}\) do punktu \(\displaystyle{ X}\). Powstał więc jedynie jeden odcinek.
Rozważmy teraz pozostałe z punktów i weźmy pewien z nich, niech będzie to \(\displaystyle{ P}\). Jeśli został już połączony z innym punktem, nazwijmy go \(\displaystyle{ Q}\), a z punktu \(\displaystyle{ P}\) jest najbliżej do punktu \(\displaystyle{ Q}\), to nie powstał nowy odcinek. W innym wypadku dorysowujemy jeden odcinek. Wynika z tego, że nie może powstać z pozostałych punktów więcej niż \(\displaystyle{ n-2}\) odcinków, a więc łącznie liczba odcinków nie może być większa niż \(\displaystyle{ n-1}\).
Jeśli pewne punkty nie są ze sobą połączone łamaną, to koniec. Załóżmy więc, że wszystkie odcinki są połączone pewną łamaną. Udowodnimy, że nie mogła w ten sposób powstać łamana zamknięta. Załóżmy, nie wprost, że dla pewnego ułożenia tych punktów jednak powstała. Niech powstała łamana zamknięta ma \(\displaystyle{ k \in \mathbb{N_{\ge{3}}}}\) wierzchołków. Wówczas usuwając kolejno punkty nienależące do niej, zostaje \(\displaystyle{ k}\) punktów połączonych \(\displaystyle{ k}\) odcinkami. Jednak udowodniliśmy, że dla danej liczby punktów, liczba powstałych odcinków musi być od niej mniejsza. Sprzeczność. A więc nie może powstać łamana zamknięta.
Teraz zauważmy, że jeśli pewien odcinek \(\displaystyle{ CD}\) tej łamanej jest czerwony, a pozostałe pokolorowane na zielono, to nie możemy połączyć obu końców tego czerwonego odcinka. Gdyby bowiem byłoby to możliwe, to musiałaby istnieć pewna łamana zamknięta łącząca te punkty. Sprzeczność. A więc istnieją pewne dwa punkty należące do tego zbioru, których nie można połączyć zielonymi odcinkami, co należało wykazać.

Z góry dziękuję za pomoc. :)

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7793
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3060 razy

Re: Łamana w przestrzeni

Post autor: kerajs » 5 sie 2020, o 06:17

To poprawne rozwiązanie. Sam bym tak dowodził (pominąłbym fragment o łamanej zamkniętej zawierającej wszystkie punkty).

Thingoln
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 27 lip 2019, o 22:19
Płeć: Mężczyzna
Lokalizacja: województwo śląskie
Podziękował: 48 razy
Pomógł: 13 razy

Re: Łamana w przestrzeni

Post autor: Thingoln » 5 sie 2020, o 12:49

Dziękuję za pomoc. :)

ODPOWIEDZ