ilosc punktow

[alfred0]

Mamy n punktow na plaszczyznie. Oznaczmy kolorem czerwonym kazdy punkt, ktory jest srodkiem dowolnego odcinka utwrzonego z danych punktow. Jaka jest mozliwie najmniejsza ilosc czerwonych punktow?

[Ponewor]

Zadanie niestandardowe, więc musisz zacząć po omacku. Zacznij od badania małych \(\displaystyle{ n}\), zastanów się jakiej postaci może być poszukiwane wyrażenie (czy np. może być funkcją wykładniczą) i sformułuj jakąś hipotezę.

[alfred0]

Sprswdzilem dla n=3 mamy 3, dla n=4 mamy 5, dla n=5 mamy 7, ale nie potrafie zadnej hipotezy wysnuc. I nie wiedzialbym tez jak ja udowodnic.

[Hydra147]

Mi się wydaje, że będzie to funkcja \(\displaystyle{ f(n)=2n-3}\), powstaje z ułożenia n punktów na jednej prostej tak, aby odległość pomiędzy dwoma sąsiednimi punktami była taka sama. Teraz trzeba by tylko wykazać, że nie można tego zrobić lepiej.

[alfred0]

No tak, tez myslalem ze tyle bedzie ale jak to wykazac bo to jest najwazniejsze

[Hydra147]

I cz. :
Załóżmy nie wprost, że istnieje taki układ n punktów, że po dodaniu do nich 1 punktu ilość czerwonych punktów nie ulegnie zmianie. Oznaczmy dodany punkt przez A. Wybierzmy dowolny punkt z początkowego układu i nazwijmy go \(\displaystyle{ B_{1}}\). Środek odcinka \(\displaystyle{ A B_{1}}\) musiał być już środkiem jakiegoś innego odcinka. Z dwóch punktów, które są jego końcami wybierzmy ten bliżej \(\displaystyle{ A}\) i nazwijmy go \(\displaystyle{ B_{2}}\). Naturalnie punkt \(\displaystyle{ B _{2}}\) jest bliżej \(\displaystyle{ A}\) niż \(\displaystyle{ B_{1}}\). Środek odcinka \(\displaystyle{ A B_{2}}\) musiał być już środkiem innego odcinka itd. rozumowanie musiałoby przebiegać w nieskończoność, a niestety mamy tylko skończoną ilość punktów.

Teraz trzeba pokazać to samo tylko w sytuacji, w której powstaje dokładnie 1 punkt czerwony. Z tego wynika oczywiście to, że z każdym nowym punktem ilość punktów czerwonych zwiększa się o co najmniej 2. Mamy więc w połączeniu z faktem \(\displaystyle{ f(2)=1}\) nierówność \(\displaystyle{ f(n) \ge 2n-3}\). Oczywiście w połączeniu z tym co napisałem post przedtem otrzymujemy \(\displaystyle{ f(n)=2n-3}\).

[Ponewor]

Naturalnie punkt \(\displaystyle{ B _{2}}\) jest bliżej \(\displaystyle{ A}\) niż \(\displaystyle{ B_{1}}\).

To nieprawda.

Ja w swoim dowodzie (bardzo prawdopodobne, że można zrobić prostszy), wykorzystuję istnienie otoczki wypukłej.

[Hydra147]

Faktycznie, pomyłka. To może coś takiego:
Załóżmy, że \(\displaystyle{ A}\) jest wewnątrz otoczki. Wówczas istnieją takie trzy punkty \(\displaystyle{ B_{1} , C_{1}, D_{1}}\), że \(\displaystyle{ A}\) zawiera się w trójkącie \(\displaystyle{ B_{1} C_{1} D_{1}}\). W tymże trójkącie znajdują się także punkty \(\displaystyle{ B_{2} , C_{2} , D_{2}}\), które są środkami (odpowiednio) odcinków \(\displaystyle{ AB_{1} , AC_{1}, AD_{1}}\). Skoro ilość czerwonych punktów nie zwiększyła się, to punkty te musiały należeć już do zbioru. Ponadto punkt A zawiera się w trójkącie \(\displaystyle{ B_{2} C_{2} D_{2}}\). Oczywiście, podobnie jak w poprzednim "dowodzie" prowadzi nas to do sprzeczności. Punkt \(\displaystyle{ A}\) musi być zatem poza otoczką. Wybierzmy z naszego zbioru punkt najbliższy \(\displaystyle{ A}\). Środek odcinka łączącego go z \(\displaystyle{ A}\) leży poza otoczką czyli sprzeczność.

[alfred0]

Naturalnie punkt \(\displaystyle{ B _{2}}\) jest bliżej \(\displaystyle{ A}\) niż \(\displaystyle{ B_{1}}\).

To nieprawda.

Ja w swoim dowodzie (bardzo prawdopodobne, że można zrobić prostszy), wykorzystuję istnienie otoczki wypukłej.

A moze ktoś napisac dowód bez tej otoczki

[Hydra147]

Otoczka wypukła to dość proste w zrozumieniu pojęcie ale można się obejść bez jego pomocy. Wystarczy w moim rozumowaniu zamiast przypadków: A poza otoczką; A w otoczce rozpatrzyć: A należy/nie należy do pewnego trójkąta utworzonego z trzech wybranych punktów. W drugim przypadku trzeba się będzie nieco bardziej rozpisać