Skocz do zawartości


Zdjęcie

Łączenie kropek


Ten temat został zarchiwizowany. Nie można odpowiadać w tym temacie.
4 odpowiedzi w tym temacie

#1 nitro

nitro

    Kombinator

  • VIP
  • 200 postów
40
Mały Pomocnik II

Napisano 14.04.2010 - 20:33

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

Posted Image

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

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 1881 postów
870
Wykładowca III

Napisano 14.04.2010 - 21:18

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 3 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 3 punkty, to po narysowaniu drugiego odcinka mielibyśmy połączone 2+2=4 punkty (nie 2+3 bo koniec pierwszego odcinka jest początkiem drugiego i nie liczymy go 2 razy), po narysowaniu kolejnego odcinka byłoby połączonych 4+2=6 punktów no i na końcu mielibyśmy połączonych maksymalnie 6+2=8 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 9-3-1=5 lub 9-3-2=4 punkty.
Jeśli pozostało nam 5 punktów to kolejnymi dwoma odcinkami połączymy maksymalnie 2+2=4 nowe punkty - sprzeczność.
Wobec tego przyjmijmy, że zostały nam 4 punkty. Można pokazać, że żadne 3 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 4 punktów pewne 3 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ć 5 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 :)

#3 nitro

nitro

    Kombinator

  • VIP
  • 200 postów
40
Mały Pomocnik II

Napisano 14.04.2010 - 21:28

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

#4 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 1881 postów
870
Wykładowca III

Napisano 14.04.2010 - 21:51

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ł.

#5 nitro

nitro

    Kombinator

  • VIP
  • 200 postów
40
Mały Pomocnik II

Napisano 14.04.2010 - 22:06

Ekstra ;) Chyba pójdę na matematykę :)






Partnerem technologicznym jest dhosting.pl      Współpracują z nami     PortalMatematyczny.pl