Kilka zadań na zaspokojenie fascynacji uczniów liczbami sześć i siedem

Prosty trik na zyskanie uwagi uczniów. Zadania dotyczące cyfr 6, 7 i liczby 67.

Nie bardzo rozumiem o co chodzi z fenomenem liczby 67. Ale młode pokolenie (od kilkuletnich dzieci do nastolatków w liceum) jakoś bardzo fascynują się tą liczbą i mimo, że ona rzekomo nic nie oznacza, to jakoś zawsze raźniej się robi, gdy wynikiem lub argumentem jakiegoś działania jest liczba 67. Pomyślałem sobie, że warto to wykorzystać i przygotowałem plan zajęć z zadaniami kombinatorycznymi z tą liczbą, który z powodzeniem zrealizowałem (z pewnymi modyfikacjami) w różnych grupach wiekowych. W tym wpisie podzielę się z Wami tym planem i konkretnymi zadaniami.

Pierwsze zadanie

Na wstępie warto zacząć od czegoś naprawdę łatwego. Mamy worek z czterema różnokolorowymi cyframi sześć oraz worek z pięcioma różnokolorowymi cyframi siedem. Na ile sposobów można stworzyć liczbę 67?

Nawet dzieci z klasy trzeciej potrafią odpowiedzieć, że można stworzyć $4 \cdot 5 = 20$ różnych six-seven’ów. Dobrze jednak zacząć od czegoś prostego, żeby mieć na czym budować trudniejsze zadania.

Kontratak pierwszy

A gdybyśmy chcieli stworzyć dokładnie six-seven na dokładnie $21$ różnych sposobów, to ile najmniej cyfr byśmy potrzebowali?

To też nie wydaje się bardzo trudne, gdy przypomnimy sobie, że $21 = 3 \cdot 7$. Wystarczy więc wziąć trzy szóstki i siedem siódemek (albo odwrotnie: trzy siódemki i siedem szóstek) i six-seven można zrobić na $3 \cdot 7 = 21$ sposobów. Razem użyliśmy tylko $10$ cyfr.

A gdyby chcieć stworzyć six-seven na dokładnie $67$ różnych sposobów?

Okazuje się, że $67$ to liczba pierwsza, a więc jedyne co możemy zrobić to dać $67$ cyfr jednego typu oraz jedną cyfrę drugiego typu. Razem aż $68$ cyfr. Tutaj, zależnie od wieku uczniów, możemy się zacząć zastanawiać nad tym skąd wiadomo, że $67$ to liczba pierwsza i czy naprawdę trzeba sprawdzać podzielność przez wszystkie liczby od $2$ do $66$. Nawet niedoświadczeni w olimpijskich bojach uczniowie dość szybko zauważają, że wystarczy sprawdzać podzielność od $2$ do $33$, bo gdy spróbujemy podzielić $67$ przez coś pomiędzy $34$ a $66$ to wyjdzie nam coś pomiędzy $1$ a $2$ (czyli liczba niecałkowita). Łatwo jednak pójść z takim uczniem o krok dalej i zauważyć, że nie ma też sensu sprawdzać liczb pomiędzy $23$ a $33$, bo gdy spróbujemy podzielić $67$ przez taką liczbę, to wyjdzie coś pomiędzy dwójką a trójką itd. Nieco bardziej, choć jeszcze nie do końca precyzyjnie: każdemu potencjalnemu małemu dzielnikowi $d$ liczby $n$ przypisany jest również drugi, duży dzielnik tej liczby czyli $\frac{n}{d}$. Co to znaczy mały, a co to znaczy duży? Zanim o to zapytamy uczniów, warto pokazać im jakiś dobry przykład, a takim jest liczba $100$. Można pozwolić uczniom znajdować dzielniki tej liczby:

• $100 = 1 \cdot 100$,
• $100 = 2 \cdot 50$,
• $100 = 4 \cdot 25$,
• $100 = 5 \cdot 20$,
• $100 = 10 \cdot 10$.

W tym przypadku liczby $1, 2, 4, 5$ to te małe dzielniki, a liczby $100, 50, 25, 20$ to te duże. Liczbę $10$ możemy potraktować jako mały i duży dzielnik jednocześnie. Naturalne jest więc pytanie ogólne: gdzie jest ta granica małego i dużego dzielnika, które oczywiście warto postawić uczniom. Tym młodszym może nie warto przedstawiać tego jako pytanie ogólne i oczekiwać, że powiedzą nam $\sqrt{n}$, ale można podać inną konkretną liczbę (np. $400$ albo $144$ albo [trudniej] $200$).

Tutaj gdzieś dobrym pomysłem jest przypomnieć nieco starszym uczniom, że dzielniki liczby możemy generować na podstawie rozkładu na czynniki pierwsze: $100 = 2 \cdot 2 \cdot 5 \cdot 5$, a więc jej dzielnikami są jedynie liczby, które mają w swoim rozkładzie na czynniki pierwsze zero, jedną lub dwie dwójki oraz zero, jedną lub dwie piątki. Z unikalności rozkładu na czynniki pierwsze (nie łudzę się nawet, że uczniowie zobaczyli tego dowód, a bardzo szkoda, co pisałem w serii wpisów A ma Pan dowód?) dostajemy więc od razu, że każda taka kombinacja daje inny dzielnik.

Może jestem dziwny, ale mi od razu rodzą się nowe pytania sprawdzające zrozumienie tematu:

• Ile dzielników ma liczba $1000$?
• Jaka jest najmniejsza liczba, która ma dokładnie $12$ dzielników?
• Znajdź najmniejszy dzielnik większy niż $100$ liczby $4500$.
• Które liczby mają nieparzyście wiele dzielników?

Olimpijczycy od razu mogliby się zastanawiać nad uogólnieniami tych metod i próbą implementacji programów, które rozwiązują tego typu zadania automatycznie.

Naturalnym pytaniem jest teraz wrócić do six-sevenów: chcemy mieć dokładnie $n$ różnych możliwości uzyskania six-sevena. Jaka jest ogólna metoda wyznaczenia ile cyfr potrzebujemy? Nie trudno zauważyć, że chcemy po prostu znaleźć największy mały dzielnik $d \le \sqrt{n}$ i uzyskamy rozwiązanie składające się z $d + \frac{n}{d}$ cyfr.

Z tymi nieco starszymi można teraz przejść do dowodu, że to jest optymalne. Jedną opcją byłoby użycie pochodnej funkcji $f(d) = d + \frac{n}{d}$, czyli $f’(d) = 1 - \frac{n}{d^2}$, znaleźć interesujące nas miejsce zerowe $d = \sqrt{n}$.

Można jednak bardziej elementarnie. Wystarczy przypomnieć sobie inne naturalne pytanie, które można było przerobić z uczniami wcześniej (dobra, znowu nie wierzę, że nauczyciele to robią, chociaż powinni): dla ustalonego obwodu prostokąta (w naszym przypadku dwukrotności sumy $d + \frac{n}{d}$), jaki jest optymalny kształt, który maksymalizuje pole tego prostokąta (w naszym przypadku $d \cdot \frac{n}{d} = n$)? Innymi słowy: wyobrażam sobie, że zamiast myśleć “chcę wygenerować $n$ six-sevenów” myślę “chcę wygenerować prostokąt o polu $n$”, a zamiast myśleć “optymalizując $d + \frac{n}{d}$” myślę “optymalizując obwód prostokąta”. Intuicyjnie jest jasne, że najlepiej przyjąć kwadrat, ale my chcemy wiedzieć formalnie dlaczego tak jest najlepiej. To wynika z wzoru skróconego mnożenia: $(a - b)(a + b) = a^2 - b^2$. Im bardziej oddalone są od siebie (lub raczej: od ich średniej) są czynniki mnożenia, tym mniejszy jest wynik mnożenia (bardziej precyzyjnie: wynikiem jest kwadrat średniej pomniejszony o kwadrat różnicy od średniej).

Kontratak drugi

Zróbmy jednak coś trudniejszego niż po prostu dogłębne rozważanie mnożenia dwóch liczb. Rozważmy teraz napis składający się z różnokolorowych cyfr sześć i siedem. Chcemy zakryć wszystkie cyfry, poza dokładnie dwiema, żeby te dwie pozostawione cyfry (niekoniecznie sąsiednie) tworzyły (w tej kolejności) liczbę $67$.

Na powyższym obrazku możliwe jest uzyskanie czterech six-sevenów (żółto-czerwony, żółto-czarny, zielono-czarny oraz niebiesko-czarny).

Po upewnieniu się, że uczniowie zrozumieli, można przestać już używać kolorów (i zakładać, że cyfry są po prostu różnokolorowe) i zapytać ich o liczbę six-sevenów w napisach:

• 6767676767 (odpowiedź $15$)
• 6666677777 (odpowiedź $25$)
• 7777766666 (odpowiedź $0$)

Moje oczekiwanie byłoby chyba takie, żeby uczniowie intuicyjnie wypracowali sobie metodę, że każda szóstka zwiększa liczbę six-sevenów o liczbę siódemek, które znajdują się po jej prawej stronie.

Kontratak trzeci

Naturalne staje się pytanie odwrotne: gdybyśmy chcieli $10$ six-sevenów, to jaki (najkrótszy możliwy) napis należałoby stworzyć? Wydaje mi się, że narzucającym się jest rozwiązanie 6666677 lub 6677777 (bazując na przykładach z pierwszego kontrataku).

A gdyby chcieć $11$ six-sevenów? Co prawda $11$ to liczba pierwsza, więc pomysł z pierwszego kontrataku sugeruje rozwiązanie 677777777777 lub 666666666667. Można jednak lepiej, na przykład w taki sposób: 66666767. Dostawienie tej ostatniej szóstki zaraz przed ostatnią siódemką do wcześniejszego napisu zawierającego $10$ six-sevenów daje nam nadal te wcześniejsze dziesięć six-sevenów plus jeszcze jeden, składający się z dwóch ostatnich cyfr napisu.

Żeby upewnić się, czy uczniowie zrozumieli powyższy pomysł, warto zapytać o wygenerowanie najkrótszego napisu zawierającego dokładnie $67$ six-sevenów. Oczekujemy tutaj rozwiązania typu: 66666666777776777 ($64 = 8 \cdot 8$ six-sevenów uzyskanych z napisu 6666666677777777 oraz trzy nowe six-seveny po inteligentnym dostawieniu szóstki wewnątrz bloku siódemek, przed dokładnie trzema).

Ponownie zasadnym jest pytanie o optymalność tego rozwiązania. Wyobrażam sobie tutaj dowód składający się z dwóch kroków:

• pokazanie, że każdy napis o długości $\le 16$ ma $\le 64$ six-seveny (a więc nie jest dobry)
• sprawdzenie, że napis, który podaliśmy ma $67$ six-sevenów.

To drugie chyba już zrobiliśmy, a to pierwsze robi się podobnie do uzasadnienia pierwszego kontrataku.

Naturalnym pytaniem jest próba uogólnienia tego rozważania na generowanie napisów zawierających dokładnie $n$ six-sevenów. Nie jest to chyba bardzo trudne, bo możemy wyjść zawsze od napisów postaci $\underbrace{\texttt{66}\ldots\texttt{66}}_k\underbrace{\texttt{77}\ldots\texttt{77}}_k$ lub napisów postaci $\underbrace{\texttt{66}\ldots\texttt{66}}_k \texttt{6} \underbrace{\texttt{77}\ldots\texttt{77}}_k$ i dostawić w odpowiednim miejscu wewnątrz bloku siódemek jedną szóstkę w podobny sposób jak powyżej. Szczegóły do dopracowania, ale wydaje mi się, że nie jest to zbyt skomplikowane. Wyobrażam sobie, że mógłbym dać tego typu zadanie na jakiś sparing. Oh wait, odrobinę trudniejsze zadanie tego typu już dałem na Olimpiadę Informatyczną Juniorów.

Inne kontrataki

Pokrótce napiszę jakie jeszcze pomysły przychodzą mi do głowy:

• Gdyby rozpatrzyć wszystkie $2^n$ napisów złożonych z szóstek i siódemek i dodać do siebie liczby six-sevenów dla wszystkich tych napisów to ile równa jest ta suma? (odpowiedź: $n \cdot (n+1) \cdot 2^{n-2}$)
• Ile jest napisów długości $n$ zawierających dokładnie $k$ six-sevenów? (tutaj widziałbym napisanie programu opartego o programowanie dynamiczne, ale nie myślałem o tym na tyle długo, żeby wykluczyć lepsze metody)

Zapytałem też kilka czatów AI o pomysły na inne kontrataki i jeden z nich nawet trochę przypadł mi do gustu. Zdefiniujmy wynik napisu jako liczba six-sevenów minus liczba seven-sixów (rozważamy je jako podciągi, tak jak w kontrataku drugim i trzecim). Czat zaczął rozważać dla jakich napisów możliwe jest uzyskanie wyniku $0$ i wywnioskował strukturę (niestety nie wszystkich) napisów, które uzyskują taki wynik. Podejrzewam, że gdyby pociągnąć ten pomysł dalej (samemu lub z czatem), to dałoby się coś jeszcze ciekawego ułożyć.

A jakie pomysły przychodzą do głowy Wam? Zachęcam do podzielenia się w komentarzach.