grudzień 2022

Zad. 1. Nierówność [tex]f(x)\ge0[/tex] jest równoważna układowi nierówności [tex]a\ge0[/tex] i [tex]b^2-4ac\le0[/tex]. Niech [tex]d=b-a[/tex]. Warunek [tex]a0[/tex], nierówność [tex]b^2-4ac\le0[/tex] jest równoważna [tex]c\ge \frac{(a+d)^2}{4a}[/tex], a wyrażenie do zminimalizowania jest równe [tex]\frac{2a+d+c}{d}\ge\frac{(4a)(2a+d)+(a+d)^2}{4ad}= \frac{3}{2} + \frac{3}{4}(\frac{3a}{d}+\frac{d}{3a})\ge 3[/tex] i wartość ta jest osiągana dokładnie gdy [tex]c=\frac{(a+d)^2}{4a}[/tex] oraz [tex]\frac{3a}{d}=1[/tex]. Przykładowym wielomianem, dla którego wartość zadanego wyrażenia jest minimalna, jest [tex]x^2 + 4x+ 4.[/tex]

Zad. 2. Rozważmy układ współrzędnych o środku leżącym na odcinku AC. W tym rozwiązaniu punkty będziemy traktować jak dwuwymiarowe wektory. Relację [tex]DF\perp AE[/tex] możemy zapisać za pomocą iloczynu skalarnego jako [tex](D-F)\cdot (A-E)=0[/tex] lub równoważnie jako [tex]A\cdot D + E\cdot F=A\cdot F + D\cdot E[/tex]. Ze względu na symetrię [tex]A\cdot (B-D)=0[/tex]. Z założeń zadania wiemy, że [tex]AB\perp FB[/tex], czyli [tex](A-B)\cdot (F-B)=0[/tex], równoważnie [tex]A\cdot B + B\cdot F=A\cdot F + B\cdot B[/tex]. Analogicznie z [tex]AD\perp DE[/tex] otrzymujemy [tex]A\cdot D + D\cdot E=A\cdot E + D\cdot D[/tex]. Dodając otrzymane równości stronami oraz używając relacji [tex]D\cdot D=B\cdot B,A\cdot B=A\cdot D[/tex] wynikających z symetrii, otrzymujemy [tex]D\cdot E + A\cdot F =B\cdot F + A\cdot E[/tex]. Używając pozostałych otrzymanych przez nas tożsamości, otrzymujemy [tex]A\cdot B + E\cdot F = B\cdot F + A\cdot E[/tex], czyli [tex](A-F)\cdot (B-E)=0[/tex]. Stąd [tex]AF\perp BE[/tex], co należało dowieść.

Zad. 3. Szukaną tablicę skonstruujemy indukcyjnie. W każdym kroku będziemy z tablicy o wymiarach [tex]k\times k[/tex] i sumie elementów [tex]\ge 2000-k[/tex] usuwać jeden wiersz i jedną kolumnę otrzymując w ten sposób podtablicę o wymiarach [tex](k-1)\times (k-1)[/tex] i sumie elementów [tex]\ge 2000 -(k-1)[/tex]. Zaczynamy od tablicy [tex]2000\times 2000[/tex] z zadania i po 1000 kroków otrzymamy szukaną podtablicę. Wiersz i kolumnę którą usuniemy w danym kroku wybieramy w następujący sposób: Jeśli istnieją wiersz oraz kolumna o sumach elementów [tex]\le 0[/tex] to suma elementów należących do wiersza lub kolumny nie może przekraczać [tex]-1[/tex], bo jest liczbą niedodatnią będącą sumą nieparzyście wielu jedynek (dokładnie 2k-1). W takim razie usunięcie tego wiersza i kolumny zwiększy sumę elementów tablicy. Jeżeli wszystkie wiersze i kolumny mają dodatnią sumę elementów, to bez straty ogólności możemy przyjąć, że suma elementów tablicy jest [tex]< 3k[/tex]. W przeciwnym wypadku podtablica powstała po wyrzuceniu dowolnego wiersza i kolumny miałaby sumę elementów równą co najmniej [tex]3k - 2k = k\ge 2000-(k-1)[/tex] ([tex]k[/tex] zawsze jest większe niż 1000). Przy takim oszacowaniu na sumę elementów wiemy że istnieją wiersz oraz kolumna, z których każde ma sumę elementów [tex]\ge 2[/tex], czyli suma elementów należących do wiersza lub kolumny nie przekracza 3 (patrz argument powyżej). Jeżeli suma elementów tablicy jest [tex]\ge k + 2[/tex], to usunięcie tego wiersza i kolumny zagwarantuje nam podtablicę o sumie elementów [tex]\ge k-1\ge 2000 - (k-1)[/tex]. W przypadku gdy suma elementów [tex]s[/tex] naszej tablicy spełnia nierówności [tex]k\le s \le k+1[/tex] (wciąż rozważamy przypadek w którym suma elementów w każdym wierszu/kolumnie jest dodatnia) to analogiczny argument działa (teraz mamy lepsze oszacowanie na najmniejszą sumę elementów w wierszu/kolumnie). W przypadku gdy suma elementów w każdym wierszu jest dodatnia, ale istnieje kolumna o nieujemnej sumie usuwamy tę właśnie kolumnę i wiersz który przecina się z tą kolumną na polu z liczbą 1. Jeżeli ta kolumna składa się z samych -1 to usuwamy dowolną kolumnę (przekonaj się, że to wystarczy).