Matematyka dyskretna - zadania na egzamin

lucrah · Post autor: **lucrah** » 5 paź 2015, o 10:06

Witam,

czy byłby ktoś w stanie rozwiązać kilka zadań, które pojawiły się na egzaminie z matematyki dyskretnej? Sprawa jest raczej pilna bo jutro poprawka i gdyby ktoś był w stanie wytłumaczyć jak to ugryźć.

1. Udowodnij twierdzenie : " jeśli pewne dwie liczby naturalne są równe \(\displaystyle{ 5}\) modulo \(\displaystyle{ 7}\), to ich iloczyn jest równy \(\displaystyle{ 4}\) modulo \(\displaystyle{ 7}\)". Jaki rodzaj dowodu został wykorzystany?

2. Na czym polega zasada indukcji matematycznej. przedstaw jej schemat ( i udowodnij) na przykładzie twierdzenia \(\displaystyle{ \frac{3}{15} + \frac{8}{15} + \frac{13}{15} + ... + \frac{5n-2 }{15} = \frac{5n ^{2} + n }{30}}\)

4. Ile jest możliwości wylosowania \(\displaystyle{ 3}\) kul spośród \(\displaystyle{ 3}\) kul białych, \(\displaystyle{ 6}\) kul zielonych i \(\displaystyle{ 3}\) kul czerwonych, tak aby otrzymać przynajmniej pod jednej wylosowanej kuli koloru białego i koloru czerwonego ( przedstaw stosowaną zasadę kombinatoryczną i objaśnij obliczenia. )

5.Kiedy relacja jest równowaznościowa? Przedstaw warunki. Objaśnij czy relacja \(\displaystyle{ m R n \Leftrightarrow \frac{1}{m} + \frac{1}{n} = 1}\) dla \(\displaystyle{ m, n \in\NN}\) jest równoważnościowa?

jutrvy · Post autor: **jutrvy** » 5 paź 2015, o 11:46

1. Te dwie liczby są postaci \(\displaystyle{ 7k + 5, 7l+5}\) dla pewnych całkowitych \(\displaystyle{ k,l}\). Ich iloczynem będzie \(\displaystyle{ 49kl + 35(k+l) + 25 = 7(7kl + 5(k+l) + 3) + 4}\), zatem ich iloczyn w dzieleniu przez siedem daje resztę \(\displaystyle{ 4}\). Udowodniłem to metodą najbardziej elementarną, jak tylko można :p

2.

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Indukcja_matematyczna

.

3. Liceum.

4. Nie ma czegoś takiego, jak relacja równoważnościowa...

lucrah · Post autor: **lucrah** » 5 paź 2015, o 12:56

Jeżeli chodzi o zadanie 3, wiem że temat z liceum i prosty, ale czy mogę to zapisać w takiej formie że wypisze wszystkie możliwe kombinacje i po prostu jest zlicze razem?

A w zadaniu z relacjami taka była dokładnie treść na kartce z egzaminu podejrzewam, że chodziło o równoważnościową więc trzeba udowodnić że jest symtryczna przechodnia i zwrotna.

Premislav · Post autor: **Premislav** » 5 paź 2015, o 13:44

Jak to "wypiszę wszystkie możliwe kombinacje", chcesz sobie pisać biała-czerwona-czerwona itp.? Bo nie rozumiem, jeśli tak, to proponuję coś wygodniejszego.
Możliwości wylosowania trzech kul z tego zbioru tak, aby nie było białych, jest \(\displaystyle{ {9\choose 3}}\), podobnie mamy \(\displaystyle{ {9 \choose 3}}\) możliwości wylosowania z tego zbioru trzech kul tak, aby nie było czerwonych. A na \(\displaystyle{ {6 \choose 3}}\) sposobów możemy wybrać tak, by nie wylosować ani kuli białej, ani kuli czerwonej (po prostu zachodzi to tylko jeśli wylosujemy same zielone).
Czyli z zasady włączeń i wyłączeń mamy \(\displaystyle{ {9 \choose 3}+{9 \choose 3}-{6 \choose 3}}\) możliwości wylosowania trzech kul tak, aby nie wylosować żadnej białej lub nie wylosować żadnej czerwonej. Teraz odejmij tę liczbę od liczby wszystkich możliwych wylosowań \(\displaystyle{ 3}\) spośród \(\displaystyle{ 12}\) kul i masz wynik.

jutrvy · Post autor: **jutrvy** » 5 paź 2015, o 21:22

Relacja równoważności, nie równoważnościowa, jeśli już. No to pokaż, że jest zwrotna, przechodnia i antysymetryczna. Możesz zacząć od zwrotności.

-- 5 paź 2015, o 20:23 --

PS nie rozumiem, co znaczy "...(i udowodnij) na przykładzie twierdzenia...", czyżby chodziło o dowód przez przykład?

Post autor: **Jan Kraszewski** » 5 paź 2015, o 23:03

jutrvy pisze:Relacja równoważności, nie równoważnościowa, jeśli już. No to pokaż, że jest zwrotna, przechodnia i antysymetryczna. Możesz zacząć od zwrotności.

Co to ma być?!

JK

jutrvy · Post autor: **jutrvy** » 5 paź 2015, o 23:20

To? To jest pomyłka.