Zad. 1. Pewien algorytm przyjmuje na wejściu jedną dodatnią liczbę całkowitą n, a na wyjściu zwraca dwie liczby całkowite, a(n) i b(n), gdzie a(n) to liczba bitów w zapisie liczby n w systemie dwójkowym, a b(n) to suma cyfr liczby n w systemie dziesiętnym. Podaj najmniejszą liczbę całkowitą, dla której:
a) a(n)>b(n),
b) b(b(n)) = 13.
Zad. 2. Dla algorytmu z poprzedniego zadania, ile wynosi:
a) a(1) + a(2) + a(3) + ... + a(100)?
b) b(1) + b(2) + b(3) + ... + b(100)?
Zad. 3. W grze "Czekolada" prostokątna tabliczka czekolady jest podzielona na kwadratowe kostki. Gracze na przemian zjadają (zamalowują swoim kolorem) jedną lub więcej kostek tworzących prostokąt. Gracz otwierający musi zjeść kawałek zawierający kostkę z prawego dolnego rogu czekolady. Kolejne zjadane kawałki muszą przylegać do wcześniej zjedzonych. W lewym górnym rogu znajduje się gorzka kostka. Gracz, który musi ją zjeść, przegrywa. Który gracz ma strategię wygrywająca w grze na tabliczce o wymiarach 4 kostki × 4 kostki? Opisz tę strategię.
Komplet 3 pktów zdobyli:
- Krystyna Lisiowska, redaktor z Warszawy,
- Szymon Meyer, analityk danych z Dziewkowic,
- Kasper Przenzak, analityk ryzyka z Krakowa,
- Marzena Wąsiewicz, nauczyciel matematyki z Kajetan.
Gratulujemy!
Zad. 1. a) Wartości a(n) dla coraz większych n nie maleją i: a(1)=1, a(3)=2, a(7)=3, a(9)=4, więc szukana liczba nie może być jednocyfrowa, bo wówczas b(n) = n. Łatwo sprawdzić, że n = 10 spełnia warunki zadania.
Zad. 1. b) Dla m równego kolejno: 0, 1, 2, ..., 9; 10, 11, 12, ..., 19; 20, 21, 22, ..., 29; ...; 90, 91, 92, ..., 99 wartości b(m) cyklicznie 9 razy rosną i następnie maleją, b(n) musi być zatem co najmniej 49, a najmniejsze takie n to 499999.
Zad. 2. a) Liczba 1 jest jednobitowa, 2 i 3 - dwubitowe, 4, 5, 6 i 7 - trzybitowe, 8, 9, ..., 15 - czterobitowe, 16, 17, ..., 31 - pięciobitowe, 32, 33, ..., 63 - sześciobitowe, a 64, 65, ..., 100 - siedmiobitowe. Szukamy zatem sumy 1+2·2+4·3+8·4+16·5+32·6+37·7 = 580.
Zad. 2. b) Możemy osobno dodać cyfry liczby 100 oraz 10 razy każdą cyfrę dziesiątek (od 1 do 9) i 10 razy każdą cyfrę jedności (od 0 do 9). Szukamy zatem sumy 1+2·10·45 = 901.
Zad. 3. Strategię wygrywającą ma I gracz. W I ruchu zjada kwadrat 3x3, a dalsze ruchy wykonuje symetrycznie do ruchów przeciwnika (symetria względem przekątnej oryginalnej tabliczki przechodzącej przez gorzką kostkę).
