Punkty i linie • Nikolay Avilov • Popularne problemy naukowe w "Elementach" • Matematyka

Punkty i prosto

Zadanie

Ponieważ uczymy się w szkole na lekcjach geometrii, poprzez dwa różne punkty, można narysować dokładnie jedną linię prostą. Można powiedzieć, że para punktów określa unikalną linię. Ale jeśli jest więcej punktów, liczba linii, które definiują, może być inna. Na przykład, w zależności od jego położenia, trzy punkty mogą określać trzy proste linie (jeśli te punkty są wierzchołkami nieodnawianego trójkąta) lub jedną prostą (jeśli te punkty są współliniowe, to znaczy leżą na jednej linii prostej). Jeśli jest ich jeszcze więcej, to istnieje więcej możliwości ich wzajemnego porozumienia, stąd odpowiedzi na pytanie "ile bezpośrednich n Będzie wiele punktów. "Jednak zadanie to ma zająć się określonymi konfiguracjami punktów, a później omówimy ogólne pytania.

Ryc. 1

a) Na kraciastym papierze wybieramy kwadrat z bokiem pięciu komórek i zaznaczamy wszystkie punkty w jego środku i na jego granicy – otrzymujemy 36 punktów w postaci kwadratowej siatki 6 × 6 (ryc. 1). Ile bezpośrednio określić te punkty? A jeśli 64 punkty (w postaci siatki 8 × 8)?

b) Długość krawędzi regularnego czworościanu wynosi 4. Na każdym z nich zaznaczono trzy punkty dzielące krawędź na segmenty jednostkowe. Wierzchołki czworościanu są również oznaczone. Ile linie definiują wszystkie zaznaczone punkty?


Podpowiedź

Spróbuj policzyć linie zdefiniowane przez mniejszą liczbę punktów – 4, 9 lub 16 punktów. Jeśli odpowiedzi mają wartość 6, 20 i 62 bezpośrednio, jesteś na dobrej drodze.

Główną trudnością jest to, że niektóre proste przechodzą tylko przez dwa zaznaczone punkty, a niektóre przez trzy lub więcej zaznaczonych punktów. Podczas rozwiązywania problemu ważne jest zorganizowanie systemu liczenia linii prostych.


Rozwiązanie

Dzielimy wszystkie proste na rozłączne klasy równoległych linii prostych. Proste linie z jednym spadkiem wchodzą do każdej klasy. k.

Ryc. 2 Niektóre klasy linii równoległych

Na rys. 2 pokazuje niektóre klasy linii. Ich współczynniki kątowe, z wyjątkiem 0 i 1, są możliwymi nieredukowalnymi poprawnymi ułamkami, których mianownik jest nie większy niż 5. Aby uzyskać wszystkie klasy w ogólności, należy wziąć pod uwagę symetrię obrazu. Więc podczas obliczania, – i liczby po prostu do dodania, – liczba linii w klasach z k = 0 i k = 1 należy podwoić, aw innych klasach – czterokrotnie. Wynikiem jest 2 × (6 + 9) + 4 × (5 + 4 + 3 + 2 + 10 + 6 + 15 + 12 + 12) = 306 linii.

Podobne obliczenie dla 64 punktów da 938 linii.

Zajmijmy się teraz czworościanem. Ten problem można natychmiast rozpatrzyć w ogólnej formie. Niech rama czworościanu z krawędzią długości m podzielone przez kropki na pojedyncze segmenty.Ile różnych prostych określa te punkty i wierzchołki samego czworościanu?

Czworościan ma 4 wierzchołki i 6 krawędzi. Wraz z wierzchołkami i punktami podziału na szkielecie czworościanu oznaczane są 4 + 6 (m − 1) = 6m – 2 punkty. Gdyby wszystkie te punkty znajdowały się w ogólnej pozycji (to znaczy, że żadna z nich nie leżałaby w tej samej linii), wówczas określiliby (6m − 2)(6m − 3)/2 = (3m − 1)(6m – 3) linie proste (ponieważ jeśli punkty znajdują się w pozycji ogólnej, to dowolne dwie z nich określają własną linię prostą). Teraz musimy wziąć pod uwagę, że na każdej krawędzi czworościanu jest zaznaczone m + 1 punkt nie w ogólnej pozycji. Gdyby te punkty znajdowały się w ogólnej pozycji, to by je zdefiniowały m(m + 1) / 2 linie proste. Ale wszystkie te linie pokrywają się – jest to linia zawierająca daną krawędź czworościanu. W związku z tym całkowita liczba linii zdefiniowanych we wskazanych punktach wynosi (3m − 1)(6m − 3) − 6·m(m + 1) / 2 + 6. Po uproszczeniu otrzymujemy 15m2 − 18m + 9 linii prostych. W naszym zadaniu m = 4, więc odpowiedź to 177 linii.


Posłowie

Jeśli zastosujemy rozumowanie, którego używaliśmy do odpowiedzi na pierwsze pytanie problemu, możemy znaleźć odpowiedzi na inne kwadraty od n2 punkty. Oto one n od 2 do 10: 6, 20, 62, 140, 306, 536, 938, 1492, 2306. Ta sekwencja jest zawarta w internetowej encyklopedii sekwencji całkowitych pod numerem A018808.

Czy istnieje względnie prosta formuła wyrażenia liczby? N takie linie są arbitralne n? Spróbujmy jej szukać.

Używamy dwóch znanych faktów z geometrii częstości występowania.

1) Jeśli w samolocie zaznacz k punkty w ogólnej pozycji (pamiętaj, że oznacza to, że trzy z tych punktów nie leżą na jednej linii prostej), wtedy liczba różnych linii prostych zdefiniowanych przez te punkty jest równa k(k − 1)/2.

Użyliśmy tego stwierdzenia w rozwiązaniu i łatwo to udowodnić poprzez indukcję.

2) Jeśli w samolocie zaznacz k punkty, które nie są w tej samej linii, a następnie definiują co najmniej k różne proste linie.

Druga wypowiedź wydaje się dość oczywista, ale została udowodniona dopiero w połowie XX wieku i jest obecnie znana jako twierdzenie de Bruin – Erdёos.

Na podstawie tych dwóch właściwości możesz oszacować liczbę N(n). Korzystając z drugiego faktu, otrzymujemy dolną granicę: N(n) ≥ n2. Korzystając z pierwszego faktu, otrzymujemy wyższe oszacowanie: N(n) ≤ n2(n2 – 1) / 2 to liczba określonych linii n2 punkty ogólnej pozycji.

Oznacza to, że jeśli istnieje formuła N (n) w postaci wielomianu z n, – i jest to prawdopodobnie najprostsza forma formuły, – ten wielomian może mieć tylko 2, 3 lub 4 stopnie. Używając powyższych kilku pierwszych wartości N, stosując metodę nieokreślonych współczynników, można wykazać, że nie ma formuły w postaci takiego wielomianu.

Spróbujmy innego podejścia i uogólnij metodę liczenia linii, dzieląc równoległe klasy na klasy. Każda klasa zawiera wszystkie równoległe linie ze współczynnikiem kątowym k = a/b (dalej ułamki są regularne nieredukowalne).

Ponieważ dowolna linia na płaszczyźnie jest jednoznacznie określona przez współczynnik kątowy i jeden punkt, dla każdej klasy z k = a/b w kropkowanym kwadracie wybierz punkty, które definiują wszystkie linie tej klasy. W takim przypadku możliwe są dwa przypadki:
1) jeśli b < n/ 2, a następnie punkty definiujące wszystkie linie proste ze współczynnikiem kątowym a/b, znajdują się wewnątrz niebieskich i zielonych prostokątów pokazanych po lewej stronie na rys. 3 i ich b·(na) + a·(n − 2b) = n·(a + b) − 3ab;
2) jeśli bn/ 2, a następnie punkty definiujące wszystkie linie proste ze współczynnikiem kątowym a/bznajdują się wewnątrz niebieskiego prostokąta pokazanego po prawej stronie na rys. 3 i ich (na) (nb).

Ryc. 3 Punkty za pomocą których możesz zdefiniować wszystkie linie z danej klasy w kwadracie o wartości 100 punktów. Lewy przykład dla k = 2/3, po prawej – dla k = 2/7

Liczba N(a/ba) linie proste w klasie c k = a/b równa liczbie wybranych punktów i jest obliczana przez formuły znalezione powyżej.

Dlatego liczba N(nwszystko bezpośrednio, dane n2 punkty można obliczyć według wzoru:

\ [N (n) = 2 (N_0 + N_1) +4 \ sum \ limits_ {b = 2} ^ {n-1} \ sum \ limits_ {a = 1} ^ {b-1} N \ left (\ frac ab \ right) \]

gdzie N0 = n – liczba linii poziomych N1 = 2n – 3liczba linii równoległych do przekątnej kwadratu. Ta formuła jest łatwa do zaprogramowania i sprawdzenia, czy wyniki są zgodne.

Można również uzyskać relacje powtarzalności dla liczby linii prostych wyznaczonych przez kwadraty kropki, ale również okazują się one dość kłopotliwe. Więcej szczegółów można znaleźć w artykule S. Mustonen, 2009. Na liniach i ich punktach przecięcia.

Argumenty podane dla prawidłowego czworościanu w roztworze działają dla dowolnego wypukłego wielościanu, w którym wszystkie krawędzie są sobie równe. W rzeczywistości, nigdzie nie używano żadnych specyficznych właściwości czworościennych, brano pod uwagę tylko liczbę jego wierzchołków i krawędzi. Tak więc rozumowanie powtarza się niemal dosłownie.

Zostań wielościanem B wierzchołki i P żebra. Wraz z wierzchołkami i punktami podziału na ramie wielościanu oznaczony In + R(m – 1) punktów. Gdyby wszystkie te punkty znajdowały się w ogólnej pozycji, wówczas zdefiniowaliby linie \ (\ frac12 (B + P (m-1)) (B + P (m-1) -1) \). Ale na każdej krawędzi wielościanu jest zaznaczone (m + 1) punkt, który, gdyby znajdowali się na pozycji ogólnej, określiliby m(m + 1) / 2 linie proste, ale zamiast tego definiują tylko jedną linię prostą zawierającą krawędź. Oznacza to, że wszystkie z nich muszą zostać odjęte od liczby całkowitej, a liczba linii zawierających krawędzie musi zostać dodana. Zdobądź

\ [\ dfrac12 (B + P (m-1)) (B + P (m-1) -1) -P \ cdot \ dfrac12m (m + 1) + P ..]


Like this post? Please share to your friends:

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: