Zlicz wszystkie trójkąty poza jednobarwnymi. Może Ci w tym pomóc poniższa tabelka, w której komórka leżąca na skrzyżowaniu i-tego wiersza i j-tej kolumny oznacza kolor (n – niebieski, z – zielony) odcinka łączącego punkty i-ty oraz j-ty.

	1	2	3	4	5	6	7	8	9	10
1		z	z	n	n	z	z	z	n	z
2	z		z	z	n	z	z	z	n	z
3	z	z		n	n	z	n	n	n	z
4	n	z	n		n	z	n	z	n	n
5	n	n	n	n		n	z	z	z	z
6	z	z	z	z	n		z	z	n	n
7	z	z	n	n	z	z		z	z	n
8	z	z	n	z	z	z	z		n	z
9	n	n	n	n	z	n	z	n		n
10	z	z	z	n	z	n	n	z	n

Wszystkich trójkątów o wierzchołkach w wybranych punktach jest tyle, co kombinacji 3-elementowych ze zbioru 10-elementowego (tj. możliwych sposobów wyboru trzech elementów z dziesięciu), czyli:

(10 · 9 · 8) / (1 · 2 · 3) = 120.

 

Zamiast zliczać trójkąty jednobarwne, przyjrzymy się różnobarwnym (mającym dwa boki tego samego koloru i trzeci innego), po czym odejmiemy ich liczbę od 120.

Każdy trójkąt różnobarwny ma dokładnie dwa wierzchołki, w których spotykają się dwa różnokolorowe boki; co więcej, każde takie spotkanie różnokolorowych boków wyznacza (niezależnie od koloru trzeciego boku) trójkąt różnobarwny. Dla każdego punktu wyznaczmy zatem liczby kończących się w nim kolorowych i czarnych odcinków – wyniki znajdują się w poniższej tabelce:

Punkt	1	2	3	4	5	6	7	8	9	10
Niebieskie odcinki	3	2	5	6	5	3	3	2	7	4
Zielone odcinki	6	7	4	3	4	6	6	7	2	5

Następnie zsumujmy iloczyny tych par:

18 + 14 + 20 + 18 + 20 + 18 + 18 + 14 + 14 + 20 = 174.

W ten sposób otrzymamy podwojoną liczbę trójkątów różnobarwnych. Stąd liczba trójkątów jednobarwnych to:

120 - 174 / 2 = 33.

Jak może wyglądać zbiór tomów, które mogą nie zostać ani razu przestawione?

Zbiór tomów, które mogą nie zostać ani razu ruszone, musi, oczywiście, stanowić podciąg rosnący (pod względem numerów) wyjściowego ciągu tomów. Z drugiej strony, jeżeli wybierzemy jakikolwiek podciąg rosnący w rzędzie tomów i postanowimy sobie, że właśnie tych tomów nie zamierzamy ruszać, to możemy każdy z pozostałych tomów, poczynając od tych o najmniejszych numerach, wstawić w jednym ruchu we właściwe miejsce w ramach tego podciągu. Skoro tak, to wybierzmy najdłuższy taki podciąg rosnący; szukana minimalna liczba ruchów będzie wówczas równa 12 minus długość tego ciągu.

Jak w systematyczny sposób wyznaczyć długość najdłuższego podciągu rosnącego naszego ciągu

11, 1, 10, 4, 3, 2, 8, 7, 12, 6, 9, 5?

Można chociażby dla każdego elementu policzyć długość najdłuższego podciągu rosnącego kończącego się na nim, a potem wziąć największą spośród tych wartości.

Dla każdego z pierwszych dwóch tomów szukanym wynikiem jest 1. Trzeci tom ma numer 10, więc można za jego pomocą przedłużyć jednoelementowy ciąg rosnący kończący się na tomie numer 1, otrzymując ciąg długości 2. Podobnie ma się sytuacja w przypadku każdego z kolejnych trzech tomów: 4, 3, 2 – daje to ciąg początkowych wyników:

tomy:	11	1	10	4	3	2
długości podciągów:	1	1	2	2	2	2

Kolejny tom, ten o numerze 8, może zostać użyty nie tylko do przedłużenia wspomnianego już ciągu jednoelementowego, ale także każdego spośród stworzonych już ciągów dwuelementowych, które kończą się tomami o numerach mniejszych niż 8, tj. 4, 3 i 2. To oznacza, że wynikiem dla tego tomu jest 3:

tomy:	11	1	10	4	3	2	8
długości podciągów:	1	1	2	2	2	2	3

Widać już, jak kontynuować te obliczenia – wystarczy każdorazowo wybierać najdłuższy ciąg spośród dotychczas utworzonych, kończący się tomem o numerze mniejszym niż numer rozważanego tomu, i ten właśnie ciąg przedłużać. W ten sposób otrzymamy następującą tabelkę wyników:

tomy:	11	1	10	4	3	2	8	7	12	6	9	5
długości podciągów:	1	1	2	2	2	2	3	3	4	3	4	3

Stąd najmniejsza konieczna liczba ruchów jest równa 12 - 4 = 8. Jako ćwiczenie pozostawiamy znalezienie jakiegoś 4-elementowego podciągu rosnącego tomów i wykonanie ośmiu ruchów, po których ciąg tomów stanie się uporządkowany rosnąco.

W jednej serii ruchów doprowadź do sytuacji, w której pierwszy tom znajdzie się na początku półki. Następnie „usuń” ten tom i powtarzaj tę samą procedurę dla tomów 2, ..., 12.

Poniższa tabelka pokazuje, jak zrealizować procedurę opisaną we wskazówce. Przestawiamy w niej kolejno tomy od pierwszego do dwunastego w kierunku początku ciągu, a w momencie przesuwania powiększamy wynik o liczbę nieruszonych jeszcze tomów położonych na lewo od wykreślanego.

Krok	Liczba ruchów	Układ tomów
1	1	11, 1, 10, 4, 3, 2, 8, 7, 12, 6, 9, 5
2	4	1, 11, 10, 4, 3, 2, 8, 7, 12, 6, 9, 5
3	3	1, 2, 11, 10, 4, 3, 8, 7, 12, 6, 9, 5
4	2	1, 2, 3, 11, 10, 4, 8, 7, 12, 6, 9, 5
5	7	1, 2, 3, 4, 11, 10, 8, 7, 12, 6, 9, 5
6	5	1, 2, 3, 4, 5, 11, 10, 8, 7, 12, 6, 9
7	3	1, 2, 3, 4, 5, 6, 11, 10, 8, 7, 12, 9
8	2	1, 2, 3, 4, 5, 6, 7, 11, 10, 8, 12, 9
9	3	1, 2, 3, 4, 5, 6, 7, 8, 11, 10, 12, 9
10	1	1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 12
11	0	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
12	0	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
13		1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

A zatem udało nam się uporządkować półkę za pomocą 31 ruchów. Poszło nam całkiem łatwo, ale musimy sobie jeszcze odpowiedzieć na pytanie, czy aby na pewno wykonaliśmy najmniejszą możliwą liczbę ruchów?

Powiemy, że dwa tomy na półce tworzą inwersję, jeżeli pierwszy z nich leży na lewo od drugiego oraz ma numer większy od drugiego (przykładem takiej sytuacji są tomy o numerach 7 i 10 na naszej „początkowej” półce). Zauważmy, że:

• na uporządkowanej rosnąco półce nie ma żadnych inwersji – a do takiego układu dążymy;
• jeden ruch, czyli zamiana miejscami sąsiednich tomów, może zmienić liczbę inwersji co najwyżej o 1 (tj. dodać lub usunąć inwersję między przestawianymi tomami);
• w naszej metodzie w każdym ruchu przenosimy mniejszy element na lewo, czyli usuwamy jedną inwersję.

Wniosek: wymagana liczba ruchów jest co najmniej tak duża jak liczba inwersji w ciągu, a z drugiej strony liczba ruchów wykonywanych w naszej metodzie jest dokładnie taka sama jak liczba inwersji. To uzasadnia, że nasza metoda daje najlepszy możliwy wynik dla dowolnej początkowej postaci półki, a w szczególności dla tej z naszego zadania.

Zastosuj metodę „dziel i zwyciężaj”: jak sprowadzić problem dla kwadratu 8 na 8 do czterech podobnych problemów dla kwadratów 4 na 4?

Podzielmy wyjściowy kwadrat na cztery mniejsze i umieśćmy jeden klocek tak, aby każda z części była kwadratem 4 na 4 z brakującym jednym polem:

Teraz wykonajmy analogiczny krok dla każdego z kwadratów 4 na 4:

W wyniku poprzedniego kroku pozostaje 16 kwadratów 2 na 2 z brakującym polem – pokrywając każdy z nich za pomocą jednego klocka, otrzymujemy kompletne rozwiązanie dla wyjściowej szachownicy:

Przede wszystkim policz, ile ten ciąg ma elementów. Następnie przyjrzyj się sumom kolejnych prefiksów (tj. początkowych fragmentów) tego ciągu.

Jeżeli zaczniemy wyznaczać kolejne sumy prefiksów naszego ciągu (a dokładniej reszty z dzielenia ich przez 13), to gdy tylko natrafimy na zero, będzie znaczyło, że znaleźliśmy jeden z szukanych podciągów o sumie podzielnej przez 13. Łatwo sprawdzić, że taka sytuacja nie występuje w przypadku naszego ciągu. Czy jest to jedyny przypadek, dla którego odpowiedź na postawione pytanie mogłaby być pozytywna? Oczywiście nie: może się też zdarzyć, że suma i-tego prefiksu będzie równa sumie jakiegoś j-tego prefiksu (dla i < j) – wówczas fragment ciągu od wyrazu (i+1)-szego do j-tego włącznie będzie jednym z szukanych podciągów, gdyż jego suma jest różnicą sum tych prefiksów.

Podany ciąg ma 15 elementów, a wartości sum prefiksów są liczbami od 0 do 12 (modulo 13). To oznacza, że wśród tych sum musi się jakaś powtórzyć (fakt ten nazywa się mądrze Zasadą Szufladkową Dirichleta), dzięki czemu niezależnie od konkretnych wartości wyrazów ciągu będziemy mogli znaleźć żądany spójny podciąg sumujący się do wielokrotności 13.

Jeżeli ktoś nie wierzy w całe to abstrakcyjne rozumowanie, to proponujemy przyjrzeć się resztom z dzielenia przez 13 sum kolejnych prefiksów wyjściowego ciągu:

1, 2, 11, 5, 4, 8, 7, 12, 6, 9, 3, 5, 2, 4, 7.

Mamy tu jakieś powtórzenia – wybierzmy z nich, powiedzmy, parę piątek. Wyznaczają one fragment wyjściowego ciągu od piątego do dwunastego wyrazu:

12, 4, 12, 5, 7, 3, 7, 2,

którego suma jest równa 52 = 4 · 13.

Dla każdego prefiksu (tj. początkowego fragmentu) ciągu policz, ile podciągów w nim zawartych ma sumy dające reszty 0, 1, 2, 3, 4 z dzielenia przez 5.

Wskazówka podpowiada, co należy policzyć, jednakże nie daje żadnej informacji o tym, jak to zrobić. Spróbujmy zatem wykonać „ręcznie” kilka pierwszych kroków, może coś z tego wyjdzie. Przypomnijmy jeszcze nasz ciąg:

3, 2, 3, 4, 1, 1, 2, 3.

Początek jest prosty – dla pierwszego prefiksu mamy tylko jeden podciąg [3], więc tabelka wyników dla reszt od 0 do 4 wygląda tak: Podciągi kolejnego prefiksu to: [3], [2] oraz [3, 2] – daje to tabelkę:

A jak wyglądają podciągi prefiksu 3, 2, 3? Podzielmy je na dwie grupy – na podciągi prefiksu o jeden krótszego oraz na te, które zawierają końcową trójkę prefiksu. Tabelkę wyników dla tych pierwszych już wypisaliśmy. Natomiast sumy podciągów z drugiej grupy są takie same, jak sumy podciągów z pierwszej, tylko powiększone o 3. Daje to tabelkę wyników: przesuniętą cyklicznie o 3 w stosunku do poprzedniej tabelki. Wystarczy teraz wysumować obie te tabelki i jesteśmy w domu:

Sprawdźmy, czy o niczym nie zapomnieliśmy: dwa podciągi [3, 2] i [2, 3] mają sumy podzielne przez 5, podciąg [3, 3] daje resztę 1, podciąg [2] – resztę 2, a podciągi dające resztę 3 to [3] oraz [3, 2, 3]. Chwila, ale pierwszy z tych podciągów powinniśmy policzyć dwukrotnie, gdyż w naszym prefiksie mamy dwie trójki! To pokazuje, że w naszych obliczeniach zapomnieliśmy o jednoelementowym podciągu odpowiadającym ostatniemu elementowi rozważanego prefiksu – faktycznie, nie załapał się on do żadnej z rozważanych grup. Po jego uwzględnieniu (trzecia tabelka) otrzymujemy już poprawny wynik:

Dla kolejnego prefiksu – 3, 2, 3, 4 – możemy postąpić podobnie. Wystarczy zsumować trzy tabelki: poprzednią, poprzednią przesuniętą cyklicznie o 4 oraz tabelkę odpowiadającą podciągowi [4]:

Teraz możemy już stosunkowo łatwo wykonać kolejne kroki, odpowiadające elementom 1, 1, 2, 3:

Ostatecznie mamy więc 50 podciągów wyjściowego ciągu, których sumy dzielą się przez 5 – wypisanie ich wszystkich byłoby bardzo żmudnym zadaniem. A Tobie, Czytelniku, pozostawiamy wyznaczenie liczby spójnych podciągów o sumach podzielnych przez 5. Można do tego podejść całkiem podobnie; tym razem jednak w wyliczanych tabelkach należy uwzględnić tylko spójne podciągi kończące się na ostatnich pozycjach kolejnych prefiksów ciągu. Dodajmy, że w wyniku powinno się otrzymać 6.

Wskazówka do pierwszej części zadania: idź po kolei. Do drugiej: nie idź po kolei, ale po potęgach dwójki (cokolwiek by to miało znaczyć).

Zacznijmy od pierwszej części zadania. Zgodnie ze wskazówką, idziemy po kolei: 2¹ kończy się cyfrą 2, 2² kończy się cyfrą 4, 2³ kończy się cyfrą 8, 2⁴ kończy się cyfrą 6, 2⁵ kończy się cyfrą 2. I w tym miejscu możemy już skończyć: łatwo widzimy, że dalej reszty będą się powtarzać. Ponieważ 1000 dzieli się przez 4, to 2¹⁰⁰⁰ kończy się tą samą cyfrą co 2⁴, tzn. cyfrą 6.

Druga część zadania jest nieco trudniejsza. Moglibyśmy znów iść po kolei: 2¹ kończy się cyframi 02,
2² kończy się cyframi 04,
2³ kończy się cyframi 08,
2⁴ kończy się cyframi 16,
2⁵ kończy się cyframi 32,
2⁶ kończy się cyframi 64,
2⁷ kończy się cyframi 28,
2⁸ kończy się cyframi 56...

ale szybko nam się znudzi, a nie będziemy mieli gwarancji, że nie będziemy musieli przejrzeć kilkudziesięciu możliwości, zanim uda nam się znaleźć powtórzenie dwóch cyfr. Podążając za wskazówką, możemy zamiast tego obliczać ostatnie cyfry potęg dwójki o wykładnikach będących potęgami dwójki. W tym celu za każdym razem podnosimy poprzednią wartość do kwadratu:

2¹ – cyfry 02,
2² – cyfry 04,
2⁴ – cyfry 16,
2⁸ – cyfry 56,
2¹⁶ – cyfry 36,
2³² – cyfry 96,
2⁶⁴ – cyfry 16,
2¹²⁸ – cyfry 56,
2²⁵⁶ – cyfry 36,
2⁵¹² – cyfry 96.

Zauważmy, że mieliśmy po drodze trochę szczęścia, gdyż trzy ostatnie wartości mogliśmy po prostu przepisać. Teraz wystarczy przedstawić 1000 w układzie binarnym:

1000 – 512 = 488, 488 – 256 = 232, 232 – 128 = 104, 104 – 64 = 40, 40 – 32 = 8

i już możemy ostatecznie obliczyć ostatnie dwie cyfry 2¹⁰⁰⁰ na podstawie 2⁸, 2³², 2⁶⁴, 2¹²⁸, 2²⁵⁶ i 2⁵¹²:

56 · 96 · 16 · 56 · 36 · 96 = 76 · 16 · 56 · 36 · 96 = 16 · 56 · 36 · 96 = 96 · 36 · 96 = 56 · 96 = 76.

Oczywiście, równości powyżej nie są prawdziwymi równościami, tylko zachowują dwie ostatnie cyfry. W każdym razie dwie ostatnie cyfry 2¹⁰⁰⁰ to 76.

Wypisz wszystkie liczby naturalne od 1 do 17 i połącz za pomocą krawędzi wszystkie pary postaci (m, 2m).

Na początku zastosujemy się do zalecenia ze wskazówki i połączymy krawędziami wszystkie pary (m, 2m) dla m ∈ Z. Żeby się przy tym przypadkiem nie pomylić, spróbujmy zabrać się do tego jakoś systematycznie, np. po kolei. 1 powinna być połączona z 2, 2 z 4, 4 z 8, 8 z 16, no i to tyle, bo 2 · 16 > 17 – daje to nam taki łańcuszek kolejnych połączeń. Kolejną niepołączoną jeszcze z niczym liczbą jest 3; z 3 krawędź powinna prowadzić do 6, z 6 do 12, a 12 kończy ten łańcuszek. Dokładając do tego kolejne łańcuszki rozpoczynające się od 5, 7 itd., otrzymujemy następujący obrazek:

To było całkiem łatwe, ale... po co w ogóle konstruowaliśmy te łańcuszki? Otóż przyjrzyjmy się temu, jak w tę konfigurację wpisują się zbiory antydwójkowe. Każdy taki zbiór A ma tę własność, że dla każdej pary m, 2m (m ∈ Z) zachodzi m ∉ A lub 2m ∉ A, czyli w A nie może znaleźć się naraz żadna para liczb połączonych krawędzią na powyższym rysunku. Zauważmy, że łańcuszki możemy rozpatrywać oddzielnie, gdyż są one całkowicie niezależne – to, jakie liczby wybierzemy do zbioru antydwójkowego z jednego łańcuszka, nie ma zupełnie wpływu na nasz wybór w pozostałych łańcuszkach.

Aby skonstruować najliczniejszy zbiór antydwójkowy A, musimy zatem z każdego łańcuszka wybrać jak najwięcej liczb. Z łańcuszków jednoelementowych (czyli takich bez krawędzi) możemy do A wziąć, oczywiście, po co najwyżej jednym elemencie. Również tylko tyle uda nam się wybrać z każdego z łańcuszków dwuelementowych. W łańcuszku trzyelementowym możemy sobie już pozwolić na wybór dwóch liczb: 3 i 12 (gdybyśmy wzięli 6, to nie moglibyśmy już wziąć ani 3, ani 12). Podobnie, wybierając co drugi element z najdłuższego łańcuszka, możemy do A dołożyć jeszcze trzy liczby.

Ostatecznie szukanym najliczniejszym zbiorem antydwójkowym jest na przykład:

A = {1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17}.

A jakie są inne najliczniejsze? I ile ich jest?

Przejdźmy teraz do pytania o liczbę wszystkich zbiorów antydwójkowych. Łatwo przekonać się, że może ich być dosyć sporo – chociażby każdy podzbiór naszego najliczniejszego zbioru A jest zbiorem antydwójkowym, a wszystkich takich podzbiorów jest już 2¹² = 4096 (!). Skoro podział na łańcuszki już raz okazał się skuteczny, to może pomoże nam także i tym razem? Spróbujmy! Przypomnijmy sobie, że każdy zbiór antydwójkowy możemy konstruować, dołączając do niego niezależnie wybrane elementy z poszczególnych łańcuszków. Przeanalizujmy więc kolejno wszystkie łańcuszki, powiedzmy, znów poczynając od najkrótszych, i przyjrzyjmy się temu, na ile sposobów można z każdego z nich wybrać pewną liczbę elementów (potencjalnie 0), tak aby nie uzyskać żadnej pary liczb połączonych krawędzią.

W każdym łańcuszku jednoelementowym mamy tylko jeden wybór: albo bierzemy jego jedyny element, albo nie – to daje każdorazowo dokładnie dwie możliwości. Dla łańcuszków dwuelementowych mamy trzy możliwości: albo nie bierzemy żadnego elementu (możemy to uczynić na jeden sposób), albo bierzemy dokładnie jeden element (dwa sposoby). Dalej sytuacja zaczyna się powoli komplikować, więc spróbujmy wymyślić jakiś bardziej systematyczny sposób postępowania. Przyjrzyjmy się przypadkowi łańcuszka trzyelementowego; jednym z wyborów, jakie musimy dla niego podjąć, jest to, czy wziąć do zbioru ostatni jego element, czy też nie. W pierwszym z tych przypadków wiemy, że środkowego elementu nie możemy już wybrać, stąd problem sprowadza się do zdecydowania, co zrobić z pozostałym jednym elementem, który to element jest w szczególności łańcuszkiem jednoelementowym. Z kolei w drugim przypadku nie mamy nałożonych żadnych dodatkowych ograniczeń na wybór pozostałych dwóch elementów łańcuszka, czyli mamy do zagospodarowania łańcuszek dwuelementowy. Ostatecznie, wynik dla trzyelementowego łańcuszka jest sumą wyników dla łańcuszków dwu- i jednoelementowego, czyli 2 + 3 = 5. Łatwo sprawdzić, że niczego nie pominęliśmy: np. dla trzyelementowego łańcuszka z naszego obrazka mamy następujące pięć możliwości wyboru elementów do zbioru antydwójkowego: ∅, {3}, {6}, {12} oraz {3, 12}.

Odtąd już pójdzie zupełnie łatwo. Wynik dla łańcuszka czteroelementowego (w naszym podziale żaden taki nie występuje) to suma wyników dla dwuelementowego (odpowiada to sytuacji, w której do zbioru wybieramy ostatni element łańcuszka) oraz trzyelementowego (co odpowiada przypadkowi przeciwnemu), czyli 3 + 5 = 8. Wreszcie dla łańcuszka pięcioelementowego mamy 5 + 8 = 13 możliwości wyboru elementów do zbioru. Łączna liczba zbiorów antydwójkowych jest iloczynem liczb możliwości wyboru dla poszczególnych łańcuszków, a zatem jest równa 13 (jeden pięcioelementowy) razy 5 (jeden trzyelementowy) razy 3² (dwa dwuelementowe) razy 2⁵ (pięć jednoelementowych), czyli 18720, czyli rzeczywiście dosyć dużo.

Na koniec dwie rzeczy: ciekawostka i zagadka. Ciekawostka: liczby oznaczające ilości sposobów wyboru zbioru antydwójkowego z łańcuszków kolejnych długości, tzn. 2, 3, 5, 8, 13,... to tzw. liczby Fibonacciego. A pojawienie się tych liczb w naszym zadaniu nie jest tylko osamotnionym przypadkiem – jakoś tak się składa, że ciąg Fibonacciego występuje w wielu miejscach, często bardzo zaskakujących, zarówno w matematyce i informatyce, jak i w biologii, muzyce itp. Więcej o ciągu Fibonacciego można dowiedzieć się np. w tym artykule w Wikipedii.

Uporządkujmy niemalejąco ciąg nominałów monet:

1, 1, 2, 5, 7, 17, 17, 35, 83, 170, 300.

Przyjrzyj się teraz zbiorom kwot, które mogą zostać wypłacone za pomocą monet z kolejnych prefiksów (tj. początkowych fragmentów) uporządkowanego ciągu.

Przyjrzyjmy się kolejnym zbiorom kwot wspomnianym we wskazówce – może uda nam się zauważyć coś ciekawego.

Za pomocą pierwszych dwóch jedynek można wypłacić wszystkie kwoty całkowite z przedziału [0,2]. Jeżeli dołączymy do tego dwójkę, to, jak łatwo sprawdzić, możemy wypłacić wszystkie kwoty z przedziału [0,4]. Dołóżmy teraz monetę o nominale 5. Czy za pomocą poprzednich monet oraz piątki możemy wypłacić wszystkie kwoty od 0 do 4+5=9? Otóż tak: kwoty mniejsze od 5 wypłacamy za pomocą wcześniejszych monet (można nimi wypłacić wszystkie kwoty z przedziału [0,4]), a dowolną kwotę k od 5 do 9 – za pomocą piątki i układu wcześniejszych monet o sumie k-5, która to wartość dla każdej z rozważanych wartości k „szczęśliwie” należy do przedziału [0,4].

Już mniej więcej widać, jak kontynuować to rozumowanie. Jeżeli za pomocą pewnych początkowych monet można wypłacić kwoty z przedziału [0,M] i kolejną monetą jest a_i ≤ M+1, to za pomocą zbioru monet powiększonego o a_i można wypłacić każdą kwotę z przedziału [0, M + a_i] – kwoty od 0 do a_i - 1 (przypomnijmy, że a_i - 1 ≤ M) tylko za pomocą wcześniejszych monet, a pozostałe z użyciem a_i i pewnych wcześniejszych monet. A co, jeżeli a_i > M + 1? Wówczas, ponieważ wszystkie kolejne po a_i monety mają nominały nie mniejsze niż nominał a_i, to na pewno za pomocą naszych monet nie da się wypłacić kwoty M+1 (i jest to wówczas najmniejsza taka kwota).

Stosując opisaną regułę do kolejnych monet z zestawu, otrzymujemy: przedział [0,9] i moneta 7 dają przedział [0,16], który wraz z monetą 17 daje przedział [0,33], który po dołączeniu kolejnej siedemnastki daje [0,50], co wraz z monetą 35 daje [0,85], do czego, dokładając monetę 83, otrzymujemy [0,168], co wraz z 170 daje... no właśnie, w tym miejscu trzeba przerwać naszą wyliczankę z wnioskiem, że najmniejszą kwotą, jakiej nie da się wypłacić, jest 168 + 1 = 169.

Na koniec pytanie kontrolne: jakie byłoby rozwiązanie zadania, gdybyśmy z powyższą „wyliczanką” doszli do końca ciągu nominałów monet?

Wystarczy zliczyć liczby palindromiczne w przedziałach [1, 84 633 902] i [1, 285 923], a następnie obliczyć różnicę wyników. A liczby w każdym z tych przedziałów warto sprytnie podzielić na grupy.

Wykonajmy to, co sugeruje wskazówka. Zacznijmy zliczenia liczb palindromicznych w przedziale [1, 84 633 902]. Klucz do rozwiązania zadania stanowi sprytne pogrupowanie wszystkich liczb całkowitych dodatnich nieprzekraczających 84 633 902, na przykład na następujące kategorie:

[1-9]	[1-7]*******
[1-9]*	8[0-3]******
[1-9]**	84[0-5]*****
[1-9]***	846[0-2]****
[1-9]****	8463[0-2]***
[1-9]*****	84633[0-8]**
[1-9]******	8463390[0-2]

Znaczenie kategorii wyjaśnijmy na przykładzie: 846[0-2]**** oznacza wszystkie liczby całkowite dodatnie, których zapis dziesiętny zaczyna się od cyfr 846, po czym następuje jakakolwiek z cyfr 0, 1, 2, a dalej jeszcze cztery dowolne cyfry. Zwróćmy uwagę na to, że wśród kategorii brakuje ośmiocyfrowej zakończonej pojedynczą gwiazdką. Dodajmy także, że pierwsze siedem kategorii (wraz z zerem) można by łącznie opisać jednym oznaczeniem *******, ale wówczas stracilibyśmy tę miłą własność naszych kategorii, że każda z nich zaczyna się od niezerowej cyfry. Spróbujemy teraz zliczyć liczby palindromiczne poszczególnych kategorii.

Pierwsze siedem kategorii odpowiada liczbom jedno-, dwu-, ..., aż do siedmiocyfrowych. Wszystkie liczby jednocyfrowe są palindromiczne, natomiast wśród liczb dwucyfrowych tylko takie postaci AA spełniają ten warunek – łącznie mamy 2 · 9 = 18 takich liczb. Wśród liczb trzy- i czterocyfrowych dowolny układ pierwszych dwóch cyfr niezaczynający się od zera wyznacza jednoznacznie liczbę palindromiczną (odpowiednio ABA i ABBA), co razem daje 2 · 9 · 10 = 180 liczb palindromicznych. Podobnie, wśród liczb pięcio- i sześciocyfrowych mamy łącznie 2 · 9 · 10² = 1 800 liczb palindromicznych, a wśród siedmiocyfrowych – 9 000 tychże. Naliczyliśmy już razem 10 998 liczb palindromicznych.

Kolejne kategorie wyglądają nieco ciekawiej. W pierwszych czterech mamy zawsze kilka mniej lub bardziej precyzyjnie określonych cyfr, po których następuje co najmniej połowa liczby wypełniona gwiazdkami. To oznacza, że możemy te początkowe cyfry przepisać na koniec reprezentacji (oczywiście w odwróconej kolejności), w wyniku czego w środku pozostanie pewna parzysta liczba gwiazdek g reprezentująca dowolną g-cyfrową liczbę palindromiczną (potencjalnie zaczynającą się od zera), których to liczb jest 10^g/2. Dzięki temu spostrzeżeniu możemy już całkiem łatwo porachować liczby palindromiczne tych kategorii: [1-7]******[1-7] daje 7 · 10³ = 7 000 liczb palindromicznych, 8[0-3]****[0-3]8 – 400 liczb, 84[0-5]**[0-5]48 – 60 liczb, a 846[0-2][0-2]648 – 3 liczby palindromiczne, razem 7 463.

W ostatnich trzech kategoriach mamy jednoznacznie wyznaczoną pierwszą połowę liczby; musimy jedynie sprawdzić, czy możemy do niej dopasować drugą – jeśli tak, to do wyniku dochodzi nam dokładnie jedna liczba palindromiczna. Widzimy, że jest to możliwe jedynie w przypadku kategorii 84633[0-8]**, w którym otrzymujemy liczbę palindromiczną 84 633 648.

Łącznie naliczyliśmy 10 998 + 7 463 + 1 = 18 462 liczby palindromiczne nieprzekraczające naszej górnej granicy. Podobnie można sprawdzić, że w przedziale [1, 285 923] są, ni mniej ni więcej, jak 1 284 liczby palindromiczne, co pozwala wyznaczyć liczbę liczb palindromicznych w oryginalnym przedziale z zadania: 18 462 – 1 284 = 17 178.

Zauważmy na koniec, że podobnych zagadek moglibyśmy wymyślić dużo więcej. Dla danej klasy zliczanych liczb wystarczyłoby wymyślić metodę sprawdzania, ile liczb danej kategorii należy do danej klasy. Poniżej trzy przykłady tego typu zadań, z których każde dotyczy wyłącznie liczb parzystej długości, czyli składających się z dwóch takiej samej długości połówek. Pozostawiamy je do samodzielnego rozwiązania.

Jak sprawdzić, ile liczb danej kategorii (np. 84[0-5]*****) jest:

1. liczbami podwójnymi, które składają się z dwóch kolejno zapisanych takich samych fragmentów, np. 345 345?
2. (dla miłośników matematyki) liczbami permutacyjnymi, których pierwsza połówka zawiera wyłącznie różne cyfry, a druga – permutację cyfr z pierwszej połówki, np. 345 453?
3. (dla miłośników informatyki) liczbami o równych sumach, w których sumy cyfr z obydwu połówek są równe, np. 235 424?

W przypadku naszej przykładowej kategorii poprawnymi odpowiedziami są: (A) 60, (B) 840, (C) 34 661.