SP w Zielonkach-Parceli

Zanurzeni w: Języku, Kulturze, Sporcie...

Przygotowanie do konkursów informatycznych

Zaczynamy

Zadanie 1. Kolorowe pola

Na kartce narysowano rząd 6 pól. Każde pole ma być pokolorowane na czerwono (C) albo niebiesko (N).
Nie wolno, żeby trzy kolejne pola miały ten sam kolor.

  1. Przykład kolorowania: C C N C N N – czy jest poprawne?
  2. Ile jest możliwych kolorowań, w których żadne trzy kolejne pola nie są tego samego koloru?
Pokaż odpowiedź

a) Tak, to kolorowanie jest poprawne. Nigdzie nie pojawiają się trzy kolejne pola w tym samym kolorze: mamy co najwyżej dwie litery C obok siebie i dwie litery N obok siebie.

b) Poprawnych kolorowań jest 26.

Wyjaśnienie:
Dla każdego z 6 pól mamy teoretycznie 2 możliwości (C lub N), co daje 26 = 64 kolorowania, ale część z nich odrzucamy, bo zawierają trzy te same kolory obok siebie (np. C C C …).
Liczbę poprawnych ustawień można policzyć systematycznie (wypisując je lub robiąc małą tabelkę/algorytm, który nie dopuszcza trzech takich samych kolorów z rzędu). Po takim policzeniu wychodzi dokładnie 26 różnych poprawnych kolorowań.

Zadanie 2. Ciasteczka w pudełkach

Mamy 3 pudełka: A, B, C.
Na początku:
– w pudełku A jest 5 ciasteczek,
– w pudełku B są 2 ciasteczka,
– w pudełku C jest 0 ciasteczek.

Wykonujemy po kolei operacje:

  1. Z pudełka A przekładamy 2 ciasteczka do B.
  2. Z pudełka B przekładamy 3 ciasteczka do C.
  3. Z pudełka C przekładamy 1 ciasteczko do A.

Ile ciasteczek jest na końcu w każdym pudełku?

Pokaż odpowiedź

Odpowiedź:
Pudełko A: 4 ciasteczka
Pudełko B: 1 ciasteczko
Pudełko C: 2 ciasteczka

Wyjaśnienie krok po kroku:
Start: A = 5, B = 2, C = 0.

1) Z A do B przekładamy 2 ciasteczka:
A = 5 − 2 = 3, B = 2 + 2 = 4, C = 0.

2) Z B do C przekładamy 3 ciasteczka:
A = 3, B = 4 − 3 = 1, C = 0 + 3 = 3.

3) Z C do A przekładamy 1 ciasteczko:
A = 3 + 1 = 4, B = 1, C = 3 − 1 = 2.

Ostatecznie: A = 4, B = 1, C = 2.

Zadanie 3. Wieża z klocków

Budujemy wieżę z klocków:
– czerwone klocki mają wysokość 2 cm,
– zielone klocki mają wysokość 3 cm.

Wieża ma mieć dokładnie 20 cm wysokości.
Ile różnych wież możemy zbudować, jeśli kolejność klocków ma znaczenie?
(Przykład: wieża z 10 czerwonych klocków też ma 20 cm i liczy się jako jedna z możliwości).

Pokaż odpowiedź

Odpowiedź: Możemy zbudować 114 różnych wież.

Wyjaśnienie:
Niech będzie:
– a – liczba czerwonych klocków (2 cm),
– b – liczba zielonych klocków (3 cm).

Wysokość wieży: 2a + 3b = 20.
Szukamy wszystkich par (a, b) liczb naturalnych spełniających to równanie:
– b = 6 ⇒ 2a + 3·6 = 20 ⇒ 2a = 2 ⇒ a = 1 (1 czerwony, 6 zielonych),
– b = 4 ⇒ 2a + 12 = 20 ⇒ 2a = 8 ⇒ a = 4,
– b = 2 ⇒ 2a + 6 = 20 ⇒ 2a = 14 ⇒ a = 7,
– b = 0 ⇒ 2a = 20 ⇒ a = 10.

Dla każdej pary (a, b) liczymy liczbę różnych kolejności ułożenia tych klocków (permutacje z powtórzeniami):
– (a, b) = (1, 6): liczba wież = (1+6)! / (1!·6!) = 7
– (a, b) = (4, 4): liczba wież = 8! / (4!·4!) = 70
– (a, b) = (7, 2): liczba wież = 9! / (7!·2!) = 36
– (a, b) = (10, 0): liczba wież = 10! / (10!·0!) = 1

Razem: 7 + 70 + 36 + 1 = 114.

Trochę trudniej

Zadanie 4. Dziwny kalkulator

Na ekranie dziwnego kalkulatora początkowo widnieje liczba 1.
Można nacisnąć tylko dwa przyciski:

  • A – pomnóż aktualną liczbę przez 2,
  • B – dodaj do aktualnej liczby 3.

Przykład: z 1 po naciśnięciu A otrzymujemy 2, z 2 po B otrzymujemy 5, itd.

  1. Podaj jeden możliwy ciąg przycisków, który zmieni 1 na 19.
  2. Czy da się uzyskać liczbę 20? Uzasadnij krótko „tak/nie”.
Pokaż odpowiedź

a) Jeden z możliwych ciągów: B A A B.
Przebieg obliczeń:
1 → (B) → 1 + 3 = 4
4 → (A) → 4 · 2 = 8
8 → (A) → 8 · 2 = 16
16 → (B) → 16 + 3 = 19.

b) Tak, liczbę 20 też da się uzyskać, np. ciąg A B A A:
1 → (A) → 2
2 → (B) → 5
5 → (A) → 10
10 → (A) → 20.

Wyjaśnienie:
Obie operacje (×2 i +3) zwiększają liczbę, więc możemy „szukać” ścieżki od 1 w górę, eksperymentując z sekwencjami A i B. Przykładowe udane sekwencje wyżej pokazują, że 19 i 20 są osiągalne.

Zadanie 5. Szyfr literowy

Litery A, B, C, D kodujemy następująco:
A → 1, B → 2, C → 4, D → 7.
Kod wyrazu to suma kodów jego liter.
Przykład: kod słowa „BAD” to 2 + 1 + 7 = 10.

  1. Jaki kod ma słowo „CAB”?
  2. Znajdź inne słowo (z liter A, B, C, D), które ma taki sam kod jak „CAB”.
Pokaż odpowiedź

a) „CAB” ma kod: C (4) + A (1) + B (2) = 7.

b) Taki sam kod ma słowo „D”, bo D ma kod 7.

Wyjaśnienie:
Liczymy sumę kodów liter w słowie „CAB”: 4 + 1 + 2 = 7. Następnie szukamy innych kombinacji liter, które też dają sumę 7. Od razu widzimy, że pojedyncza litera D ma kod 7, więc słowo „D” spełnia warunek.

Zadanie 6. Liczby w tabeli

W tabeli 3×3 w każdym polu ma stać liczba naturalna (0, 1, 2, 3, …).
Suma w każdym wierszu ma wynosić 10, a suma w każdej kolumnie – też 10.

  1. Zapropnuj jeden możliwy układ liczb w takiej tabeli.
  2. Czy jest możliwe, aby wszystkie liczby były różne? Uzasadnij.
Pokaż odpowiedź

1) Przykładowa tabela spełniająca warunki:

4   3   3
3   4   3
3   3   4

Każdy wiersz ma sumę 10, każda kolumna ma sumę 10.

2) Nie, nie da się tak dobrać liczb, żeby wszystkie dziewięć było różne.

Wyjaśnienie:
Suma wszystkich liczb w tabeli to suma wszystkich wierszy: 10 + 10 + 10 = 30.
Gdyby wszystkie liczby były różne i nieujemne, to najmniejszy możliwy zestaw dziewięciu różnych liczb naturalnych to:
0, 1, 2, 3, 4, 5, 6, 7, 8
Ich suma wynosi 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36, czyli jest większa niż 30.
To oznacza, że przy sumie równej 30 nie da się mieć 9 różnych liczb naturalnych w tabeli – co najmniej dwie liczby muszą się powtórzyć.

Zwiększamy trudność

Zadanie 7. Pętle i reszty

Rozważ program: 

1. Ustaw x = 0.
2. Powtórz 10 razy:
   - zwiększ x o 5,
   - jeśli x jest podzielne przez 4, to zmniejsz x o 3.
3. Wypisz wartość x.

Jaka wartość zostanie wypisana po wykonaniu programu?

Pokaż odpowiedź

Odpowiedź: Po zakończeniu programu x = 41.

Wyjaśnienie krok po kroku (kolejne iteracje):
Start: x = 0.

1) +5 ⇒ 5 (niepodzielne przez 4)
2) +5 ⇒ 10 (niepodzielne przez 4)
3) +5 ⇒ 15 (niepodzielne przez 4)
4) +5 ⇒ 20, 20 jest podzielne przez 4 ⇒ 20 − 3 = 17
5) +5 ⇒ 22 (niepodzielne przez 4)
6) +5 ⇒ 27 (niepodzielne przez 4)
7) +5 ⇒ 32, 32 jest podzielne przez 4 ⇒ 32 − 3 = 29
8) +5 ⇒ 34 (niepodzielne przez 4)
9) +5 ⇒ 39 (niepodzielne przez 4)
10) +5 ⇒ 44, 44 jest podzielne przez 4 ⇒ 44 − 3 = 41

Ostatecznie wypisujemy 41.

Zadanie 8. Sortowanie trzech liczb

Mamy trzy liczby całkowite a, b, c. Program wygląda tak: 

1. Jeśli a > b, zamień miejscami a i b.
2. Jeśli b > c, zamień miejscami b i c.
3. Jeśli a > b, zamień miejscami a i b.
4. Wypisz a, b, c.
  1. Co wypisze program dla a = 7, b = 2, c = 5?
  2. Czy ten program zawsze wypisuje liczby a, b, c w kolejności niemalejącej (od najmniejszej do największej)?
Pokaż odpowiedź

a)
Start: a = 7, b = 2, c = 5.

1) a > b (7 > 2), więc zamiana ⇒ a = 2, b = 7, c = 5
2) b > c (7 > 5), więc zamiana ⇒ a = 2, b = 5, c = 7
3) a > b? 2 > 5 – nie, więc bez zmian.

Program wypisze: 2, 5, 7.

b) Tak, program zawsze ustawia liczby w kolejności od najmniejszej do największej.

Wyjaśnienie:
– Po kroku 1 wiemy, że a ≤ b (jeśli było inaczej, zostały zamienione).
– Po kroku 2 wiemy, że b ≤ c (jeśli było inaczej, zostały zamienione).
Może się jednak zdarzyć, że po zamianie b i c w kroku 2 należałoby jeszcze raz poprawić relację między a i b. Dlatego jest krok 3, który znów gwarantuje, że a ≤ b.
Mając jednocześnie a ≤ b i b ≤ c, otrzymujemy a ≤ b ≤ c, czyli liczby są posortowane niemalejąco.

Zadanie 9. Ścieżka robota na planszy

Robot stoi na planszy w punkcie (0,0). Wykonuje instrukcje zapisane jako ciąg liter:

  • P – idź o 1 w prawo (zwiększ x),
  • L – idź o 1 w lewo (zmniejsz x),
  • G – idź o 1 w górę (zwiększ y),
  • D – idź o 1 w dół (zmniejsz y).

Przykład: dla ciągu „PGD” robot wykona ruch w prawo, w górę, w dół i skończy w punkcie (1,0).

Weź ciąg: PPGGLLGDPPG

  1. W jakim punkcie (x, y) robot zakończy ruch?
  2. Czy da się tak zmienić dokładnie jedną literę w tym ciągu, aby robot wrócił do punktu (0,0)?
Pokaż odpowiedź

a) Robot kończy w punkcie (2, 3).

Wyjaśnienie:
Liczymy krok po kroku (x, y):
start: (0, 0)
P → (1, 0)
P → (2, 0)
G → (2, 1)
G → (2, 2)
L → (1, 2)
L → (0, 2)
G → (0, 3)
D → (0, 2)
P → (1, 2)
P → (2, 2)
G → (2, 3)

b) Nie, nie da się zmienić tylko jednej litery tak, aby robot wrócił do (0,0).

Wyjaśnienie:
Obecne przesunięcie robota względem startu to wektor (2, 3).
Zmiana jednej litery oznacza, że jeden krok w pewnym kierunku (np. P = (1,0)) zastępujemy innym krokiem (np. L = (−1,0) lub G = (0,1) itd.).
Różnica między dwoma ruchami może mieć współrzędne tylko z zakresu od −2 do 2 (bo odejmujemy liczby z {−1, 0, 1}).
Żeby wrócić do (0,0), musielibyśmy „zlikwidować” przesunięcie (2, 3), czyli zmienić je o (−2, −3). Część pionowa (−3) jest niemożliwa do uzyskania pojedynczą zamianą (maksymalnie |zmiana y| = 2), więc jedna zmiana litery nie wystarczy.

Zadanie 10. Skreślanie liczb

Na tablicy zapisano kolejne liczby od 1 do 20.
Kasia skreśla wszystkie liczby, które są wielokrotnością 2 lub wielokrotnością 3 (albo jednym i drugim).
Ile liczb nie zostanie skreślonych?

Pokaż odpowiedź

Odpowiedź: Nie zostanie skreślonych 7 liczb: 1, 5, 7, 11, 13, 17, 19.

Wyjaśnienie:
Skreślamy liczby, które dzielą się przez 2 lub przez 3:
– wielokrotności 2: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
– wielokrotności 3: 3, 6, 9, 12, 15, 18

Zostają te, które nie dzielą się ani przez 2, ani przez 3:
1, 5, 7, 11, 13, 17, 19 – razem 7 liczb.

Zadanie 11. Dwucyfrowe kody

Mamy cyfry od 1 do 9. Z tych cyfr tworzymy dwucyfrowe liczby, w których cyfry nie mogą się powtarzać.
Ile takich liczb jest większych niż 50?

Pokaż odpowiedź

Odpowiedź: Jest 40 takich liczb.

Wyjaśnienie:
Dwucyfrowa liczba ma postać XY, gdzie X – cyfra dziesiątek, Y – cyfra jedności.
– liczba ma być > 50, więc X może być: 5, 6, 7, 8 lub 9 (5 możliwości),
– Y może być dowolną cyfrą z 1..9 z wyjątkiem X (żeby się nie powtarzały), czyli mamy 8 możliwości dla Y.

Łącznie: 5 (wyborów X) · 8 (wyborów Y) = 40 liczb.

Zadanie 12. Prosty program z pętlą

Rozważ program: 

Ustaw n = 13.
Powtarzaj dopóki n > 0:
  jeśli n jest parzyste, to n := n / 2
  w przeciwnym razie n := n - 1
Na końcu wypisz liczbę kroków, które wykonano.

Ile kroków wykona program, startując od n = 13?

Pokaż odpowiedź

Odpowiedź: Program wykona 6 kroków.

Wyjaśnienie – śledzimy krok po kroku:
Start: n = 13, kroki = 0

1) n = 13 (nieparzysta) ⇒ n = 12, kroki = 1
2) n = 12 (parzysta) ⇒ n = 6, kroki = 2
3) n = 6 (parzysta) ⇒ n = 3, kroki = 3
4) n = 3 (nieparzysta) ⇒ n = 2, kroki = 4
5) n = 2 (parzysta) ⇒ n = 1, kroki = 5
6) n = 1 (nieparzysta) ⇒ n = 0, kroki = 6

Gdy n = 0, pętla się kończy. Wykonano dokładnie 6 przejść pętli.

Zadanie 13. Ścieżki w kratkach

Mamy planszę w kształcie kwadratu 4×4 pól (4 w wierszu i 4 w kolumnie).
Zaczynamy w lewej górnej kratce, a chcemy dojść do prawej dolnej kratki.
Możemy wykonywać tylko ruchy:

  • w prawo (P),
  • w dół (D).

Ile różnych ścieżek prowadzi z lewego górnego pola do prawego dolnego, jeśli zawsze idziemy tylko w prawo lub w dół?

Pokaż odpowiedź

Odpowiedź: Jest 20 różnych ścieżek.

Wyjaśnienie:
Aby przejść z lewego górnego pola do prawego dolnego na planszy 4×4, musimy zrobić:
– 3 kroki w prawo (P),
– 3 kroki w dół (D).

Łącznie mamy więc 6 ruchów: 3 razy P i 3 razy D. Różne ścieżki to różne kolejności tych liter.
To jest zadanie z permutacjami z powtórzeniami:
liczba ścieżek = 6! / (3! · 3!) = 720 / (6 · 6) = 720 / 36 = 20.

Zadanie 14. Dziwny ciąg liczb

Dany jest ciąg liczb:
2, 5, 11, 23, …

Każdy następny wyraz powstaje według tej samej zasady.
Zauważ, że:
2 → 5 (2 · 2 + 1),
5 → 11 (5 · 2 + 1),
11 → 23 (11 · 2 + 1).

Czyli: następny wyraz = poprzedni · 2 + 1.

Jaka liczba będzie 6. wyrazem tego ciągu?

Pokaż odpowiedź

Odpowiedź: Szóstym wyrazem jest liczba 95.

Wyjaśnienie – wyliczamy kolejne wyrazy:
1) a1 = 2
2) a2 = 2 · 2 + 1 = 5
3) a3 = 5 · 2 + 1 = 11
4) a4 = 11 · 2 + 1 = 23
5) a5 = 23 · 2 + 1 = 47
6) a6 = 47 · 2 + 1 = 95

Odpowiedź: 95.

Zadanie 15. Monety 2 zł i 5 zł

W pudełku są tylko monety 2 zł i 5 zł.
Razem jest ich 6 sztuk, a ich łączna wartość to 18 zł.
Ile jest monet 2-złotowych, a ile 5-złotowych?

Pokaż odpowiedź

Odpowiedź: Są 4 monety 2 zł i 2 monety 5 zł.

Wyjaśnienie:
Oznaczmy:
– x – liczba monet 2 zł,
– y – liczba monet 5 zł.

Mamy dwa warunki:
1) x + y = 6 (razem 6 monet),
2) 2x + 5y = 18 (wartość w złotówkach).

Z pierwszego równania: x = 6 − y.
Podstawiamy do drugiego:
2(6 − y) + 5y = 18
12 − 2y + 5y = 18
12 + 3y = 18
3y = 6 ⇒ y = 2.

Skoro y = 2, to x = 6 − 2 = 4.
Sprawdzenie: 4 · 2 zł + 2 · 5 zł = 8 + 10 = 18 zł – zgadza się.

Kolejne zadania – coraz trudniejsze

Zadanie 16. Program z dzieleniem przez 4

Rozważ program: 

Ustaw x = 1.
Powtórz 7 razy:
  zwiększ x o 3
  jeśli x jest podzielne przez 4, to podziel x przez 2
Na końcu wypisz x.

Jaką wartość wypisze program?

Pokaż odpowiedź

Odpowiedź: Program wypisze liczbę 8.

Wyjaśnienie – prześledzenie krok po kroku:
Start: x = 1.

1) +3 ⇒ x = 4, 4 jest podzielne przez 4 ⇒ x = 4 / 2 = 2
2) +3 ⇒ x = 5 (niepodzielne przez 4)
3) +3 ⇒ x = 8, 8 jest podzielne przez 4 ⇒ x = 8 / 2 = 4
4) +3 ⇒ x = 7 (niepodzielne przez 4)
5) +3 ⇒ x = 10 (niepodzielne przez 4)
6) +3 ⇒ x = 13 (niepodzielne przez 4)
7) +3 ⇒ x = 16, 16 jest podzielne przez 4 ⇒ x = 16 / 2 = 8

Po wykonaniu 7 powtórzeń otrzymujemy x = 8.

Zadanie 17. Ile ma dzielników?

Dana jest liczba:
N = 23 · 32 · 5.

Ile dodatnich dzielników ma liczba N?

Pokaż odpowiedź

Odpowiedź: Liczba N ma 24 dodatnie dzielniki.

Wyjaśnienie:
Gdy liczba ma postać rozkładu na czynniki pierwsze:
N = p1a · p2b · p3c,
to liczba jej dodatnich dzielników wynosi:
(a + 1) · (b + 1) · (c + 1).

Tutaj N = 23 · 32 · 51, więc:
(3 + 1) · (2 + 1) · (1 + 1) = 4 · 3 · 2 = 24.

Zadanie 18. Układanie słowa „BANAN”

Ile różnych wyrazów (układów liter) można utworzyć z liter słowa „BANAN”?
(Uwzględniamy, że niektóre litery się powtarzają.)

Pokaż odpowiedź

Odpowiedź: Można utworzyć 30 różnych wyrazów.

Wyjaśnienie:
Słowo „BANAN” ma 5 liter, w tym:
– litera B: 1 raz,
– litera A: 2 razy,
– litera N: 2 razy.

Gdyby wszystkie litery były różne, byłoby 5! = 120 ułożeń.
Ale litery A i N powtarzają się, więc dzielimy przez 2! za A i przez 2! za N:
liczba różnych wyrazów = 5! / (2! · 2!) = 120 / 4 = 30.

Zadanie 19. Skaczący indeks

Mamy tablicę (pięć liczb):
t[1] = 2, t[2] = 5, t[3] = 1, t[4] = 4, t[5] = 3.

Rozważ program: 

Ustaw i = 1.
Powtórz 4 razy:
  i := t[i]
Wypisz i.

Jaką wartość wypisze program?

Pokaż odpowiedź

Odpowiedź: Program wypisze 1.

Wyjaśnienie – krok po kroku:
Start: i = 1.

1) i := t[1] = 2
2) i := t[2] = 5
3) i := t[5] = 3
4) i := t[3] = 1

Po czterech krokach i wraca do wartości 1.

Zadanie 20. Dwójkowy zapis liczby

Mamy liczbę 27 zapisaną w systemie dziesiętnym.

  1. Jaki jest zapis liczby 27 w systemie dwójkowym (binarnym)?
  2. Ile cyfr „1” występuje w tym zapisie?
Pokaż odpowiedź

Odpowiedź:
1) 27 w systemie binarnym to 11011.
2) W tym zapisie występują 4 jedynki.

Wyjaśnienie:
Rozkładamy 27 na sumę potęg dwójki:
27 = 16 + 8 + 2 + 1 = 24 + 23 + 21 + 20.
To odpowiada zapisowi bitowemu: 11011 (1·16 + 1·8 + 0·4 + 1·2 + 1·1).
Zliczamy jedynki: w napisie „11011” są cztery cyfry „1”.

Zadanie 21. Zagnieżdżone warunki

Rozważ program: 

Ustaw x = 15.
Jeśli x jest podzielne przez 3, to:
  x := x + 5
w przeciwnym razie:
  x := x + 2

Jeśli x jest teraz parzyste, to:
  x := x / 2
w przeciwnym razie:
  x := x + 1

Wypisz x.

Jaką wartość wypisze program?

Pokaż odpowiedź

Odpowiedź: Program wypisze 10.

Wyjaśnienie:
Start: x = 15.
15 jest podzielne przez 3, więc w pierwszym warunku:
x := x + 5 ⇒ x = 20.

Teraz sprawdzamy drugi warunek:
20 jest parzyste, więc:
x := x / 2 ⇒ x = 10.

Wypisana zostaje liczba 10.

Zadanie 22. Trzykrotne zastosowanie funkcji

Dana jest funkcja f zdefiniowana dla liczb całkowitych: 

f(x) = 2x - 3

Oblicz wartość f(f(f(5))).

Pokaż odpowiedź

Odpowiedź: f(f(f(5))) = 19.

Wyjaśnienie – po kolei:
1) Najpierw f(5):
f(5) = 2 · 5 − 3 = 10 − 3 = 7.

2) Teraz f(f(5)) = f(7):
f(7) = 2 · 7 − 3 = 14 − 3 = 11.

3) Teraz f(f(f(5))) = f(11):
f(11) = 2 · 11 − 3 = 22 − 3 = 19.

Ostatecznie otrzymujemy 19.

Zadanie 23. Trzycyfrowe rosnące i podzielne przez 9

Szukamy trzycyfrowych liczb, w których cyfry są rosnące (każda następna większa od poprzedniej) i jednocześnie cała liczba jest podzielna przez 9.

Przykład liczby o rosnących cyfrach (niekoniecznie podzielnej przez 9): 247 (2 < 4 < 7).

Ile jest takich liczb?

Pokaż odpowiedź

Odpowiedź: Jest 10 takich liczb.

Wyjaśnienie (idea):
Sprawdzamy trzycyfrowe liczby 100–999, w których cyfry rosną (a < b < c). Dla każdej takiej liczby obliczamy sumę cyfr – jeśli suma jest podzielna przez 9, to cała liczba jest podzielna przez 9.

Po takim przeglądzie dostajemy dokładnie następujące liczby:
126, 135, 189, 234, 279, 369, 378, 459, 468, 567.
Jest ich razem 10.

Zadanie 24. Liczba z trzema warunkami

Szukamy najmniejszej dodatniej liczby całkowitej n, która spełnia jednocześnie warunki:

  • n jest podzielne przez 6,
  • przy dzieleniu przez 5 daje resztę 2,
  • przy dzieleniu przez 7 daje resztę 3.

Jaka to liczba?

Pokaż odpowiedź

Odpowiedź: Najmniejsza taka liczba to 192.

Wyjaśnienie (intuicyjne):
Szukamy n, dla którego:
– n % 6 = 0,
– n % 5 = 2,
– n % 7 = 3.

Możemy zacząć od liczb podzielnych przez 6 i sprawdzać kolejne (6, 12, 18, 24, …), aż trafimy na liczbę spełniającą pozostałe warunki. Gdy dojdziemy do n = 192, mamy:
– 192 / 6 = 32 (bez reszty),
– 192 : 5 = 38 reszty 2,
– 192 : 7 = 27 reszty 3.

Żadna mniejsza liczba naturalna nie spełnia wszystkich trzech warunków naraz, więc odpowiedź to 192.

Zadanie 25. Gra z zapałkami

Na stole leży 21 zapałek.
Dwóch graczy na zmianę zabiera z puli 1, 2 lub 3 zapałki.
Wygrywa ten, kto weźmie ostatnią zapałkę.

Załóżmy, że obaj grają najlepiej jak potrafią.

  1. Czy wygrywającą strategię ma gracz, który zaczyna, czy ten, który jest drugi?
  2. Jak powinien zagrać w pierwszym ruchu, żeby mieć pewną wygraną?
Pokaż odpowiedź

Odpowiedź:
1) Wygrywającą strategię ma pierwszy gracz.
2) W pierwszym ruchu powinien wziąć 1 zapałkę (zostawić 20).

Wyjaśnienie:
Kluczowa obserwacja: jeśli po Twoim ruchu na stole zostaje wielokrotność 4 (np. 4, 8, 12, 16, 20), to jesteś „na prowadzeniu”.

– Na początku jest 21 zapałek.
– Jeśli pierwszy gracz weźmie 1 zapałkę, zostanie 20 = 5 · 4 (wielokrotność 4).
– Cokolwiek zrobi przeciwnik (weźmie 1, 2 lub 3), pierwszy gracz może tak odpowiedzieć (3, 2 lub 1), żeby w sumie w danej parze ruchów zawsze brać 4 zapałki.

Przykład:
– jeśli drugi weźmie 3, pierwszy weźmie 1 (razem 4),
– jeśli drugi weźmie 2, pierwszy weźmie 2,
– jeśli drugi weźmie 1, pierwszy weźmie 3.

W ten sposób po każdej parze ruchów liczba zapałek znów jest wielokrotnością 4, aż w końcu drugi gracz zostaje zmuszony wziąć ostatnią zapałkę przed końcem, a pierwszy może doprowadzić do sytuacji, w której to on wygrywa.

Zadanie 26. Program sumujący potęgi dwójki

Rozważ program (w pseudokodzie): 

Ustaw x = 1, y = 0.
Powtórz 6 razy:
  y := y + x
  x := 2 * x
Na końcu wypisz y.

Jaką wartość wypisze program?

Pokaż odpowiedź

Odpowiedź: Program wypisze liczbę 63.

Wyjaśnienie – krok po kroku:
Start: x = 1, y = 0.

1) y = 0 + 1 = 1, x = 2
2) y = 1 + 2 = 3, x = 4
3) y = 3 + 4 = 7, x = 8
4) y = 7 + 8 = 15, x = 16
5) y = 15 + 16 = 31, x = 32
6) y = 31 + 32 = 63, x = 64

Po 6 powtórzeniach otrzymujemy y = 63 – to suma potęg dwójki: 1 + 2 + 4 + 8 + 16 + 32.

Zadanie 27. Robot omijający zablokowane pole

Wyobraź sobie, że robot porusza się po planszy 3×3 pól (3 wiersze i 3 kolumny).
Zaczyna w lewej górnej kratce, ma dojść do prawej dolnej kratki.
Może wykonywać tylko ruchy:

  • w prawo (P),
  • w dół (D).

Środkowe pole (to w drugim wierszu i drugiej kolumnie) jest zablokowane – robot nie może tam wejść.
Ile różnych „programów ruchu” (ciągów liter P i D) doprowadzi robota z lewego górnego do prawego dolnego pola, jeśli nie wolno wchodzić na środkowe pole?

Pokaż odpowiedź

Odpowiedź: Są dokładnie 2 takie ciągi ruchów.

Wyjaśnienie:
Bez zakazów robot musi zrobić 2 kroki w prawo i 2 w dół – w sumie 4 kroki.
Liczba wszystkich możliwych ciągów to 4! / (2! · 2!) = 6.

Teraz liczymy te, które przechodzą przez środkowe pole. Droga dzieli się na dwa odcinki:
– z lewego górnego do środka: 1 P i 1 D ⇒ 2! / (1!·1!) = 2 ścieżki,
– ze środka do prawego dolnego: znowu 1 P i 1 D ⇒ 2 ścieżki.

Ścieżek przez środek jest 2 · 2 = 4, więc ścieżek omijających środek jest:
6 − 4 = 2.

Zadanie 28. Program liczący zera na końcu n!

Chcemy napisać funkcję (w pseudokodzie) zera(n), która zwraca liczbę zer na końcu liczby n! (n silnia).
Używamy znanego triku: liczymy, ile razy w rozkładzie n! pojawia się czynnik 5. 

funkcja zera(n):
  wynik := 0
  k := 5
  dopóki k <= n:
    wynik := wynik + (n div k)   // dzielenie całkowite
    k := k * 5
  zwróć wynik

Ile zer na końcu ma liczba 20!? (czyli jaka jest wartość zera(20)?)

Pokaż odpowiedź

Odpowiedź: Liczba 20! ma na końcu 4 zera.

Wyjaśnienie:
Dla n = 20 mamy:
– pierwsza pętla: k = 5 ⇒ wynik += 20 div 5 = 4 ⇒ wynik = 4,
– druga pętla: k = 25 > 20 ⇒ pętla się kończy.

Otrzymujemy zera(20) = 4, więc 20! ma na końcu 4 zera.

Zadanie 29. Szyfr jako funkcja na napisie

Mamy napis z liter A, B, C, D. Definiujemy funkcję szyfrującą koduj(s) tak:

  1. Każdą literę zamieniamy według reguły: A → B, B → C, C → D, D → A.
  2. Odwracamy cały napis (czytamy litery od końca).

Przykładowy pseudokod: 

funkcja koduj(s):
  dla każdej litery w s:
    zamień ją wg reguły A→B, B→C, C→D, D→A
  odwróć kolejność liter w s
  zwróć s

Jaki napis otrzymamy, jeśli zaszyfrujemy wyraz „ABCDAB”?

Pokaż odpowiedź

Odpowiedź: Otrzymamy słowo „CBADCB”.

Wyjaśnienie:
Najpierw zamieniamy litery:
A B C D A B ⇒ B C D A B C

Potem odwracamy cały napis:
B C D A B C ⇒ C B A D C B.

Wynik to „CBADCB”.

Zadanie 30. Dokładnie dwie jedynki w 10-bitowym rejestrze

Wyobraź sobie 10-bitowy rejestr (ciąg 10 pozycji, każda to 0 lub 1).
Każdy stan takiego rejestru odpowiada liczbie od 0 do 1023 w systemie dziesiętnym.

Ile jest różnych stanów rejestru, w których dokładnie 2 bity mają wartość 1, a pozostałe są równe 0?

Pokaż odpowiedź

Odpowiedź: Jest 45 takich stanów.

Wyjaśnienie:
Mamy 10 pozycji i chcemy wybrać dokładnie 2 z nich, na których będzie 1.
Pozostałe 8 pozycji automatycznie ma wartość 0.

Liczbę sposobów wybierania 2 pozycji z 10 opisuje kombinacja:
C(10, 2) = 10 · 9 / 2 = 45.

Każdy taki wybór pozycji jedynek odpowiada innemu stanowi rejestru, czyli innej liczbie.