Zadania rozgrzewkowe

Poniżej przedstawiamy kilka zadań – zagadek z matematyki rekreacyjnej, do których rozwiązania wymagana jest przede wszystkim umiejętność logicznego myślenia. Wybór zadań nie jest jednak przypadkowy. Przede wszystkim, wiele z nich stosunkowo łatwo rozwiązać, ale warto poświęcić chwilę na zastanowienie się nad rozwiązaniem jak najmniej pracochłonnym. Ponadto każde z tych zadań można sformułować tak, żeby zamiast obliczenia wyniku dla konkretnych danych, wymagane było napisanie programu, który będzie w stanie obliczyć wynik dla dowolnych danych rozsądnego rozmiaru. A stąd już bardzo blisko do zadań Olimpiady Informatycznej. I tak np. zad. 1 poniżej powstało na podstawie zadania Trójkąty jednobarwne z IV Olimpiady Informatycznej.

 

Zad. 1. Na płaszczyźnie wybrano dziesięć punktów, z których żadne trzy nie są współliniowe, i każdą parę różnych punktów połączono odcinkiem: niebieskim lub zielonym.

Ile jest na rysunku trójkątów jednobarwnych, mających wierzchołki w pewnych trzech spośród zadanych dziesięciu punktów?

Wskazówka

Rozwiązanie

 

Zad. 2. Na półce stoi dwanaście tomów encyklopedii. Ich kolejność, wskutek wieloletniego użytkowania, jest dosyć przypadkowa:

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

W jednym ruchu możesz wyjąć dowolny tom i umieścić go w wybranym miejscu, ewentualnie przesuwając pewne z pozostałych tomów. W jakiej najmniejszej liczbie ruchów możesz uporządkować wszystkie tomy, tak aby były ustawione w naturalnej kolejności od 1 do 12?

Wskazówka

Rozwiązanie

 

Zad. 3. Zmieniasz zdanie i postanawiasz uporządkować tomy encyklopedii z zad. 3 za pomocą ruchów polegających na zamianie pewnych par sąsiednich tomów miejscami. Ile takich ruchów potrzeba do uporządkowania półki?

Wskazówka

Rozwiązanie

 

Zad. 4. Jak pokryć szachownicę 8 na 8 z jednym usuniętym polem za pomocą klocków w kształcie litery L, złożonych z trzech kwadracików? Klocki nie mogą na siebie nachodzić ani wystawać poza szachownicę.

Wskazówka

Rozwiązanie

 

Zad. 5. Czy w poniższym ciągu liczb:

1, 1, 9, 7, 12, 4, 12, 5, 7, 3, 7, 2, 10, 2, 3

można znaleźć niepusty spójny podciąg (tj. jednokawałkowy fragment), którego suma jest podzielna przez 13?

Wskazówka

Rozwiązanie

 

Zad. 6. Ile różnych podciągów ciągu:

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

ma sumy podzielne przez 5? Podciągi złożone z takich samych elementów, ale różnie umiejscowione w ciągu, uznajemy za różne. Ponadto pomijamy ciąg pusty (zeroelementowy).

A ile spójnych (czyli jednokawałkowych) podciągów o sumach podzielnych przez 5 występuje w powyższym ciągu?

Wskazówka

Rozwiązanie

 

Zad. 7. Jaka jest ostatnia cyfra liczby 21000? A jaka jest przedostatnia cyfra tej liczby?

Wskazówka

Rozwiązanie

 

Zad. 8. Niech Z={1, 2, ..., 17}. W tym zadaniu interesować nas będą takie zbiory A ⊆ Z, że dla każdej liczby naturalnej m ∈ Z co najwyżej jedna z liczb m, 2m należy do A (czyli dla żadnej liczby naturalnej m ∈ Z nie mogą naraz zachodzić warunki m ∈ A oraz 2m ∈ A). Nazwijmy takie zbiory A antydwójkowymi.

Jaki jest najliczniejszy zbiór antydwójkowy? A ile jest wszystkich zbiorów antydwójkowych?

Wskazówka

Rozwiązanie

 

Zad. 9. Mamy do dyspozycji jedenaście monet o następujących nominałach:

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

Jaka jest najmniejsza (całkowita dodatnia) kwota, której nie da się wypłacić za ich pomocą?

Wskazówka

Rozwiązanie

 

Zad. 10. Liczbę całkowitą dodatnią nazywamy palindromiczną, jeżeli jej zapis dziesiętny przeczytany normalnie i wspak wygląda tak samo – przykładami takich liczb są 5, 22 i 21312. Ile jest liczb palindromicznych w przedziale [285 924, 84 633 902]?

Wskazówka

Rozwiązanie




Obszerne fragmenty powyższego tekstu pochodzą z artykułów „Zadanka (nie)informatyczne” w miesięczniku Delta (numer 8/2009) oraz artykułu „Liczba liczb” z numeru 6/2010 tego miesięcznika. Patrz także stara strona Delty oraz portal DeltaMi.

© Anna Michalska
Uniwersytet Warszawski