szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 19:52 
Użytkownik

Posty: 31
Lokalizacja: oOo
Na płaszczyźnie danych jest 2016 punktów, wśród których żadne 3 nie są współliniowe. Wykazać, że istnieją 672 parami rozłączne trójkąty o wierzchołkach w danych punktach.
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 20:07 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Podziel 2016przez trzy
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 20:12 
Użytkownik

Posty: 31
Lokalizacja: oOo
arek1357 napisał(a):
Podziel 2016przez trzy

To było tak oczywiste, że nie chciało mi się wierzyć, że jest prawidłowe.
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 20:18 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Mnie bardziej ciekawi kto ci to zadanie zadał.
Góra
Mężczyzna Offline
PostNapisane: 11 lis 2016, o 21:48 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
arek1357 napisał(a):
Podziel 2016przez trzy

Moim zdaniem to jeszcze nie rozwiązuje zadania bo nie wiadomo jak wyodrębniać te trójkąty.
Tutaj jest jakieś podejście:
http://archom.ptm.org.pl/?q=node/832
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2016, o 11:45 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
A poco wyodrębniać trójkąty wskazuje się tylko że takie są.
Zresztą zrób to zadanie dla n=6 punktów i z tego masz dwa trójkąty.
Poco doszukiwać się drugiego dna.
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2016, o 13:43 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
No wyodrębnienie to jest właśnie to wskazanie.
Dla małej liczby punktów może i widać jak to zrobić ręcznie, ale dla większej to już nie.
Dowolny zbiór trójkątów w tych punktach może powodować, że pewne trójkąty mają niepuste przecięcie.
Dlatego to co napisaliście oboje do tej pory nie daje rozwiązania - jest dla mnie zaskakujące, że tego nie czujecie.
Poza tym treść jest identyczna jak z zadaniem z OMa, więc chyba nie sądzisz, że przeszłoby rozwiązanie dla szczególnego przypadku n = 6, a dalej "to już widać".

Generalnie chodzi o to aby te punkty w jakiś sposób uporządkować.
Można np. posortować te punkty względem współrzędnej x. Wtedy są co najwyżej dwa punkty o takiej samej współrzędnej. Potem można iść po coraz większych x-ach biorąc kolejno punkty z dwóch lub trzech kolejnych współrzędnych x (tak aby tworzyły trójki punktów).
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2016, o 15:27 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Ależ to widać gołym okiem.


masz n=3k i zawsze znajdziesz takie otoczenie , które zawrze 3k-3 punkty
dodasz do tego indukcję i masz ....
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2016, o 15:39 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Ok, mam takie otoczenie, które zawiera 3k - 3 punkty. Pozostają mi trzy. Ale istotne jest to, że te trzy muszą tworzyć trójkąt rozłączny z pozostałymi z tego otoczenia. Tak więc trzeba wybrać odpowiedni sposób wyboru otoczenia i trzeba to napisać mimo że to jedno zdanie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Punkty przecięcia prostych - zadanie 5  michals95  5
 Płaszczyzna i punkty  mol_ksiazkowy  4
 10zad:karty,proste i trojkaty,przekatne,podzbiory,podzialy..  mateo19851  6
 punkty na płaszczyźnie - zadanie 13  szykom  2
 Punkty na płaszczyźnie - zadanie 10  Quaerens  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl