Zad. 1. Trójkąt równoboczny podzielono na n2 trójkącików równobocznych. O ile więcej jest rombów składających się z dwóch trójkącików od rombów składających się z ośmiu trójkącików?
Zad. 2. Ile dzielników niebędących kwadratami ma liczba 20240000?
Zad. 3. Na ile sposobów można pokryć prostokąt o wymiarach 2×7 siedmioma kostkami domina o wymiarach 2×1?
W tym miesiącu 11 pkt. zdobył Wiktor Gatner, SP 3 Wrocław.
Zad. 1. Zauważmy, że bok trójkącika to 1/n boku dużego trójkąta (dlaczego?), co jednoznacznie determinuje podział trójkąta na trójkąciki. Będziemy teraz rozważać boki trójkącików (nazywane odcinkami). Zbiór odcinków leżących na jednej prostej nazywać będziemy rzędem. Najdłuższy rząd w trójkącie zawiera n−1 odcinków, a najkrótszy rząd zawiera jeden odcinek. Zatem istnieje n(n−1)/2 odcinków równoległych do jednego boku dużego trójkąta. Zauważmy, że po każdej stronie odcinka nieleżącego na brzegu dużego trójkąta znajduje się jeden trójkącik, co daje łącznie 3n(n−1)/2 odcinków, a więc także rombów złożonych z dwóch trójkącików.
Aby romb składał się z ośmiu trójkątów, jego środkowy rząd musi zawierać dwa odcinki, a rzędy powyżej i poniżej muszą zawierać po jednym odcinku. Możemy policzyć liczbę linii złożonych z dwóch odcinków, które nie znajdują się w ostatnim rzędzie dużego trójkąta. Drugi pod względem długości rząd w trójkącie zawiera n−2 odcinki, natomiast drugi pod względem krótkości zawiera 2 odcinki. Zatem istnieje (n−2)(n−3)/2 poprawnych linii z dwóch odcinków równoległych do jednej strony, co daje łącznie 3(n−2)(n−3)/2 rombów zawierających osiem trójkątów
równobocznych.
Po odjęciu obu liczb otrzymujemy 6n−9.
Zad. 2. Rozkład liczby 20240000 na czynniki pierwsze to: 2⁷ · 5⁴ · 11¹ · 23¹. Liczba wszystkich dzielników wynosi (7+1) · (4+1) · (1+1) · (1+1) = 160. Aby dzielnik był kwadratem, wykładniki w rozkładzie na czynniki pierwsze muszą być parzyste. Możliwości wyboru wykładników dla każdego czynnika:
- dla 2⁷: 0, 2, 4, 6 (4 możliwości),
- dla 5⁴: 0, 2, 4 (3 możliwości),
- dla 11¹: 0 (1 możliwość),
- dla 23¹: 0 (1 możliwość).
Liczba dzielników będących kwadratami to 4 · 3 · 1 · 1 = 12, zatem liczba dzielników niebędących kwadratami wynosi 160−12 = 148.
Zad. 3. Oznaczmy przez a(n) liczbę sposobów pokrycia prostokąta o wymiarach 2×n. Dla n=0 mamy a(0) = 1 (pusty prostokąt). Dla n=1 mamy a(1) = 1 (można ułożyć tylko jedno pionowe domino). Ogólnie dla n ≥ 2 spełniona jest rekurencja: a(n) = a(n−1) + a(n−2):
- Jeżeli pierwszy słupek (pierwsze dwie kratki w kolumnie) pokryjemy pionowym domino, to pozostaje prostokąt 2×(n−1), który można pokryć na a(n−1) sposobów.
- Jeżeli pierwsze dwa słupki (pierwsze cztery kratki w dwóch kolumnach) pokryjemy dwoma poziomymi dominami, to pozostaje prostokąt 2×(n−2), który można pokryć na a(n−2) sposobów.
Widać, że mamy do czynienia z ciągiem Fibonacciego, czyli odpowiedzią dla n=7 jest 21.
To zabawny samouczek, który zaczynając się niewinnie intrygującą historyjką, krok po kroku, poczynając od najłatwiejszych łamigłówek, prowadzi nas w szpony, nie bójmy się użyć tego słowa, uzależnienia.
