Shutterstock
Strona główna

Wzorce, podziały, wariacje, czyli o liczbach Bella

Rys. 1Marek Penszko Rys. 1
Tabela 1Marek Penszko Tabela 1
Tabela 2Marek Penszko Tabela 2
Marek Penszko
Rys. 2Marek Penszko Rys. 2
Tabela 3Marek Penszko Tabela 3
Marek Penszko
Marek Penszko
Rys. 3Marek Penszko Rys. 3
Rys. 4Marek Penszko Rys. 4
Rys. 5Marek Penszko Rys. 5
Rys. 6Marek Penszko Rys. 6
materiały prasowe
Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.Scientific American Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.
Zagadka numeru.

Zastępowanie liter cyframi kojarzy się z trywialnym szyfrowaniem. Liter w abecadle jest jednak znacznie więcej niż cyfr w systemie dziesiętnym, więc większości liter w takim podstawieniowym szyfrze (na przykład w najprostszym: A=1, B=2, C=3, …) odpowiadają nie pojedyncze cyfry, lecz liczby dwucyfrowe. Do cyfr solo można się ograniczyć, szyfrując tekst zapisany znacznie krótszym alfabetem, powiedzmy hawajskim, w którym liter jest dwanaście, zatem należałoby tylko dodać trzy nowe cyfry, oznaczające liczby 10, 11 i 12.

Matematyka rekreacyjna radzi sobie z ograniczeniem liczb do jednocyfrowych bardziej radykalnie: szyfrowany tekst nie może zawierać więcej niż dziesięciu różnych liter. Praktycznie „tekst” sprowadza się do kilku słów, najczęściej trzech, tworzących zwykle zaszyfrowane działanie arytmetyczne zwane alfametykiem lub ogólniej kryptarytmem, na przykład takie, jak na rys. 1.

Rozwiązywanie, czyli jakby rozszyfrowywanie alfametyku, można właściwie uznać za operację odwrotną, czyli szyfrowanie cyframi w taki sposób, aby otrzymane liczby tworzyły poprawne dodawanie. Trzeba oczywiście pamiętać o tym, że takim samym literom muszą odpowiadać identyczne cyfry, a różnym – różne.

Familijny alfametyk jest idealny, ponieważ spełnia wszystkie warunki, określające „ideał”:

– jest sensowny;

– zawiera dziesięć różnych liter;

– ma tylko jedno rozwiązanie;

– do rozwiązania dochodzi się dość łatwo na logikę.

Innego rodzaju alfametyk można utworzyć z tytułu ŚWIAT NAUKI: liczba zastępująca ŚWIAT powinna być sześcianem, a szyfrująca wyraz NAUKI kwadratem. To już nie ideał, bo chociaż jest sens i jedno rozwiązanie, to kompletu dziesięciu liter nie ma, a co istotniejsze – rozwiązywanie „na piechotę” jest bardzo żmudne, więc praktycznie należy skorzystać z komputera, który po zaprogramowaniu szybko znajduje właściwe potęgi: ŚWIAT=10 648 (223), NAUKI=34 596 (1862). DZIECI zamiast liczby 546 196 (w rozwiązaniu innego dodawania: MALUCH+MALUCH=DZIECI) oraz ŚWIAT zamiast 10 648 to zastępstwa alfametyczne, co oznacza, że miejsce liczb zajmują słowa. Takie podstawienie stanowi szczególny przypadek kryptarytmetycznego, w którym liczby szyfrowane są ciągiem dowolnych znaków, a więc także dowolnych liter. Jest jeszcze jeden specyficzny rodzaj podstawienia kryptarytmetycznego, zwany porządkowym, interesujący ze względu na aspekt matematyczny. Stanowi on jakby odwrócenie podanego wyżej trywialnego szyfru A=1, B=2, C=3, … .

Mając jakąś n-cyfrową liczbę, zmieniamy jej cyfry na litery w następujący sposób: pierwszej cyfrze odpowiada zawsze litera A, zaś każdej następnej różnej od poprzednich – kolejna litera alfabetu łacińskiego. Takie same, powtarzające się cyfry oznaczamy identycznymi literami. Teraz liczba 10 648, która poprzednio była ŚWIAT-em, zmieni się w ABCDE, a całe rozwiązanie alfametyku ŚWIAT NAUKI, czyli 10 648 34 569, przybierze postać ABCDE FDGHC. Gdyby jednak dwie podane liczby nie były ze sobą powiązane, czyli nie tworzyły jednego tytułu (zbioru), wówczas zaszyfrowana postać każdej z nich, zwana wzorcem, byłaby taka sama – ABCDE, ponieważ obie zawierają pięć różnych cyfr. Aspekt matematyczny podstawienia porządkowego wiąże się właśnie z wzorcami literowymi odpowiadającymi „samotnym” liczbom.

Dziewięciu liczbom 1-cyfrowym odpowiada jeden wzorzec: A; dziewięćdziesięciu 2-cyfrowym – dwa wzorce: AA i AB; dziewięciuset 3-cyfrowym – pięć wzorców: AAA, AAB, ABA, ABB, ABC; dziewięciu tysiącom 4-cyfrowych – piętnaście wzorców: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD itd. Ogólnie 9×10n-1 liczbom n-cyfrowym odpowiada w wzorców. Dla kolejnych 1≤n≤10 liczby w tworzą ciąg: 1, 2, 5, 15, 52, 203, 877, 4140, 21 147, 115 975. Jest to początkowy fragment ciągu, zawierającego tzw. liczby Bella*. Fragment także dlatego, ponieważ jedenasty wyraz w (678 569), odpowiadający liczbie 11-cyfrowej, już liczbą Bella nie jest – podobnie jak wszystkie kolejne. Wynika to z następującej własności: liczba Bella (bn) określa, ile jest literowych wzorców (wn) liczby n-cyfrowej w c-cyfrowym systemie liczbowym, jeśli nŁc.

Dla każdego n≤c wn=bn. Jeżeli natomiast n>c, to wn<bn. Im większa różnica między n a c, tym większa między wn a bn. Konkretna wartość tej różnicy jest stała tylko dla n=c+1. Wtedy wn=bn–1 dla każdego c, bo jedyny wzorzec n-literowy bez odpowiednika w systemie (n–1)-cyfrowym ma postać (Rn-1)X, gdzie (Rn-1) to fragment wzorca złożony z n–1 różnych liter, a X – nowa litera, odpowiadająca nowej n-tej cyfrze. Gdy natomiast n>c+1, znalezienie wartości wn bywa nieco kłopotliwe. Na przykład, dla n=5 i c≥5 wn=bn=52 (tabela 1). Ten zbiór dla c=4 zmniejsza się o jeden wzorzec (różowy); następnie dla c=3 maleje po usunięciu 10 niebieskich do 41 (białe i żółte); wreszcie dla c=2 ubywa jeszcze 25 (żółte), czyli pozostaje 16 (białe) literowych wzorców liczb 5-cyfrowych w systemie 2-cyfrowym.

Matematycznie ciekawsza jest zależność wn=f(nc), czyli liczba wzorców wn dla liczb różnej długości (n=1, 2, 3, …) w konkretnych c-cyfrowych systemach.

Jeśli c=1, to wn=1 dla każdego n. Gdy c=2, wartości wn tworzą znany ciąg potęgowy: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512,…}. Ciągi wn dla 3≤c≤9 podane są w tabeli 2.

Dla c=2 wzór na wyraz ogólny ciągu jest prosty (wn=2n–1), ale dla kolejnych c staje się coraz bardziej skomplikowanym (n–1)-składnikowym wielomianem n-tego stopnia. Na przykład dla c=7 ma postać:

Ciągi wn dla kolejnych c zawierają coraz dłuższy początkowy fragment ciągu Bella (czerwone liczby), a zatem jakby „zbliżają się” do tego ciągu, gdy c zmierza do nieskończoności. Inaczej mówiąc: każdy n-ty wyraz ciągu {wi} albo jest równy liczbie Bella, albo wraz ze wzrostem c jest coraz bliższy n-tej liczbie Bella bn, aż w końcu dla c=n ją osiąga. Równocześnie rośnie liczba składników we wzorze ogólnym na n-tą liczbę Bella, co czyni ten wzór praktycznie „nieużytecznym”. Czy z tą niepraktycznością można sobie poradzić?

Przed odpowiedzią na to pytanie powróćmy do interpretacji liczb Bella. Przedstawiona wyżej, odwołująca się do wzorców literowych, stanowi jedną z nich, ale raczej drugoplanową. Podstawowa definicja brzmi bowiem inaczej. Zwięźle i ściśle matematycznie tak: n-ta liczba Bella (bn) to liczba wszystkich partycji zbioru n-elementowego. A bardziej przystępnie: to liczba sposobów podziału zbioru złożonego z n elementów. Albo inaczej: liczba sposobów pogrupowania n elementów. Pięć różnych podziałów zbioru {A, B, C} lub pogrupowań trzech elementów (A, B, C) na rys. 2 odpowiada trzeciej liczbie Bella, a więc także pięciu wzorcom literowym liczby 3-cyfrowej. Konkretne przyporządkowanie wzorcom jest jednak wyraźnie widoczne tylko dla ostatniego tercetu podzbiorów/grup jednoelementowych.

Liczby Bella można też określać na wiele innych sposobów. Na przykład tak: każda bn jest liczbą n-elementowych wariacji z powtórzeniami ze zbioru n-elementowego pomniejszoną o liczbę wariacji bliźniaczych. Bliźniaczymi są wariacje, w których każdy element x albo nie zmienia się, albo zostaje zastąpiony elementem y różnym od wszystkich elementów zi≠x.

Tabela 3 obejmuje wszystkie 27 3-elementowych wariacji z powtórzeniami ze zbioru 3-elementowego podzielonych na pięć grup bliźniaczych. Pięć czerwonych w pierwszym wierszu pozostaje po usunięciu ich „bliźniaków”, a więc odpowiada liczbie b3.

Liczby Bella wiążą się także z rozkładem liczb na czynniki pierwsze. Gdy w rozkładzie liczby R występuje n różnych czynników i żaden się nie powtarza, wówczas liczba Bella oznacza, na ile sposobów można przedstawić R w postaci iloczynu (uwzględniając też samo R). Przykładem może być pamiętny rok 1410. To liczba, która ma w rozkładzie cztery czynniki pierwsze – 1410=2×3×5×47, a b4=15:

Powracając do postawionego wyżej pytania: nie jest znany prosty wzór, który umożliwiałby po wykonaniu krótkiego działania obliczenie dajmy na to pięćdziesiątej siódmej liczby Bella (inna sprawa, że w tym przypadku liczenie i tak nie byłoby krótkie, bo liczba ta składa się z… 57 cyfr). Możliwy do praktycznego stosowania, ale w ograniczonym zakresie, jest tylko wzór rekurencyjny.

Ograniczenie wynika ze żmudnych obliczeń oraz konieczności korzystania z wszystkich liczb Bella mniejszych od szukanej, a więc trzeba je znać. Dotarcie zatem na przykład do trzynastej liczby wymaga policzenia i zsumowania dwunastu iloczynów symbolu Newtona i k-tej liczby Bella. Trochę szybsze wydaje się skorzystanie z tablicowego odpowiednika powyższego wzoru zwanego trójkątem Bella (rys. 3). Tworzenie tego trójkąta zaczyna się od niebieskiej jedynki i dwójki w górnym rzędzie. Wpisywaniem pozostałych liczb rządzą dwie proste zasady: 1) ostatnia liczba w danym rzędzie jest przenoszona na początek następnego rzędu; 2) liczba umieszczana w każdym polu (poza pierwszym w rzędzie) jest sumą dwóch liczb – sąsiadki z lewej strony i liczby znajdującej się nad tą sąsiadką. W rezultacie każda liczba, oprócz skrajnych prawych i górnych, stanowi różnicę jej sąsiadek – prawej i górnej. Przede wszystkim jednak efektem są kolejne liczby Bella, pojawiające się na „stoku”, a po przeniesieniu także w pierwszej kolumnie. Efektem jest także pozornie osobliwa własność trójkąta: przedostatnia liczba w każdym rzędzie (oprócz pierwszego) jest równa sumie liczb w rzędzie piętro wyżej, jak również suma liczb w danym rzędzie i liczby na końcu tego rzędu równa jest liczbie Bella na końcu następnego rzędu. Dysponując liczbami z pierwszej kolumny na rys. 3, nieco łatwiej policzyć następną, czyli czternastą liczbę w trójkącie, niż korzystając z wzoru rekurencyjnego.

Własności liczb Bella, a zwłaszcza ich powiązania z innymi liczbami (na przykład Catalana, Stirlinga, liczbą e), są tematem wielu prac naukowych. Niektóre z tych własności ze względu na ich specyfikę zasługują przynajmniej na wzmiankę w ramach matematycznych rekreacji.

Szukając regularności w ciągu liczb Bella, najłatwiej zauważyć związaną z parzystością, parzysta jest bowiem każda co trzecia liczba, zaczynając od drugiej. Stąd dwa proste wnioski – nieparzystych liczb Bella jest dwukrotnie więcej niż parzystych oraz suma każdego tercetu kolejnych liczb jest parzysta.

W roku 1933 matematyk francuski Jacques Touchard udowodnił osobliwą kongruencję, którą można zapisać w postaci: bnbnp+bnp+1 (mod p), gdzie p jest dowolną liczbą pierwszą nie większą od n. Inaczej mówiąc, reszta z dzielenia bn przez p jest taka sama, jak reszta z dzielenia przez p sumy bnp i bnp+1. Na przykład dla n=11 i p=7 mamy: b11b4+b5 (mod 7), czyli 678 570≡15+52=67 (mod 7) i istotnie – wielokrotnościami siedmiu są liczby mniejsze od 678 570 i 1080 o tyle samo, czyli o 4. Szczególny przypadek występuje, gdy n=p; wówczas bnb0+b1 (mod n), czyli pojawia się zerowy wyraz ciągu (b0) – przyjmuje się, że jest on równy 1. Stąd zaskakujący wniosek: jeżeli n jest liczbą pierwszą, to bn≡2 (mod n). A zatem jeśli od n-tej liczby Bella, gdy n=p, odejmiemy 2, to różnica zawsze będzie podzielna przez n. Na przykład dla n=13 bn=27644437, a 27644435:13=2126495.

A skoro o liczbach pierwszych mowa, to warto wspomnieć o polowaniu na nie w gąszczu bn. Początek jest łatwy i owocny: pierwszymi pierwszymi są b2, b3, b7 i b13. Kontynuacji łowów podjął się w latach 80. jeden z pionierów informatyki Vaughan Pratt, a łupem padły kolejne pierwsze – 38-cyfrowa b42 i 54-cyfrowa b55. Siódma i dotąd ostatnia została ostatecznie upolowana dopiero w roku 2004. Komputery się napracowały, bo to 6539-cyfrowy potwór b2841.

Na koniec krótki powrót do literowych wzorców liczb, a ściślej kwadratów. Żaden kwadrat nie pasuje do wzorca An, jeśli n≥2, ani do wzorca AnB, gdy n≥3 (An oznacza n-cyfrowy ciąg cyfr A). Dlaczego? Warto się nad tym zastanowić w ramach ćwiczenia przed zadaniami konkursowymi.

Zadania

1. Liczba b12=4 213 597 ma dwie szczególne własności:

I) składa się z różnych cyfr,

II) w rozkładzie tej liczby na czynniki pierwsze nie ma innych cyfr niż te, które są w niej samej – 4 213 597=37×47×2423.

Liczba b6=4140 ma własności przeciwne:

III) nie składa się z różnych cyfr;

IV) w rozkładzie tej liczby na czynniki pierwsze wszystkie cyfry są inne niż w niej samej – 4140=2×2×3×3×5×23.

Proszę znaleźć przynajmniej jedną z trzech najmniejszych liczb 5-cyfrowych (oczywiście nie Bella), która ma własność (I) i (IV).

2. Słowa LICZBA i BELLA zastępują iloczyny cząstkowe w zapisie mnożenia (rys. 4). Należy rozszyfrować działanie, wiedząc że takim samym literom odpowiadają jednakowe cyfry, a różnym – różne. Ponadto wiadomo, że wszystkie cyfry, ukrywające się pod literami słowa BELLA są jednocyfrowymi liczbami pierwszymi.

3. Wzorcem literowym niektórych kwadratów jest AnBmC, gdzie n i m oznaczają dowolną liczbę kolejnych liter A i B we wzorcu, a więc także odpowiadających im cyfr. Na przykład, dla n=m=2 wzorcowi odpowiada liczba 11 449 (1072), a dla n=4, m=2 – 5 555 449 (23572). Jaka trójka cyfr powinna być zaszyfrowana literami A, B, C, aby istniało nieskończenie wiele kwadratów o podanym wyżej wzorcu?

Rozwiązania prosimy nadsyłać do 31 lipca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 07/20. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Mary Roach Do boju. Jak w skrajnych sytuacjach pozostać w jednym kawałku, zachować zmysły i nie złapać infekcji ufundowaną przez wydawnictwo Prószyński Media. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji Konkursu.

Regulamin konkursu jest dostępny na stronie www.swiatnauki.pl

***

*Eric Temple Bell (1883–1960) – amerykański matematyk i pisarz pochodzenia szkockiego. Zajmował się głównie teorią liczb i kombinatoryką. Autor poczytnej choć kontrowersyjnej książki o matematykach (Men of Mathematics…, 1937) oraz (pod pseudonimem John Taine) kilkunastu powieści science fiction.

***

Rozwiązania zadań z numeru majowego

1. Schematy pierwotnych piątek pitagorejskich są dwa: N+N+N+N=P i N+P+P+P=N.

2. Rozmieszczenie kwadratów różnych liczb od 1 do 9 (oprócz 8) takie, jak na rys. 5, daje największą sumę 12 iloczynów par kwadratów na końcach wspólnej krawędzi równą 11 209.

3. Szukana czwórka pitagorejska: 13-16-40-45 (jednocyfrowe sumy cyfr tych czterech liczb także są czwórką pitagorejską: 4-4-7-9).

4. Zapewne najprostszą interpretacją geometryczną piątki pitagorejskiej jest połączenie trójkąta prostokątnego o przyprostokątnych (a, b) i przeciwprostokątnej c z prostopadłościanem o krawędziach (c, d, e) i przekątnej f. W takim układzie (rys. 6) a2+b2=c2 oraz c2+d2+e2=f2, czyli a2+b2+d2+e2=f2.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Jima Baggotta Przestrzeń kwantowa. Pętlowa grawitacja kwantowa i poszukiwanie struktury przestrzeni, czasu i Wszechświata, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Andrzej Gałka z Wrocławia, Piotr Iwiński z Torunia, Magdalena Kowalczyk i Jakub Krawczyk z Krakowa, Wojciech Ożdżeński z Warszawy.

Świat Nauki 07.2020 (300347) z dnia 01.07.2020; Umysł giętki; s. 72

Ta strona do poprawnego działania wymaga włączenia mechanizmu "ciasteczek" w przeglądarce.

Powrót na stronę główną