3545336446

Zadania dodatkowe z Matematyki Dyskretnej semestr letni 2015

1    Indukcja

Zadanie 1.1. Udowodnić indukcyjnie, że mając do dyspozycji nieograniczoną liczbę monet o wartości 2 lub 5 złotych, można zapłacić w automacie (niewydającym reszty) za dowolny napój, którego cena wynosi n > 5 złotych.

Zadanie 1.2. Rozważ grę, w której na początku mamy dwa stosy po n żetonów (n > 1). W każdej rundzie kolejno każdy z dwóch graczy bierze dowolną liczbę żetonów z jednego ze stosów. Gracz, który zabierze ostatni żeton wygrywa. Pokaż indukcyjnie, że dla dowolnego n > 1 drugi gracz ma strategię wygrywającą (tzn. gdy obaj gracze grają optymalnie, to zawsze drugi wygrywa).

Zadanie 1.3. Załóżmy, że każda prostokątna tabliczka czekolady składa się z identycznych kwadratowych kostek. Dowolna taka tabliczka może zostać przełamana tylko wdłuż pionowej lub poziomej linii prostej rozdzielającej kostki. Ile „przełamań” należy zrobić, aby podzielić dowolną prostokątną tabliczkę czekolady składającą się z n identycznych kwadratowych kostek na n kostek? Odpowiedź uzasadnij korzystając z indukcji.

2    Zasada Szufladkowa

Zadanie 2.1. Udowodnij, że w dowolnym wielościanie

a.    istnieją dwa wierzchołki, z których wychodzi taka sama liczba krawędzi;

b.    istnieją dwie ściany, które mają tyle samo krawędzi.

Zadanie 2.2. W kole o promieniu 1

a.    wybrano 8 punktów. Wykaż, że istnieje wśród nich co najmniej jedna para punktów, których odległość nie przekracza 1.

b.    wybrano 14 punktów, z których żadne 3 nie są współliniowe. Wykaż, że trzy z nich tworzą trójkąt o polu co najwyżej 0.6.

Zadanie 2.3. Zadanie 1.19 (z podręcznika)

3    Schematy wyboru

Zadanie 3.1. Wyznacz liczbę calkowitoliczbowych rozwiązań równania:

xi + X2 +    4- ano = 30, gdy x, > 0 dla i = 3,..., 10 oraz

a.    xi > 3, 0 < x₂ < 2;

b.    0 < xi < 10, x₂ > 0;

c.    0 < xi < 10, 0 < x₂ < 10.

Zadanie 3.2. Alfabet łaciński zawiera 21 spółgłosek i 5 samogłosek. Ile ciągów składających się ze 100 wielkich liter alfabetu łacińskiego zawiera:

a.    dokładnie 3 samogłoski?

b.    co najwyżej 3 samogłoski?

c.    tę samą liczbę spółgłosek co samogłosek?

Zadanie 3.3. Ile ciągów

a.    binarnych;

b.    ternarnych (składających się ze znaków: 0,1,2);

długości 200 zawiera dokładanie 100 zer w 7 seriach? (Serią zer nazywamy ciąg kolenych zer, który nie jest poprzedzony zerem i po którym nie następuje zero, np. ciąg 120000222010022 ma trzy serie zer).

Zadanie 3.4. Na ile sposobów można usadzić 10 spośród 100 uczestników wesela wokół okrągłego stołu? Dwa ustawienia uznajemy za takie same, jeśli każda osoba przy stole ma tego samego sąsiada po prawej i po lewej w obu ustawieniach. Jak zmieni się odpowiedź, jeśli przy stole mają siedzieć obok siebie pan i pani młoda?