Zadania 21-25

Trzeba zastosować algorytm wyszukiwania binarnego (czyli tzw. podziału połówkowego). Wiedząc, że szukany element o wartości x znajduje się w uporządkowanym zbiorze S, porównujemy go ze środkowym elementem S (lub średnią dwóch środkowych) i w zależności od otrzymanej nierówności kontynuujemy przeszukiwanie w przedziale o połowę mniej licznym (ściślej mówiąc: jeśli zbiór ma 2n lub 2n+1 elementów, to w następnym kroku rozpatrujemy zbiór n-elementowy).

W przypadku naszego zadania mamy 10⁹-elementowy zbiór S = {0, 1, 2, ..., 10⁹-1}. Po kolejnych zapytaniach Jasia liczba elementów zbioru, w którym znajduje się szukany numer, maleje dwukrotnie. Zakładając, że Jaś ma wyjątkowego pecha i dopiero na samym końcu trafia w wybrany numer, potrzebuje do tego 29 pytań, więc po 20 pytaniach mimo optymalnej strategii może nie odgadnąć numeru Małgosi.

Rozumowanie przedstawione powyżej jest z grubsza poprawne, ale ostateczna odpowiedź jest błędna. Czekamy na jej poprawienie.

Do znalezienia właściwego numeru x w uporządkowanym zbiorze dwuelementowym {a, b} wystarczy jedno pytanie: "Czy x<b?". Używając algorytmu połówkowego podziału opisanego wyżej przez Piotra, zadając n pytań, możemy znaleźć x w zbiorze o 2ⁿ elementach (dowód, że jest to strategia optymalna nie jest prosty, więc zakładam, że nie trzeba tego uzasadniać, ale można z tej własności skorzystać).

Ponieważ Małgosia ma numer 9-cyfrowy, jest on liczbą naturalną z przedziału <100 000 000, 999 999 999>. Ten zbiór ma 900 000 000 elementów. Rzeczywiście 20 pytań nie wystarczy do znalezienia w nim liczby x, bo 2²⁰= (2¹⁰)²< (10⁴)²= 10⁸= 100 000 000. Jednak 29 pytań to też za mało, bo 2²⁹= 536 870 912. Natomiast 30 pytań już wystarczy, bo 2³⁰> 900 000 000.

Ile razy cyfra 1 pojawia się wśród liczb naturalnych od jeden do miliona?

W zapisie liczby 10⁶ jest jedna jedynka. Dalej rozpatrzmy wszystkie liczby sześciocyfrowe. W tych liczbach jedynka moze wystąpić od jednego do sześciu razy. Jeśli cyfra 1 występuje w liczbie sześciocyfrowej k razy, to te k jedynek można rozmieścić na 6 pozycjach na [tex]{{6}\choose{k}}[/tex] sposobów. Pozostałe pozycje zapełniamy dowolnie, cyframi ze zbioru {0, 2, ..., 9}, co możemy zrobić na 9^6-k sposobów, przy czym zapisy rozpoczynające się pewną liczbą zer utożsamiamy z liczbą powstałą po ich odrzuceniu (np. 000134 to 134). Dzięki temu nie musimy już rozpatrywać liczb o mniejszej liczbie cyfr niż 6. Wobec tego cyfra 1 w liczbach od jeden do miliona występuje: [tex] 1+1\cdot {{6}\choose{1}}\cdot 9^5+2\cdot {{6}\choose{2}}\cdot 9^4+3\cdot {{6}\choose{3}}\cdot 9^3+4\cdot {{6}\choose{4}}\cdot 9^2+5\cdot{{6}\choose{5}}\cdot 9^1+6\cdot{{6}\choose{6}}\cdot 9^0 [/tex] = 600001 razy.

Wśród liczb od 1 do 1000000 jedynka na miejscu jedności pojawia się co dziesiątą liczbę, czyli 100000 razy, na miejscu dziesiątek co setną liczbę, ale za to po 10 razy za każdym razem, czyli w sumie 100000 itd. przez kolejnych 6 miejsc dziesiętnych. Na siódmym miejscu pojawia się tylko raz. Zatem wszystkich wystąpień jedynki jest 6·100000+1 = 600001.

Czy istnieje 100 podzbiorów liczb naturalnych (niekoniecznie rozłącznych) takich, że każdą liczbę naturalną można jednoznacznie przedstawić w postaci sumy 100 liczb, po jednej z każdego z tych zbiorów?

Taką własność (co łatwo sprawdzić) mają np. zbiory:
{0, 1, 2, ..., 9},
{0, 10, 20, ..., 90},
{0, 100, 200, ..., 900},
...,
{0, 10⁹⁸, 2·10⁹⁸, ..., 9·10⁹⁸},
{0, 10⁹⁹, 2·10⁹⁹, 3·10⁹⁹, ...},
z których ostatni jest nieskończony.

Można też zamiast "dziesiętnie" konstruować potrzebne zbiory np. "dwójkowo". Dobrymi przykładami zbiorów są więc też:
{0, 1},
{0, 2},
{0, 4},
...,
{0, 2⁹⁸},
{0, 2⁹⁹, 2·2⁹⁹, 3·2⁹⁹, ...}.

Ile razy wśród liczb od jeden do 10 bilionów występuje liczba 5?

Liczba 5 w tym zakresie występuje tylko raz, bo każda liczba jest tylko jedna.  Liczby składają się z cyfr. Cyfry występują w liczbach wiele razy, ale liczba nie może się powtórzyć.

Chcąc wbić po gwoździu w kilkadziesiąt słupów przy prostej drodze pokonując najmniejszą trasę, zaczynamy od pierwszego, a kończymy na ostatnim. Jak to zrobić, aby przejść najdłuższą trasę, oczywiście poruszając się tylko między słupami, w których nie ma jeszcze gwoździ?

Zaczynamy od ostatniego, potem zaliczamy pierwszy, następnie przedostatni, potem drugi, dalej trzeci od końca i trzeci od początku itd. aż dojdziemy do środka.

osóbka :P podała jedną z możliwych odpowiedzi do zadania, ale bez podania rozwiązania, tzn. bez uzasadnienia, dlaczego taki sposób miałby dawać najdłuższą możliwą drogę. Czekamy na takie uzasadnienia lub przykłady innych algorytmów obchodzenia słupów z uzasadnieniem, że pokonujemy wtedy najdłuższą drogę.

Należałoby uzupełnić treść zadania np. o warunek, że nie możemy mijać tego samego słupa więcej niż raz pomiędzy jednym wbiciem gwoździa a następnym... Obecna treść zadania pozwala na to i zadanie na maksimum nie ma sensu, gdyż w celu osiągnięcia najdłuższej drogi można by chodzić między słupami aż do wyczerpania sił:)

Moim zdaniem żadne dodatkowe warunki nie są potrzebne. Jasne jest, że "poruszając się tylko między słupami, w których nie ma jeszcze gwoździ" musimy wbić gwóźdź w każdy docelowy słup, do którego w danym momencie idziemy. Zatem z każdym przejściem liczba pustych słupów maleje i nie da się chodzić między nimi w nieskończoność.

Odpowiedź osóbki :P jest poprawna, choć jej formalne uzasadnienie jest dość trudne. Nie znam krótkiego sposobu. Oto kilka impresji na ten temat.

Niech a₁ < a₂ < ... < a_n. Szukamy permutacji indeksów n₁, n₂, ..., n_n takiej, że suma [tex]\sum_{i=1}^{n-1} |a_{n_i} - a_{n_{i+1}}|[/tex]  jest największa z możliwych.

UWAGA
Dla dowolnej permutacji mamy:

[tex]|a_{n_n} - a_{n_1}| + \sum_{i=1}^{n-1} |a_{n_i} - a_{n_{i+1}}| \leq \sum_{i=1}^{n-1} |a_i - a_{i+1}| \cdot 2 \cdot \min(n-i, i) [/tex].

PSEUDODOWÓD UWAGI
Nad odcinkiem [tex]a_ia_{i+1}[/tex] bez zatrzymywania przechodzimy w lewo lub w prawo.

• w lewo przechodzimy nie więcej razy niż jest miejsc "lądowań", czyli i,
• w lewo przechodzimy nie więcej razy niż jest miejsc "startów", czyli n-i,
• w prawo przechodzimy nie więcej razy niż jest miejsc "lądowań", czyli n-i,
• w prawo przechodzimy nie więcej razy niż jest miejsc "startów", czyli i.

c.k.d.

Przypadek n = 2k
PRZYKŁAD
Chodzimy zgodnie z permutacją indeksów:
n₁= k+1, n₂= 1, n₃= k+2, n₄= 2, n₅= k+3, n₆= 3, n₇= k+4, ...  n_n-2= k-1, n_n-1= k+k, n_n= k.
Wtedy łączna długość przejść jest równa:

[tex]\sum_{i=1}^{n-1} |a_i - a_{i+1}| \cdot 2 \cdot \min(n-i, i) - |a_k - a_{k+1}|[/tex].
Taka sama suma wychodzi dla dowolnej permutacji indeksów spełniającej warunki:

• {n₁, n_n} = {k, k+1}
• jeśli n_i > k, to n_i+1≤ k
• jeśli n_i ≤ k, to n_i+1 > k.

To są (chyba) wszystkie najlepsze permutacje.

Przypadek n = 2k+1 oraz |a_k - a_k+1| < |a_k+1 - a_k+2|
PRZYKŁAD
Chodzimy zgodnie z permutacją indeksów:
n₁= k+1, n₂= k+2, n₃= 1, n₄= k+3, n₅= 2, n₆= k+4, n₇= 3, n₈= k+5, ..., n_n-2= k-1, n_n-1= k+k+1, n_n= k. Wtedy łączna długość przejść jest równa:
[tex]\sum_{i=1}^{n-1} |a_i - a_{i+1}| \cdot 2 \cdot \min(n-i, i) - |a_k - a_{k+1}|[/tex].

Przypadek n = 2k+1 oraz |a_k - a_k+1| ≥ |a_k+1 - a_k+2|
rozpatruje się analogicznie.

Więcej uwag na ten temat jest w tekście Szczególne przypadki komiwojażera w dziale MAT-ŚWIAT (Wzorzyste wzory).