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 < x2 < 2;
b. 0 < xi < 10, x2 > 0;
c. 0 < xi < 10, 0 < x2 < 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?
Wyszukiwarka
Podobne podstrony:
q 2011 09 14 54 49 Matematyka dyskretna Semestr letni 2011 Kolokwium zaliczeniowe - III tc ;rmin 1.
q dsc05543a Matematyka dyskretna Semestr letni 2011 I kolokwium 1. Wykazać, ż
q kruk poprawka Matematyka dyskretna Semestr letni 2011 I kolokwium (poprawkowe) 1. Wykazać,
img015 (50) Egzamin z matematyki termin I (ZIP semestr letni) Zadanicl .Wyznaczyć — J (ci dx Zadanie
Image0001 (16) Egzamin z matematyki, 1 rok, ZIP (semestr letni). .22.06.2009 Zadanie 1. Obliczyć
img018 3 Egzamin z matematyki część teoretyczna -semestr letni IMIR, rok I (dr Ryszard Mosurski
img023 2 0 — Egzamin z matematyki część zadaniowa - semestr letni IMIR, rok I (dr Ryszard Mosur
Image0001 (17) 22.06.2009 Egzamin z matematyki, 1 rok, ZIP (semestr letni) .n Zadanie 1. Obliczyć
e2 Egzamun dodatkowy z matematyki Wydział WILiŚ, Budownictwo, sem. 2, r.ak. 2009/2010 ZADANIA Zad.
Egzamin 09 10 (termin dod ) Egzamun dodatkowy z matematyki Wydział WILiŚ, Budownictwo, sem. 2, r.a
egzamin dodatkowy 09 2010 Egzamun dodatkowy z matematyki Wydział WILiŚ, Budownictwo, sem. 2, r.ak. 2
egzamin dodatkowy 13 14 Egzamun dodatkowy z matematyki Wydział WTLiŚ, Budownictwo, sem. 3. r.ak. 201
więcej podobnych podstron