Uniwersytet im. A. Mickiewicza w Poznaniu
Algorytm zachłanny to taki, który dokonuje wyborów, jakie w aktualnej chwili (lokalnie) wydają się najlepsze, natomiast nie jest jasne, czy są one słuszne w sensie globalnym, gdy szukamy rozwiązania optymalnego. Choć nie jest to regułą, to niektóre algorytmy zachłanne dają optymalne rozwiązania, i o tym będzie w tym kąciku.
Przykład 1. Mamy banknoty o nominałach \(10^k,\) \(2\cdot10^k\) i \(5\cdot10^k\) pengő dla \(k=0,1,2,\ldots\) Chcemy wypłacić nimi \(n\) pengő dla pewnej liczby naturalnej \(n.\) Robimy to w ten sposób, że za każdym razem, gdy zostało jeszcze do wypłacenia \(m\) pengő, wybieramy banknot z największym nominałem nieprzekraczającym \(m.\)
Przykład 2. Chcemy dojechać z miasta \(A\) do miasta \(B.\) Nawigacja prowadzi nas według następującej reguły: udaj się do miasta najbliższego aktualnej pozycji, spośród tych, w których jeszcze nie byłeś.
Pozostawiam Czytelnikowi uzasadnienie, że algorytm przedstawiony w pierwszym przykładzie daje optymalne rozwiązanie ze względu na liczbę wykorzystanych banknotów, a algorytm z przykładu drugiego nie jest optymalny ze względu na przebyty dystans.
Zadania
-
Dla danego wielokąta \(\mathcal{W}\) niech \(s(\mathcal{W})\) oznacza sumę kwadratów długości jego boków. Udowodnić, że jeśli \(\mathcal{W}\) jest wielokątem wypukłym, to można wskazać takie trzy jego wierzchołki \(A,\) \(B,\) \(C,\) że \(s(\triangle ABC)\ge s(\mathcal{W}).\) (XI Wielkopolska Liga Matematyczna)
Wskazówka Wybieramy trzy kolejne wierzchołki \(X,\) \(Y,\) \(Z\) – tak by \(|\measuredangle XYZ|\ge 90^\circ\) (jest to możliwe, gdy wielokąt ma co najmniej cztery boki). Jeśli \(\mathcal{W}'\) jest wielokątem powstałym z \(W\) przez zastąpienie boków \(XY\) i \(YZ\) bokiem \(XZ,\) to \(s(\mathcal{W'})\ge s(\mathcal{W}).\)
-
Dana jest liczba całkowita \(n\ge2\) oraz ciąg \(n-1\) znaków mniejszości i większości. Wykazać, że liczby \(1,2,\ldots,n\) można tak wstawić między znaki, aby wszystkie nierówności były spełnione (na przykład dla \(n=5\) i ciągu znaków \((<,>,>,<)\) mamy \(4<5>2>1<3\)). (III WLM)
Wskazówka Postawmy \(1\) na pierwszym miejscu, a dalej będziemy dobierać liczby całkowite (niekoniecznie dodatnie) tak, by nierówności były zachowane; dla „ \(>\) ” największą możliwą, a dla „ \(<\) ” – najmniejszą. Otrzymamy \(n\) kolejnych liczb całkowitych, które trzeba będzie jeszcze tylko powiększyć o pewną stałą.
-
Liczby naturalne \(k,n\ge2\) spełniają warunek \(1+\frac12+\ldots+\frac1n<k.\) Dowieść, że zbiór \(\{\frac12,\frac13,\ldots,\frac1n\}\) można podzielić na \(k\) podzbiorów, z których każdy ma sumę elementów nie większą niż \(1.\)
Wskazówka Wystarczy każdy kolejny element zbioru \(\{\frac 12,\frac 13,\ldots,\frac 1n\}\) dodawać do któregokolwiek z tych \(k\) podzbiorów – można wykazać, na przykład metodą nie wprost, że zawsze się do jakiegoś „zmieści”.
-
Zbiór nazywamy wolnym od sum, jeśli każde dwa jego różne podzbiory mają różne sumy elementów. Niech \(k\) będzie liczbą całkowitą dodatnią. Dowieść, że zbiór o więcej niż \(3^k\) elementach ma \((k+1)\) -elementowy podzbiór wolny od sum. (LXII OM)
Wskazówka Przypuśćmy, że mamy zbiór \(X=\{x_1,x_2,\ldots,x_k\}\) wolny od sum, i chcemy powiększyć go o nowy element \(y.\) Jest to możliwe dokładnie wtedy, gdy dla dowolnych podzbiorów \(A,B\subseteq X\) zachodzi \(y \neq \sum_{a\in A}a - \sum_{b\in B}b = \sum_{i=1}^k\varepsilon_ix_i,\) przy czym \(\varepsilon_i\in\{-1,0,1\}.\) To oznacza, że co najwyżej \(3^k\) liczb może zaszkodzić zbiorowi \(X.\)
-
Wyznaczyć najmniejszą stałą \(c\) o następującej własności: Dla każdego całkowitego dodatniego \(n\) w sumie \(1+\frac12+\frac13+\ldots+\frac1n\) można zmienić część znaków \(+\) na \(-\) w taki sposób, by otrzymać wyrażenie o wartości bezwzględnej nieprzekraczającej \(\frac{c}{n^2}.\) (XV WLM)
Wskazówka Szukaną stałą jest \(c=\frac{35}{12}\) i jest ona osiągana dla \(n=5.\) Niech \(S_n\) będzie najmniejszą możliwą wartością bezwzględną utworzonego wyrażenia. Można wykazać indukcyjnie, że dla \(n\ge 7\) zachodzi nierówność \(S_n<\frac{1{,}3}{n^2}.\) Krok indukcyjny z \(n\) do \(n+2\) otrzymujemy przez dodanie \(\pm\frac 1{n+1}\mp\frac 1{n+2},\) w zależności od znaku.
-
Rozstrzygnąć, czy w kole można zmieścić nieskończony zbiór parami rozłącznych kół, które mają nieskończoną sumę obwodów.
Wskazówka Zachodzi \(1+\frac 12+\frac 13+\ldots=\infty.\) Koła o promieniach \(\frac 1{2^k},\frac 1{2^k+1},\ldots,\frac 1{2^{k+1}-1}\) można zmieścić w prostokącie o wymiarach \(\frac 1{2^{k-1}}\times 2.\)
Problem otwarty
-
Czy w zadaniu 3 zawsze możliwy jest podział na \(k-1\) podzbiorów?