Zadania 21-25

Data ostatniej modyfikacji:
2009-07-4

Symbole matematyczne można wpisywać w notacji kalkulatorowej lub tex'owej. Można korzystać ze ściągi zamieszczonej na  górze strony na pasku poziomego MENU. Każdy wzór należy poprzedzić napisem tex i zakończyć napisem /tex umieszczonymi w nawiasach kwadratowych.

 

ZADANIE 21 (10 VIII 2008) 
jury (niezweryfikowany), niedziela, 10/08/2008 - 16:26

Małgosia ma 9-cyfrowy numer telefonu komórkowego. Jaś chce wydostać od niej ten numer, ale musi zgadywać. Małgosia zgadza się odpowiadać, czy podany przez Jasia numer jest za mały, za duży, czy prawidłowy. Jaś ma tylko 20 pytań do dyspozycji. Jaka jest najmniejsza liczba pytań, w jakiej na pewno może odgadnąć numer Małgosi? 

 

ROZWIĄZANIE ZADANIA 21

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 109-elementowy zbiór S = {0, 1, 2, ..., 109-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.

UWAGA

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

NOWE ROZWIĄZANIE ZADANIA 21

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 2n 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 220= (210)2< (104)2= 108= 100 000 000. Jednak 29 pytań to też za mało, bo 229= 536 870 912. Natomiast 30 pytań już wystarczy, bo 230> 900 000 000.

ZADANIE 22 (23 VIII 2008)

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

ROZWIĄZANIE ZADANIA 22

W zapisie liczby 106 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 96-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.

PROSTSZE ROZWIĄZANIE ZADANIA 22

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.

ZADANIE 23 (30 VIII 2008)

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?

ROZWIĄZANIE ZADANIA 23

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

INNE(?) ROZWIĄZANIE ZADANIA 23

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, 298},
{0, 299, 2·299, 3·299, ...}.

ZADANIE 24 (31 VIII 2008)

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

ROZWIĄZANIE ZADANIA 24

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ć.

ZADANIE 25 (9 IX 2008)

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?

ROZWIĄZANIE ZADANIA 25

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.

UWAGA

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ę.

Dodatkowy warunek

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ł:)

To jest jasne

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ść.

Uzasadnienie jest trudne

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 a1 < a2 < ... < an. Szukamy permutacji indeksów n1, n2, ..., nn 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:
n1= k+1, n2= 1, n3= k+2, n4= 2, n5= k+3, n6= 3, n7= k+4, ...  nn-2= k-1, nn-1= k+k, nn= 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:

  • {n1, nn} = {k, k+1}
  • jeśli ni > k, to ni+1k
  • jeśli ni ≤ k, to ni+1 > k.

To są (chyba) wszystkie najlepsze permutacje.

 

Przypadek n = 2k+1 oraz |ak - ak+1| < |ak+1 - ak+2|
PRZYKŁAD
Chodzimy zgodnie z permutacją indeksów:
n1= k+1, n2= k+2, n3= 1, n4= k+3, n5= 2, n6= k+4, n7= 3, n8= k+5, ..., nn-2= k-1, nn-1= k+k+1, nn= 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 |ak - ak+1| ≥ |ak+1 - ak+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).

Powrót na górę strony