/Szkoła średnia/Kombinatoryka/Geometria

Zadanie nr 8677667

Dodaj do ulubionych
Dodaj do rozwiązanych

Okrąg podzielono dwudziestoma punktami na dwadzieścia łuków tej samej długości. Ile można zbudować łamanych zamkniętych z wierzchołkami w tych punktach i z odcinkami równej długości? (Odcinki mogą się przecinać, ale nie mogą się pokrywać.)

Rozwiązanie

Jeżeli ktoś wytrwały, to może sobie wszystkie możliwości narysować, ale my spróbujemy być trochę sprytniejsi (dzięki temu będziemy poradzimy sobie jak odcinków będzie np. 60).


PIC


Jak zaczniemy sobie te łamane rysować, to widać, że mogą one być różnej długości. Aby nad tym zapanować, ponumerujmy wierzchołki liczbami od 0 do 19. Zastanówmy się jak wyglądają łamane przechodzące przez wierzchołek z numerem 0. Na pewno jedna z krawędzi o wierzchołku w 0 musi mieć drugi koniec w przedziale ⟨1,9⟩ (nie liczymy odcinka 0-10 jako łamanej). Powiedzmy, że ten drugi wierzchołek to x . W takim razie kolejne wierzchołki będą równe 2x,3x,4x itd., przy czym w momencie, gdy otrzymana liczba przekracza 20, odejmujemy od niej 20 (innymi słowy bierzemy resztę z dzielenia przez 20). Skoro kolejne wierzchołki dane są wzorem kx , gdzie k = 0,1,2,... , to łatwo zgadnąć kiedy łamana wróci do punktu wyjścia – tak będzie gdy liczba kx będzie podzielna przez 20. Dla jakiego k tak będzie? – to zależy od x .

Jeżeli x jest liczbą względnie pierwszą z 20, czyli jedną liczb 1,3,7,9 , to kx będzie podzielne przez 20 dopiero dla k = 20 , czyli łamana obejdzie wszystkie wierzchołki. Ponadto dla różnych liczb otrzymamy różne łamane (inna będzie długość jej boku). Są zatem 4 takie łamane (2 z nich są na rysunku).

Jeżeli x dzieli się przez 2, ale nie dzieli się przez 4, czyli x ∈ { 2,6} to łamana zamknie się już dla k = 1 0 . Innymi słowy, łamana przechodzi przez co drugi wierzchołek. Obie łamane są różne (mają inną długość boku), więc jak dodamy jeszcze dwie analogiczne łamane przechodzące przez wierzchołek 1, to mamy w sumie 4 łamane długości 10.

Jeżeli x dzieli się przez 4, czyli x ∈ {4,8 } , to mamy łamaną długości 5 (czyli dla k = 5 liczba kx dzieli się przez 20). Teraz otrzymane dwie łamane możemy obrócić na 3 sposoby (żeby przechodziły przez 1,2,3 odpowiednio), więc w sumie mamy 8 łamanych długości 5.

Pozostało nam już tylko x = 5 . Wtedy mamy kwadrat i możemy go obrócić na 4 sposoby, co daje nam 5 łamanych.

W sumie jest więc 4+4+8+5=21 takich łamanych zamkniętych.  
Odpowiedź: 21

Wersja PDF
spinner