Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Łączenie kropek


  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
4 odpowiedzi w tym temacie

#1 nitro

nitro

    Kombinator

  • VIP
  • 200 postów
40
Mały Pomocnik II
  • Płeć:Kobieta

Napisano 14.04.2010 - 20:33

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

Dołączona grafika

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) :)
  • 0

Afroman

    Kombinator

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

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2023 postów
946
Wykładowca III
  • Płeć:Mężczyzna

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 :)
  • 0

#3 nitro

nitro

    Kombinator

  • VIP
  • 200 postów
40
Mały Pomocnik II
  • Płeć:Kobieta

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ś ;)
  • 0

#4 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2023 postów
946
Wykładowca III
  • Płeć:Mężczyzna

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

#5 nitro

nitro

    Kombinator

  • VIP
  • 200 postów
40
Mały Pomocnik II
  • Płeć:Kobieta

Napisano 14.04.2010 - 22:06

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




Partner i sponsor hostingu



sys-com.pl          m-networks.pl