Lista 1: Rozgrzewka
Zadania na ćwiczenia: 2025-02-24
Zadania do samodzielnego rozwiązania
- Na szachownicy o wymiarach \(n\times n\) umieszczono \(8\) nierozróżnialnych wież, w taki sposób aby żadne dwie się nie biły. Na ile sposobów można to zrobić? Jak zmieni się wynik, gdy wieże będą rozróżnialne?
Jeżeli wieże nie są rozróżnialne \({n \choose 8}^28!\) jeżeli wieże są rozróżnialne \({n \choose 8}^2(8!)^2\).
- Na ile sposobów można rozmieścić \(n\) kul w \(k\) urnach jeżeli: (a) kule są rozróżnialne, (b) kule są nierozróżnialne.
a \(n^k\) b \({n+k-1 \choose k-1}\)
- Ile jest liczb mniejszych od \(1000\) podzielnych przez jedną z liczb \(3\), \(5\), \(7\)?
\(542\)
- Na płaszczyznie danych jest pięć punktów kratowych (o obu współrzędnych całkowitych).
Wykazać, ze środek jednego z odcinków łączacych te punkty również jest kratowy
Należy pokazać, że istnieje para punktów na płaszczyźnie, której współrzędne mają tę samą parzystość. Teza wynika z zastosowania zasady szufladkowej Dirichleta.
- Oblicz prawdopodobieństwo zdarzenia, że w potasowanej talii \(52\) kart wszystkie cztery asy znajdują się koło siebie.
\(4!/(52\cdot 51\cdot 50)\)
Zadania na ćwiczenia
Na ile sposobów można ustawić \(7\) krzeseł białych i \(3\) czerwone przy okrągłym stole?
Zsumuj \[\begin{equation*} \sum_{k=0}^m{n+k \choose j} \end{equation*}\] gdzie \(m,n,j \in \mathbb{N}\) są liczbami naturalnymi. Zapisz \(k^2\) jako \(a_2{k \choose 2 }+ a_1{ k \choose 1} + a_0{k \choose 0}\). Wykorzystaj to do policzenia \(\sum_{k=0}^n{k^2}\)
-
Wachlarzem rzędu \(n\) nazywamy graf o wierzchołkach \(\{0, 1, \ldots , n\}\) z \(2n-1\) krawędziami zdefiniowanymi następująco: wierzchołek \(0\) połączony jest krawędzią z każdym z pozostałych wierzchołków i wierzchołek \(k\) połączony jest krawędzią z wierzchołkiem \(k+1\) dla każdego \(1 \leq k<n\). Dla przykładu wachlarz rzędu \(5\) wygląda następująco
Przyjmując \(S_0=0\), ile wynosi \(S_n\) liczba drzew rozpinających na takim grafie? Drzewem rozpinającym nazywamy spójny podgraf bez cykli zawierający wszystkie wierzchołki
Znajdź zależność rekurencyjną na \(S_n\).
W klasie jest \(15\) uczniów. Na każdej lekcji odpytywany jest losowo jeden z nich. Oblicz prawdopodobieństwo, że podczas \(16\) lekcji zostanie przepytany każdy z nich.
W Totolotku losuje się \(6\) z \(49\) liczb. Jakie jest prawdopodobieństwo, że żadne dwie nie będą dwiema kolejnymi liczbami naturalnymi?
Stefan Banach w każdej z kieszeni trzymał po pudełku zapałek. Początkowo każde z nich zawierało \(n\) zapałek. Za każdym razem kiedy Banach potrzebował zapałki sięgał losowo do jednej z kieszeni i wyciągał jedną zapałkę. Oblicz prawdopodobieństwo, że w momencie gdy sięgnął po puste pudełko, w drugim pozostało jeszcze \(k\) zapałek.
-
Oblicz \[\begin{equation*} \int_{-\infty}^{\infty} e^{-x^2} \: \mathrm{d}x. \end{equation*}\]
Podnieś całkę do kwadratu i zastosuj współrzędne biegunowe.
Grupa składająca się z \(2n\) pań i \(2n\) panów została podzielona na dwie równoliczne grupy. Znaleźć prawdopodobieństwo, że każda z tych grup składa się z takiej samej liczby pań i panów. Przybliżyć to prawdopodobieństwo za pomocą wzoru Stirlinga.
Zadania dodatkowe
- Pewien sułtan więził 100 osób. Pewnego dnia postanowił ich zgładzić. Jako, że był znany ze swego miłosierdzia dał im ostatnią szansę. Postawił przed nimi następujące zadanie. Każdemu więźniowi przyporządkował liczbę. Następnie w pokoju obok umieścił w rzędzie kolejno \(100\) pudełek i do każdego z nich włożył losową liczbę od \(1\) do \(100\) (w każdym pudełku inną). Wieżniowie po kolei, pojedynczo, wchodzą do pokoju z pudełkami. Mogą otworzyć \(50\) pudełek, aby znaleźć swój numer, ale pokój muszą pozostawić dokładnie w takim samym stanie w jakim go zastali. Następnie opuszczają pokój wychodząc innym wyjściem i nie mają możliwości skontaktowania się z pozostałymi osobami. Więźniowie zostaną ocaleni, jeżeli z nich każdy znajdzie swój numer. Jeżeli każdy z nich otwiera losowe 50 pudełek, to szanse ich przeżycia wynoszą \(2^{-100} \approx 7,8*10^{-31}\). Czy mają oni lepszą strategię?