4 odpowiedzi w tym temacie

[nitro]

Spójrzcie na tą zagadkę: POŁĄCZ 9 KROPEK CZTEREMA LINIAMI PROSTYMI! NIE ODRYWAJ OŁÓWKA OD KARTKI!



Wiem jakie jest rozwiązanie, natomiast czy mozna jakoś matematycznie udowodnić, że nie da się tego zrobić tak, aby linie nie wyszły poza kwadrat nakreślony przez zewnętrzne kropki (mam nadzieje, że zrozumiale w miarę napisałam)

[Afroman]

[Ereinion]

O, ciekawy problem

Jeśli mamy się ograniczyć do kwadratu to zamiast o prostych będę mówił o odcinkach. Jeśli dopuścimy "wracanie po śladzie" tzn. rysuję odcinek a potem mogę "po nim" wrócić do dowolnego punktu na nim (niby wszystko jest w porządku bo nie odrywam ołówka od kartki) to zagadkę można rozwiązać nie wychodząc poza kwadrat i jest to stosunkowo proste, dlatego przyjmijmy dalej, że rysujemy "jednym ciągiem" tj. koniec jednego odcinka jest początkiem następnego itd.

Najpierw taki sobie pomocniczy

Lemat.
Nie da się przy zachowaniu warunków zadania połączyć dwoma odcinkami czterech punktów, z których żadne trzy nie są współliniowe.
Szkic dowodu:

==============================================================================
Jednym odcinkiem możemy połączyć tylko 2 punkty, wobec tego dwoma odcinkami połączymy tylko 3 punkty, bo koniec jednego odcinka jest początkiem następnego, więc jeden punkt musimy "policzyć" dwukrotnie.
==============================================================================

Teraz przejdźmy do dowodu który będzie ad absurdum (czyli nie wprost):

Załóżmy, że szukane połączenie istnieje.
Wobec tego mamy przynajmniej jeden odcinek, który przechodzi przez dokładnie kropki. (dlaczego?)

=============================================================================
Wynika to z tzw. zasady szufladkowej Dirichleta, ale można też intuicyjnie: mamy 4 odcinki, które w sumie przechodzą przez 9 punkty (bo założyliśmy, że istnieje szukane "dobre" łączenie). Żaden odcinek nie przechodzi przez 4 albo więcej punktów (bo te punkty musiałyby być współliniowe). Wobec tego każdy z odcinków przechodzi przez 2 albo 3 punkty. Gdyby wszystkie odcinki przechodziły tylko przez 2 punkty to łącznie pokrytych mielibyśmy maksymalnie 8 punktów czyli za mało. Wobec tego musi istnieć przynajmniej jeden odcinek przechodzący przez 3 punkty.
=============================================================================

Można przyjąć, że ten odcinek rysujemy jako pierwszy (co bynajmniej nie jest oczywiste, bo w tym zadaniu kolejność rysowania poszczególnych odcinków ma znaczenie).

=============================================================================
Załóżmy, że zaczynamy od odcinka łączącego dwa punkty. Nawet gdyby każdy następny odcinek przechodził przez punkty, to po narysowaniu drugiego odcinka mielibyśmy połączone punkty (nie bo koniec pierwszego odcinka jest początkiem drugiego i nie liczymy go razy), po narysowaniu kolejnego odcinka byłoby połączonych punktów no i na końcu mielibyśmy połączonych maksymalnie punktów, a to za mało.
==============================================================================

Kolejny odcinek połączy dwa lub trzy punkty, z których jeden jest końcem pierwszego odcinka, więc pozostanie nam do połączenia lub punkty.
Jeśli pozostało nam punktów to kolejnymi dwoma odcinkami połączymy maksymalnie nowe punkty - sprzeczność.
Wobec tego przyjmijmy, że zostały nam punkty. Można pokazać, że żadne z tych czterech punktów nie będą współliniowe, wobec czego mamy sprzeczność z lematem, a to kończy dowód.

=============================================================================
Załóżmy, że z pozostałych punktów pewne są współliniowe. Mamy dwie opcje:
1. Są to punkty na przekątnej naszego "kwadratu". Wtedy jednak niemożliwe byłoby poprowadzenie pierwszego odcinka z naszej konstrukcji (łączącego 3 punkty), więc ta opcja odpada.
2. Są to punkty na linii równoległej do jednego z boków "kwadratu". Wtedy dwa pierwsze odcinki musiałyby połączyć punktów spośród sześciu, które leżą na pewnych dwóch równoległych prostych. Jest to również niemożliwe.
==============================================================================

Szczegółowe dowody poszczególnych faktów po zasygnalizowaniu mi postaram się w miarę możliwości dopisać



[edit]
dodano szczegółowe wyjaśnienia

[nitro]

Bardzo Ci dziękuje Ereinion Czy byłoby problemem dopisanie szczegółów? Zaintrygowało mnie to, co napisałeś

[Ereinion]

Nie ma sprawy, już dopisałem. W razie dalszych wątpliwości zacytuj, który fragment jest niezrozumiały i chętnie będę dalej wyjaśniał.

[nitro]

Ekstra Chyba pójdę na matematykę